Codeforces Round 868 (Div. 2) A-D

EdGrass / 2023-05-18 / 原文

Codeforces Round 868 (Div. 2)

A. A-characteristic

int fac[N];
map<int,int>mp;
void init(){
    fac[1]=0;
    mp[0]=1;
    for(int i=2;i<N;i++){
        fac[i]=fac[i-1]+(i-1); 
        mp[fac[i]]=i; 
    }
}
void solve(){
    int n=read(),k=read(),ans=-1;
    for(int i=0;i<=n;i++){
            if(fac[i]+fac[n-i]==k){
                ans=i;
                break;
            }
    }
    puts(ans!=-1?"YES":"NO");
    if(ans!=-1){
        for(int i=1;i<=ans;i++){
            cout<<1<<" ";
        }
        for(int i=1;i<=n-ans;i++){
            cout<<-1<<" ";
        }
        cout<<'\n';
    }
}

B. Sort with Step

int a[N];
void solve(){
    int n=read(),k=read();
    int cnt=0;
    for(int i=1;i<=n;i++){
        a[i]=read(); 
        if(abs(a[i]-i)%k)cnt++;   
    }
    if(cnt==0)cout<<0<<'\n';
    else if(cnt==2)cout<<1<<'\n';
    else cout<<-1<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Strongly Composite

map<int ,int >mp;
void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            mp[i]+=s;
        }
    if (x > 1) mp[x]++;
}
void solve(){
    mp.clear();
    int n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        divide(x);
    }
    int ans=0,sig=0;
    for(auto i=mp.begin();i!=mp.end();i++){
        ans+=i->second/2;
        sig+=i->second%2;
    }
    if(ans<=0&&sig<3)cout<<0<<'\n';
    else cout<<ans+sig/3<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. Unique Palindromes

字符串构造题主要抓住一个k的值很小小于字母数量

首先明确一点 n个位置可以构成最多n个回文字串例如n个a就可以完成n个回文字串

先构造一个“xyz”，如果后来需要新的回文字串就用重复的字母解决，在后面补上xyz

注意，补位的xyz也需要按顺序计数输出否则过不了题中的倒数第二个样例

int x[N],c[N];
void solve(){
    int n=read(),q=read();
    for(int i=1;i<=q;i++){
        x[i]=read();
    }
    for(int i=1;i<=q;i++){
        c[i]=read();
    }
    string s="xyz";
    int now=0;
    x[0]=3;c[0]=3;
    x[q+1]=n;c[q+1]=c[q];
    for(int i=1;i<=q+1;i++){
        int len=x[i]-x[i-1];
        int par=c[i]-c[i-1];
        if(len<par){
            cout<<"NO\n";
            return ;
        }else {
            s+=string(par,'a'-1+i);
            for(int i=1;i<=len-par;i++){
                s+=s[now];
                now=(now+1)%3;
            }
        }
    }
    cout<<"YES\n";
    cout<<s<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}