AtCoder Beginner Contest 313

AtCoder Beginner Contest 313

A - To Be Saikyo

思路：找到最大的，和第一个比较

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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,mod=998244353;
const double eps=1e-6;

int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int c(int a,int b){
    if(b>a)return 0;
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j){
        res=res*j%mod;
        res=res*ksm(i,mod-2)%mod;
    }
    return res;
}
int Lucas(int a,int b){
    if(a<mod&&b<mod)return c(a,b);
    return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){

}


void solve(){
    int n;cin>>n;
    vector<int>ve(n);
    int ma=0;
    for(int i=0;i<n;++i){
        cin>>ve[i];
        if(i){
            ma=max(ma,ve[i]);
        }
    }
    if(ma>=ve[0]){
        cout<<abs(ma-ve[0])+1;
    }else cout<<0;
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B - Who is Saikyo?

思路：保证有一个最大的，将一对关系中较小的一方标记，最大的一定没有被标记且没被标记的只有一个

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int c(int a,int b){
    if(b>a)return 0;
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j){
        res=res*j%mod;
        res=res*ksm(i,mod-2)%mod;
    }
    return res;
}
int Lucas(int a,int b){
    if(a<mod&&b<mod)return c(a,b);
    return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){

}


void solve(){
    int n,m;cin>>n>>m;
    vector<int>cnt(n+1);
    for(int i=0,x,y;i<m;++i){
        cin>>x>>y;
        cnt[y]++;
    }
    int ans,s=0;
    for(int i=1;i<=n;++i){
        if(cnt[i]==0)ans=i,s++;
    }
    if(s==1)cout<<ans;
    else cout<<-1;
    return;
}
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 - Approximate Equalization 2

思路：最终的数组取值为k=all/n(上取或下取)为最优情况，答案取大于k和小于k的操作的最大值（一加对应一减）

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int c(int a,int b){
    if(b>a)return 0;
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j){
        res=res*j%mod;
        res=res*ksm(i,mod-2)%mod;
    }
    return res;
}
int Lucas(int a,int b){
    if(a<mod&&b<mod)return c(a,b);
    return c(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
void init(){

}


void solve(){
    int n;cin>>n;
    vector<int>ve(n);
    int all=0;
    for(int i=0;i<n;++i)cin>>ve[i],all+=ve[i];
    int x=all/n,y=(all+n-1)/n;
    int xx=0,yy=0;
    for(int i=0;i<n;++i){
        if(ve[i]<x)xx+=abs(ve[i]-x);
        if(ve[i]>y)yy+=abs(ve[i]-y);
    }
    cout<<max(xx,yy);
    return;
}
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 - Odd or Even

思路：可以发现奇偶性相加等同于奇偶性异或和，可先用k+1次：{1，...，k}、{2，...，k+1}、{3，...，1}、...、{k+1，...，k-1}，可求出k*（a₁+...+a_k+1），由于k为奇数，那么前k+1次的提问的答案的和与（a₁+...+a_k+1）奇偶性相同；然后每一次的提问的答案异或上（a₁+...+a_k+1）即为1~k+1中缺少的那个数，这样便可求出1~k+1的所有数；

对于第i=[k+2，n]个数，提问为{1，...，k-1，i}，便可求出ai

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

const int mod=998244353;
void solve(){
    int n,k;cin>>n>>k;
    vector<int>ve(n+1);
    int pre=0;
    for(int i=1;i<=k+1;++i){
        cout<<"?";
        for(int j=1;j<=k+1;++j)
            if(i!=j)cout<<" "<<j;
        cout<<'\n';
        cin>>ve[i];
        pre^=ve[i];
    }
    for(int i=1;i<=k+1;++i){
        ve[i]^=pre;
    }
    int a,b=0;
    for(int i=1;i<k;++i)b^=ve[i];
    for(int i=k+2;i<=n;++i){
        cout<<"?";
        for(int j=1;j<k;++j)cout<<" "<<j;
        cout<<" "<<i<<'\n';
        cin>>a;
        ve[i]=b^a;
    }
    cout<<"!";
    for(int i=1;i<=n;++i)cout<<" "<<ve[i];
    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;
}

E - Duplicate

思路：先判断操作次数是否有限，可以发现若要操作次数有限，相邻的两个数必有一个1，否则将会永远操作；

计算操作次数：res表示准备删除s[i]时的已有的操作次数；对于s[i]，每一次操作s[i]增加（s[i]-'0'-1）个，当删除s[i]后的操作次数为res+res*（s[i]-'0'-1）+1，最后一个数不用删除，即res-1

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

const int mod=998244353;
void solve(){
    int n;
    string s;
    cin>>n>>s;
    for(int i=1;i<s.size();++i){
        if(s[i]!='1'&&s[i-1]!='1'){
            cout<<-1;return;
        }
    }
    int res=1;
    for(int i=s.size()-2;i>=0;--i){
        res=(res+res*(s[i+1]-'1')%mod+1)%mod;
    }
    res--;
    cout<<res;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}