2020年第一届辽宁省大学生程序设计竞赛

题目列表

• • A
  • B
  • C
  • F
  • G
  • I
  • J
  • K

A

题意描述

思路

可以使用一个 p a i r pair pair数组来保存< i n t , s t r i n g int,string int,string>对，排序后按题意模拟即可。注意输出队员姓名的顺序是按照排名从大到小排列，并且要开 3 3 3倍 n n n的空间。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=4*1e4+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
pair<int,string> a[N*3];
void solve(){
    int n;
    scanf("%d",&n);
    rep(i,0,n*3){
        string s;
        int n;
        cin>>s;
        scanf("%d",&n);
        a[i]={n,s};
    }
    sort(a,a+n*3);
    int idx=0;
    rep(i,0,n*3){
        vector<pair<int,string>> v;
        rep(j,i,i+3) v.PB({a[j].x,a[j].y});
        sort(all(v));
        reverse(all(v));
        printf("ACM-%d ",idx++);
        rep(j,0,2) cout<<v[j].y<<' ';
        cout<<v[2].y<<endl;
        i+=2;
    }
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int t;scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}

B

题意描述

思路

答案只会有 0 , 1 , 2 0,1,2 0,1,2三种情况。当 x = y x=y x=y时，最小距离为 0 0 0。当 x x x和 y y y互质时，最小距离为 1 1 1。否则可以先跳到一个与 x x x互质的数，再跳到 y y y，此时最小距离为 2 2 2。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=100100;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
void solve(){
    int n,q;
    scanf("%d%d",&n,&q);
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y) printf("0\n");
        else{
            printf("%d\n",min(__gcd(x,y),2));
        }
    }
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //int t;scanf("%d",&t);
    //while(t--)
        solve();
    return 0;
}

C

题意描述

思路

在纸上推完后发现每个月兔子的个数是斐波那契，由于 n n n太大，所以每次计算都对 m m m求余即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1010;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
ll a[N];
void solve(){
    int n,m;
    scanf("%d%d",&n,&m);
    a[1]=1,a[2]=1;
    rep(i,3,n+1) a[i]=(a[i-1]+a[i-2])%m;
    a[n]+=m;
    a[n]--;
    printf("%d\n",(a[n]%m));
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int t;scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}

F

题意描述

思路

由于可以任意排列字符串内字符的顺序，所以我们只需要关注字符串内的字符个数。
并且回文串的两边一定是对称的，所以我们可以使用一个 m a p map map来存储相同字符串的个数。关于判断字符串相同，可以将字符串排序后添加到 m a p map map中。
然后从两边开始添加，如果相同字符串的个数大于等于 2 2 2，则说明该字符串可以放到两边，一直重复这个过程直到两边无法放字符串即可。
最后再考虑中间位置的字符串，如果 m m m是偶数，则只能放字母出现次数为偶数的字符串。如果 m m m是奇数，则只能放字母出现次数为奇数的字符串，这里做下判断即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=105;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
void solve(){
    int n,m;
    cin>>n>>m;
    map<string,int> cnt;
    rep(i,0,n){
        string s;
        cin>>s;
        sort(all(s));
        cnt[s]++;
    }
    int ans=0;
    while(true){
        bool ok=false;
        for(auto p : cnt){
            if(p.y>=2){
                ans+=sz(p.x)*2;
                cnt[p.x]-=2;
                ok=true;
            }
        }
        if(!ok) break;
    }
    for(auto p : cnt){
        if(p.y<=0) continue;
        int c[26];
        mst(c,0);
        string sss=p.x;
        rep(j,0,sz(sss)){
            c[sss[j]-'a']++;
        }
        int one=0,zero=0;
        rep(j,0,26){
            if(c[j]){
                if(c[j]&1) one++;
                else zero++;
            }
        }
        if(m%2==0 && one==0){
            ans+=sz(sss);
            break;
        }
        if(m%2!=0 && one==1){
            ans+=sz(sss);
            break;
        }
    }
    cout<<ans<<endl;
}
signed main(){
    IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //int t;scanf("%d",&t);
    //while(t--)
        solve();
    return 0;
}

G

题意描述

思路

筛出质数后 O ( n ) O(n) O(n)扫描一遍即可。注意离它最近的不一定是它前面的质数，也有可能是它后面的质数

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=10010;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
vector<int> prime;
bool st[N];
void get_prime(){
    st[1]=true;
    st[0]=true;
    rep(i,2,N+1){
        if(!st[i]){
            prime.PB(i);
        }
        for(int j=0;prime[j]<=N/i;j++){
            st[i*prime[j]]=true;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}
void solve(){
    int n;
    scanf("%d",&n);
    if(!st[n]) printf("YES\n");
    else{
        rep(i,0,sz(prime)){
            if(prime[i]>=n){
                int res=min(abs(prime[i]-n),abs(prime[i-1]-n));
                printf("%d\n",res);
                return;
            }
        }
    }
}
signed main(){
    get_prime();
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int t;scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}

I

题意描述

思路

按照题意模拟即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=505;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
void solve(){
    int op,a,b;
    scanf("%d%d%d",&op,&a,&b);
    if(op==1) printf("%d\n",a+b);
    if(op==2) printf("%d\n",a-b);
    if(op==3) printf("%d\n",a*b);
    if(op==4) printf("%d\n",a/b);
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int t;scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}

J

题意描述

思路

我们可以从面积的角度来考虑，首先对于如下的一个三角形

它的面积为 1 2 ∗ A B → × A C → \frac{1}{2}*\overrightarrow{AB}\times \overrightarrow{AC} 21​∗AB ×AC ,即两个向量叉乘的一半。
如果一个点在三角形内，则

所以我们可以根据这个来判断覆盖在该点上的三角形个数是奇数还是偶数。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1010;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
struct Node{
    int x,y;
}node[N][3];
double area(Node n1,Node n2,Node n3){
    int x1=n1.x-n2.x;
    int y1=n1.y-n2.y;
    int x2=n1.x-n3.x;
    int y2=n1.y-n3.y;
    return abs(x1*y2-x2*y1)/2.0;
}
void solve(){
    int n,q;scanf("%d%d",&n,&q);
    rep(i,0,n){
        int x,y;
        rep(j,0,3){
            scanf("%d%d",&x,&y);
            node[i][j]={x,y};
        }
    }
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        Node no={x,y};
        int cur=0;
        rep(i,0,n){
            double h1=area(node[i][0],node[i][1],node[i][2]);
            double h2=area(node[i][0],node[i][1],no)+area(node[i][1],node[i][2],no)+area(node[i][0],node[i][2],no);
            //printf("%f %f\n",h1,h2);
            if(h1==h2) cur++;
        }
        if(cur%2) printf("Yes\n");
        else printf("No\n");
    }
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //int t;scanf("%d",&t);
    //while(t--)
        solve();
    return 0;
}

K

题意描述

思路

首先我们要知道异或的两个性质：
1. 1. 1. x x x^ x x x= 0 0 0
2. 2. 2. 0 0 0^ x x x= x x x

可以使用类似前缀和的方法求出从 [ 1 , n ] [1,n] [1,n]范围内的异或和。设 m p [ i ] mp[i] mp[i]为与当前异或值异或起来等于 x x x的方案数，则方案数的更新为当前的方案数加上 i i i^ x x x的方案数。遍历一遍即可得到答案。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
typedef __int128 lll;
constexpr int N=1e5+10;
constexpr int M=1e6+10;
constexpr int INF=0x3f3f3f3f;
constexpr int mod=1e9+7;
int a[N],Xor[N];
map<int,int> mp;
void solve(){
    int n,x;
    scanf("%d%d",&n,&x);
    rep(i,1,n+1){
        scanf("%d",&a[i]);
        Xor[i]=Xor[i-1]^a[i];
    }
    mp[0]=1;
    ll ans;
    rep(i,1,n+1){
        ans=mp[Xor[i]^x];
        mp[Xor[i]]=(mp[Xor[i]]+ans)%mod;
    }
    printf("%lld\n",ans%mod);
}
signed main(){
    //IOS;
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    //int t;scanf("%d",&t);
    //while(t--)
        solve();
    return 0;
}