专栏首页奇妙的算法世界2020年第一届辽宁省大学生程序设计竞赛

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

2020-11-242020-11-24 15:13:08阅读 820

题目列表

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;
}

本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。

展开阅读全文

我来说两句

0 条评论

登录后参与评论

codeforces 1389B（贪心）
dejavu1zz
Codeforces Round #677 (Div. 3)
找到起始 1 1 ...
dejavu1zz
Codeforces Round #677 (Div. 3)
显然，如果最大值和最小值相同，则肯定不满足题意。否则，一定存在一个值mx，它的左右两边存在一个小于它的数。此时，该位置的鱼满足题意。
dejavu1zz
Codeforces Round #677 (Div. 3)
找到起始 1 1 ...
dejavu1zz
codeforces 1389B（贪心）
dejavu1zz
Codeforces Round #677 (Div. 3)
显然，如果最大值和最小值相同，则肯定不满足题意。否则，一定存在一个值mx，它的左右两边存在一个小于它的数。此时，该位置的鱼满足题意。
dejavu1zz
codeforces 1282B（dp）
dejavu1zz
codeforces 1437D（思维）
题目中说每个点的子结点都是升序排列的，并且1结点是父结点，所以我们可以从第二层开始，统计第二层呈升序排列的点的个数，该个数即为第二层的结点数。然后以第二层为基础...
dejavu1zz
07:不与最大数相同的数字之和
07:不与最大数相同的数字之和总时间限制:1000ms内存限制:65536kB描述输出一个整数数列中不与最大数相同的数字之和。输入输入分为两行：第一行为...
attack
一张图带你看懂区块链项目生态
正如我之前在ICO的“泡沫”博客中写到的，区块链技术，加密货币和代币销售现在风靡一时。在过去5年多的时间里，我一直在风险投资行业工作，这是在任何技术领域都没见...
企鹅号小编

腾讯云·社区

dejavu1zz