Codeforces Round #629 (Div. 3)题解

A. 给你两个数a，b，每次操作可以a:=a+1，操作多少次之后能使得a%b==0?

　　输出a对b的上取整乘以b与a的差就可以通过。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

void solve(){
    int a,b;
    a=read(),b=read();
    cout<<(a+b-1)/b*b-a<<endl;
}

int main(){
    int cases;cases=read();
    while(cases--){
        solve();
    }

    return 0;
}
View Code

B. 给两个数字n，k，构造一个长度为n，有n-2个a，2个b的，字典序为k的字符串。

　　找规律，发现周期为1的字符串，开头的b在n-1的位置，第二个b的不断靠近，确定周期即可。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

void solve(){
    int n;n=read();
    int k=read();

    int t=1;
    int s=0;
    while(s+t<k){
        s+=t;
        t+=1;
    }

    int pos=n-t-1;
    k-=s;
    for(int i=0;i<n;++i){
        if(i==pos||i==n-k){
            cout<<"b";
        }else{
            cout<<"a";
        }
    }
    cout<<endl;
}

int main(){
    int cases;cases=read();
    while(cases--){
        solve();
    }

    return 0;
}
View Code

C. 给你一个字符串s，构造两个字符串s1，s2。使得s中的每一个数字都是s1，s2中对应位置数之和模3的结果并且其中最大的字符串最小。

　　s[i]=0,s1[i]=s2[i]=0,第一次s[i]=1的时候，给s1[i]=1，s2[i]=0，此后s[i]=1全都给s2[i]=1，s[i]=2给s2[i]=2即可通过。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    string s1="1";
    string s2="1";

    int ok=0;
    for(int i=1;i<n;++i){
        if(s[i]=='0'){
            s1+="0";
            s2+="0";
        }else if(s[i]=='2'){
            if(ok){
                s2+="2";
                s1+="0";
            }else{
                s1+="1";
                s2+="1";
            }
        }else{
            if(!ok){
                s1+="1";
                s2+="0";
                ok=1;
            }else{
                s1+="0";
                s2+="1";
            }
        }
    }

    cout<<s1<<endl;
    cout<<s2<<endl;
}

int main(){
    int cases;cases=read();
    while(cases--){
        solve();
    }

    return 0;
}
View Code

D. 给一个长度为n的环，里面的元素有不同的类型，要求相邻的元素且类型相同时，涂上的颜色不能相同，输出最小颜色数和一种解。

　　首先答案不会超过3，全都相等时给出n个1。n为偶数的时候1和2交错，n为奇数的时候，如果有两个相同类型的相邻或者是首尾相等，答案就是2.构造一种即可。

　　其他情况输出前n-1个为1和2交错，3作为结尾就能通过(wa得飞起。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

void solve(){
    int n=read();
    vector<int> A(n);
    int isOne=1;
    for(int i=0;i<n;++i){
        A[i]=read();
        if(A[i]!=A[0])isOne=0;
    }

    if(isOne){
        cout<<"1
";
        for(int i=0;i<n;++i)cout<<"1"<<" 
"[i==n-1];
        return;
    }

    if(!(n&1)){
        cout<<"2
";
        for(int i=0;i<n;++i){
            if(i&1)cout<<"2 ";
            else cout<<"1 ";
        }
        cout<<"
";
        return;
    }

    if((n&1)&&A[0]==A[n-1]){
            cout<<"2
";
        for(int i=0;i<n-1;++i){
            if((i&1))cout<<"2 ";
            else cout<<"1 ";
        }
        cout<<"1
";
        return;
    }
    int isTwo=0;
    for(int i=1;i<n;++i)if(A[i]==A[i-1])isTwo=i;

    if(isTwo){
        vector<int>ans={1};
        for(int i=1;i<n;++i){
            if(i==isTwo)ans.PB(ans[i-1]);
            else ans.PB(3-ans[i-1]);
        }
        cout<<"2
";
        for(int i=0;i<n;++i)cout<<ans[i]<<" 
"[i==n-1];
        return;
    }

    cout<<"3
";
    for(int i=0;i<n-1;++i){
        if(i&1)cout<<"2 ";
        else cout<<"1 ";
    }

    cout<<"3
";
}

int main(){
    int cases;cases=read();
    while(cases--){
        solve();
    }

    return 0;
}

/*
1
7
5 6 6 1 3 5 4

*/
View Code

 E. 给一棵树，多次询问，给定n个点，问是否有一条链能够使得所有点到这条链的距离不超过1。

　　对于某一个特定的点来说，要包括这个点，就必须包括这个点的父亲节点，把所有的父亲节点拿出来。考虑是否存在一条链把它们都包含，这个可以通过从上往下走和从下往上走来解决。

　　两种解法都要求将深度排序，之后，第一种通过判断下一个点是否在自己的子树中即可，具体实现上用dfs序来解决。第二种解法可以通过寻找LCA来解决，带个log。给出第一种解法的代码。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

#define go(e,u) for(int e=head[u];e;e=Next[e])
int to[MAXN<<1],Next[MAXN<<1],head[MAXN],tol;

void add_edge(int u,int v){
    Next[++tol]=head[u];to[tol]=v;head[u]=tol;
    Next[++tol]=head[v];to[tol]=u;head[v]=tol;
}

int n,m;
int fa[MAXN], dep[MAXN];

int L[MAXN], R[MAXN], dfn;

void dfs(int u, int f){
    L[u]=++dfn;
    go(e,u){
        int v=to[e];
        if(v==f)continue;
        else{
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
    R[u]=dfn;
}

bool cmp(int a, int b){
    return dep[a]<dep[b];
}

int main(){
    n=read(),m=read();
    for(int i=1;i<n;++i){
        int u,v;
        u=read();v=read();
        add_edge(u,v);
    }
    dfs(1,0);
    while(m--){//暴力会被一条链的情况卡掉,退化为O(n^2)
        int num;
        num=read();
        vector<int> nodes;
        for(int i=0;i<num;++i){
            int x=read();
            if(x!=1)nodes.PB(fa[x]);
        }

        int ok=1;
        sort(nodes.begin(),nodes.end(),cmp);
        for(int i=0;i<SZ(nodes)-1;++i){
            int x=nodes[i];
            int y=nodes[i+1];
            if(R[y]<L[x]||L[y]>R[x]){
                ok=0;
                break;
            }
        }

        if(!ok)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;

    }

    return 0;
}
View Code

 F. 给一个长度为n的数组，每次操作可以将数组中最小的数加1，最大的数减1。问最少操作多少次才能使得数组中重复元素超过k个。

　　将元素排序，考虑最后相等超过k个的元素必然是数组中的某一个。枚举一下是哪一个，由于刚开始的时候是没有收益的(不会使得相等的数增加)，只有将其他元素都增加到A[i]-1或者减少到A[i]+1时才能每操作1次，有1的收益。

　　这个时候我们只需要快速得到将前面所有元素全都变成A[i]-1和后面的元素全都变成A[i]+1的代价，然后考虑先取左边还是先取右边即可，用前缀和O(n)就能做完。

#include<bits/stdc++.h>

#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

inline int read(){
    int res=0, f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}

const int MAXN = 200'005;

const int MOD = 1000000007;

void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}

map<int, int> H;

LL sum[MAXN];

int n, k;

int A[MAXN];

int pos[MAXN], top;

void build(){
    for(int i=1;i<=n;++i){
        sum[i]=sum[i-1]+A[i];
    }
}


LL query(int L, int R){
    return sum[R]-sum[L-1];
}

int main(){
    n=read();k=read();

    for(int i=1;i<=n;++i)A[i]=read();
    sort(A+1,A+n+1);
    for(int i=1;i<=n;++i)++H[A[i]];
    for(int i=1;i<=n;++i){
        if(A[i]!=A[i-1]){
            pos[++top]=i;
        }
    }

    build();
    LL ans=1e18;
    for(auto it:H){
        if(it.sd>=k){
            cout<<"0";
            return 0;
        }
    }
    for(int i=1;i<=top;++i){
        LL res1=0,res2=0;
        int t=H[A[pos[i]]];
        int l1=1,r1=pos[i]-1;
        int l2=pos[i]+t,r2=n;

        LL cost1=1e18;
        LL cost2=1e18;

        if(r1>=l1)cost1=1ll*r1*(A[pos[i]]-1)-query(l1,r1);
        if(r2>=l2)cost2=query(l2,r2)-1ll*(r2-l2+1)*(A[pos[i]]+1);

        int num1=r1,num2=(r2-l2+1);

        /*
        不能只根据填平的代价大小去决定选哪边
        */

        res1+=cost1;
        if(num1+t>=k){
            res1+=k-t;
        }else{
            res1+=num1;
            res1+=cost2;
            res1+=k-(t+num1);
        }

        res2+=cost2;
        if(num2+t>=k){
            res2+=k-t;
        }else{
            res2+=num2;
            res2+=cost1;
            res2+=k-(t+num2);
        }

        ans=min(ans,min(res1,res2));
    }
    cout<<ans;
    return 0;
}

/*
8 6
4 5 1 2 3 5 3 3
5
*/
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JohnRan/p/12586491.html