Codeforces Round #629 (Div. 3)

Codeforces Round #629 (Div. 3)

A.Divisibility Problem

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    //IN
    int _;cin>>_;
    while(_--){
        ll a,b;
        sc("%lld%lld",&a,&b);
        if(a%b==0)O(0);
        else{
            ll x=a/b;
            O((x+1)*b-a);
        }
    }
}

B.K-th Beautiful String

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
   // IN
    int _;cin>>_;
    while(_--){
        int n,k;
        sc("%d%d",&n,&k);
        if(n==2){
            O("bb");continue;
        }
        int a=n-2;
        for(;a;){
            int b=n-a-1;
            if(k>b)k-=b,a--;
            else break;
        }
        for(int i=0;i<a;i++)putchar('a');putchar('b');
        for(int i=0;i<n-a-1-k;i++)putchar('a');putchar('b');
        for(int i=0;i<k-1;i++)putchar('a');putchar(10);
    }
}

C.Ternary XOR

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    //IN
    int _;cin>>_;
    while(_--){
        int n;sc("%d",&n);
        vector<int>y(n,0),p(n,0);
        int b[3]={0};
        string x;cin>>x;
        for(int i=0;i<n;i++){
            if(x[i]=='0')y[i]=0,p[i]=0;
            else if(x[i]=='2'){
                if(b[1])y[i]=0,p[i]=2;
                else y[i]=1,p[i]=1;
            }
            else {
                if(b[1])y[i]=0,p[i]=1;
                else y[i]=1,p[i]=0;
            }
            b[x[i]-'0']=1;
        }
        for(int i=0;i<n;i++)pr("%d",y[i]);O("");
        for(int i=0;i<n;i++)pr("%d",p[i]);O("");
    }
}

D.Carousel

答案只能是1，2，3；去掉末尾和首项相同的元素，如果长度为1就是1，长度偶数或者长度减小了就是2，
否则再找有没有相邻相同的，有就是2，否则就是3.细节处理起来有点麻烦。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int t[N],a[N];
int main(){
    //IN
    int q;cin>>q;
    while(q--){
        int n;sc("%d",&n);
        for(int i=0;i++<n;sc("%d",&t[i]),a[i]=t[i]);
        int m=n;
        while(a[1]==a[m]&&m)m--;
        if(m<=1){
            O(1);
            for(int i=0;i<n;i++)pr("1 ");
            O("");continue;
        }
        if(n%2==0){
            O(2);
            for(int i=0;i<n;i++)pr("%d ",i%2==0?2:1);
            O("");
            continue;
        }
        if(n==m){
            int p=0;
            for(int i=1;i<n;i++){
                if(t[i]==t[i+1]){
                    p=i;break;
                }
            }
            if(p){
                O(2);
                for(int i=1;i<=p;i++)pr("%d ",i%2==0?2:1);
                if(p&1)pr("1 ");else pr("2 ");
                for(int i=p+2;i<=n;i++)pr("%d ",i%2==0?1:2);
                O("");
            }else{
                O(3);
                for(int i=1;i<n;i++)pr("%d ",i%2==0?2:1);
                O(3);
            }
        }else{
            O(2);
            for(int i=0;i<n;i++)pr("%d ",i%2==0?1:2);
            O("");
        }
    }
}

E.Tree Queries

这题转化为求k个点是否在一条链上，可以用序判断，对于，两个点，，
他们在一条链上的条件为： ,对深度排序，可以满足这种关系。
或者对于所有节点 。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int k[N],f[N];
int L[N],R[N],t;
vector<int>g[N];
int n,m;
void dfs(int u,int fa){
    f[u]=***]=++t;
    for(int& v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    R[u]=t;
}
int main(){
    sc("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);f[1]=1;
    while(m--){
        int x;sc("%d",&x);
        for(int i=0;i++<x;sc("%d",&k[i]),k[i]=f[k[i]]);
        int mx=n,ma=1;
        for(int i=1;i<=x;i++)mx=min(mx,R[k[i]]),ma=max(ma,L[k[i]]);
        int ok=ma<=mx;
        puts(ok?"YES":"NO");
    }
}

F.Make k Equal

先排序，枚举当序列都变成时的最小值，分几种情况讨论。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,k;
int a[N],x=0,cnt=0;
ll pre[N],suf[N];
int main(){
    cin>>n>>k;
    for(int i=0;i++<n;sc("%d",&a[i]));sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
    for(int i=2;i<=n;i++)if(a[i]==a[i-1])x++;else cnt=max(cnt,x),x=1;cnt=max(cnt,x);
    if(cnt>=k)return O(0);ll ans=1e18+11;
    for(int i=1;i<=n;i++){
        ll res=1LL*(i-1)*a[i]-pre[i-1]-1LL*a[i]*(n-i)+suf[i+1]-(n-k);
        if(i>=k)res=min(res,1LL*(i-1)*a[i]-pre[i-1]-(i-k));
        if(n-i+1>=k)res=min(res,suf[i+1]-1LL*(n-i)*a[i]-(n-i+1-k));
        ans=min(ans,res);
    }
    O(ans);
}