Codeforces Round 884 (Div. 1 + Div. 2)

Codeforces Round 884 (Div. 1 + Div. 2)

 A - Subtraction Game

思路：显而易见为a+b

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n;
    int a,b;
    cin>>n;
    while(n--){
        cin>>a>>b;
        cout<<a+b<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B - Permutations & Primes

思路：中间的被包含的次数最多，因此越往中间放的是非质数，接着放越大的质数

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int primes[N],st[N],idx;
void init(){
    st[1]=true;
    for(int i=2;i<=N/i;++i){
        if(!st[i])primes[idx++]=i;
        for(int j=0;primes[j]*i<=N;++j){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
void solve(){
    int n;cin>>n;
    vector<int>l,r;
    for(int i=1;i<=n;++i){
        if(st[i]){
            if(l.size()<=r.size())l.push_back(i);
            else r.push_back(i);
        }
    }
    for(int i=n;i>=1&&(l.size()+r.size())<n;--i){
        if(!st[i]){
            if(l.size()<=r.size())l.push_back(i);
            else r.push_back(i);
        }
    }
    for(int i=l.size()-1;i>=0;--i)cout<<l[i]<<' ';
    for(auto v:r)cout<<v<<' ';
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C - Particles

思路：发现只有不相邻的数才能合并，并且可以通过删去的方法，获取所有不相邻的数中任意的数。那么分别枚举奇和偶位置的数，大于0则取，答案为奇和偶位置情况下的最大值。当然，全为负数时，取一个最大的负数即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n;
    cin>>n;
    vector<int>ve(n+1);
    bool ok1=false,ok2=false;
    for(int i=1;i<=n;++i){
        cin>>ve[i];
        if(i%2&&ve[i]>=0)ok1=true;
        if(i%2==0&&ve[i]>=0)ok2=true;
    }
    int res1=0,res2=0;
    if(!ok1)res1=-INF;
    if(!ok2)res2=-INF;//cout<<res1<<' '<<res2<<'\n';
    for(int i=1;i<=n;++i){
        if(i%2){
            if(ok1){
                if(ve[i]>0)res1+=ve[i];
            }else{
                res1=max(res1,ve[i]);
            }
        }
        else{
            if(ok2){
                if(ve[i]>0)res2+=ve[i];
            }else{
                res2=max(res2,ve[i]);
            }
        }
    }
    int res;//cout<<res1<<' '<<res2<<'\n';
    if(n==1)res=res1;
    else res=max(res1,res2);
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D - Row Major

思路：要求所有排列方式中相邻的元素不相同，并且要求元素种类最少。

要求相邻的一行或一列的元素的排列一定是不同的，且排列的行列数为n的约数，那么像abc...abc...abc....这样的重复字符串满足相邻一列都不同；要求相邻行不同的话，那么abc...的个数k一定不为n的约数。要求种类最少的话，就让k为非n的约数的最小值即可满足相邻的一行/一列的元素排列都是不同的。

#include<bits/stdc++.h>
using namespace std;
#define  int long long
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=100+5,M=5000000000000+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
typedef long long ll;



void solve(){
    int n;
    cin>>n;
    if(n==1)cout<<"a";
    else if(n==2)cout<<"ab";
    else{
        for(int i=2;i<=n;++i){
            if(n%i){
                int cnt=n,idx=0;
                while(cnt--){
                    cout<<char('a'+(idx++%i));
                }
                break;
            }
        }
    }cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}