Codeforces Round #629 (Div. 3)

第一次AK写篇题解庆祝一下~~

文章目录

A.Divisibility Problem
B. K-th Beautiful String
C. Ternary XOR
D. Carousel
E. Tree Queries
F. Make k Equal

A.Divisibility Problem

看代码吧

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
    for(scanf("%lld",&_);_;_--){
         scanf("%lld%lld",&n,&m);
         if(n%m==0) printf("0\n");
         else {
            LL ans=(n/m+1)*m;
            printf("%lld\n",abs(ans-n));
         }
    }
}

B. K-th Beautiful String

通过枚举第一个B的位置，可以算出排名的上限，然后从n-1开始枚举直到上限大于等于m，此时在求出第二个B的位置。

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
    for(scanf("%lld",&_);_;_--){
         scanf("%lld%lld",&n,&m);
         int pos1,pos2;
         for(int i=n-1;i>=1;i--){
            LL c=1ll*(n-i-1)*(n-i)/2+n-i;
            //cout<<c<<endl;
            if(c>=m){
                pos1=i;
                c=1ll*(n-i-1)*(n-i)/2;
                pos2=n-(m-c)+1;
                break;
            }
         }
         //printf("%d,%d\n",pos1,pos2);
         for(int i=1;i<=n;i++){
            if(i==pos1||i==pos2) printf("b");
            else printf("a");
         }
         printf("\n");
    }
}

C. Ternary XOR

贪心放，没出现1之前，两边平分，出现1之后，放小的那边

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
    for(scanf("%lld",&_);_;_--){
          scanf("%d",&n);
          scanf("%s",s+1);
          int flag=0;
          for(int i=1;i<=n;i++){
            if(!flag){
                if(s[i]=='2') {
                    a[i]=1;
                    b[i]=1;
                }
                else if(s[i]=='1'){
                    flag=1;
                    a[i]=1;
                    b[i]=0;
                }
                else {
                    a[i]=0;b[i]=0;
                }
            }
            else {
                if(s[i]=='2'){
                    a[i]=0;
                    b[i]=2;
                }
                else if(s[i]=='1'){
                    a[i]=0;
                    b[i]=1;
                }
                else {
                    a[i]=b[i]=0;
                }
            }
          }
          for(int i=1;i<=n;i++) printf("%d",a[i]);printf("\n");
          for(int i=1;i<=n;i++) printf("%d",b[i]);printf("\n");
    }
}

D. Carousel

首先想到的是把相邻的相同类型看成一个，然后12121212这么放，最后如果发现col[n]==col[1]&&a[1]!=a[n]那就把col[n]变成3，交上去后发现wa了
仔细想想发现如果中间出现相邻的相同类型的情况，那么可以借助这个中转站，将121212变成212121，这样col[n]就不会等于col[1]了（~~md这个地方break写错位置wa了好多发）~~

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

LL _,n,k,a[maxn],col[maxn],c[maxn],d[maxn];
char s[maxn],t[maxn];
int main(){
     for(scanf("%lld",&_);_;_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        int k=0;
        for(int i=1;i<=n;){
            int j=i+1;
            col[i]=k;
            while(j<=n&&a[i]==a[j]){
                col[j]=k;
                j++;
            }
            i=j;
            k^=1;
        }
        if(col[n]==col[1]&&a[n]!=a[1]) {
            int f=0;
            for(int i=2;i<=n;i++){
                if(col[i]==col[i-1]){
                    for(int j=i;j<=n;j++){
                        col[j]^=1;
                    }
                    f=1;
                    break;
                }
            }
            if(!f) col[n]=2;
        }
        k=0;
        for(int i=1;i<=n;i++){
            k=max(1ll*k,col[i]);
        }
        printf("%d\n",k+1);
        for(int i=1;i<=n;i++) printf("%d ",col[i]+1);
        printf("\n");
     }
}

E. Tree Queries

根节点肯定是向某个叶子走，那么这个过程中，所有跟他距离<=1的点有一个性质，就是他的父亲一定在这条路上，所以我们把读入的点都变成他的父亲节点，然后按深度排序后，相邻的两个点的lca一定是深度较小的那个，否则就输出NO

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

int _,n,m,fa[maxn],dep[maxn],dp[200010][30],d[maxn],k[maxn];
VI G[maxn];
void dfs(int u,int f){
     fa[u]=f;
     for(int v:G[u]){
        if(v==f) continue;
        dfs(v,u);
     }
}
void bfs(int x)
{
     d[x]=1;
     queue<int>q;q.push(x);
     int Lgn=(int)(log(n)/log(2));
     while(!q.empty()){
        int f=q.front();q.pop();
        int len=G[f].size();
        for(int i=0;i<len;i++){
            int to=G[f][i];
            if(!d[to]){
                q.push(to);
                d[to]=d[f]+1;
                dp[to][0]=f;
                for(int i=1;i<=Lgn;i++){
                    dp[to][i]=dp[dp[to][i-1]][i-1];
                }
            }
        }
     }
}

int Lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    int lgn=(int)(log(n)/log(2));
    for(int i=lgn;i>=0;i--){
        int to=dp[x][i];
        if(d[to]>=d[y]){
            x=to;
        }
    }
    if(x==y) return x;
    for(int i=lgn;i>=0;i--){
        int tx=dp[x][i],ty=dp[y][i];
        if(tx!=ty){
            x=tx;y=ty;
        }
    }
    return dp[x][0];
}
bool cmp(int a,int b){
     return d[a]<d[b];
}
int main(){
      scanf("%d%d",&n,&m);
      for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
      }
      dfs(1,-1);
      fa[1]=1;
      bfs(1);
      while(m--){
        int s;scanf("%d",&s);
        for(int i=1;i<=s;i++){
            scanf("%d",&k[i]);
            k[i]=fa[k[i]];
        }
        sort(k+1,k+1+s,cmp);
        int flag=0;
        for(int i=s-1;i>=1;i--){
            if(Lca(k[i],k[i+1])!=k[i]) {
                flag=1;break;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
      }
}

F. Make k Equal

贪心，最后出现次数>=k的一定是原数列中出现过的元素，那么我们可以O(n）枚举这个元素，然后考虑怎么O(1)或O(log)求出这个元素的答案。
仔细分析一下题目的移动规律发现要想使最大/小值变成 C，那么所有大于C的数就都得变成C+1 OR C-1（这一部分可以通过后/前缀和），然后在根据需要的个数看转移几个就行了。
最后分类讨论一下是左边全部转移还是右边全部转移就ok了

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

LL _,n,k,a[maxn],b[maxn],c[maxn],d[maxn];
char s[maxn],t[maxn];
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);

        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) c[i]=c[i-1]+a[i];
    for(int i=n;i>=1;i--) d[i]=d[i+1]+a[i];


    int m=unique(b+1,b+1+n)-b-1;
    LL ans=inf;
    for(int i=1;i<=m;i++){
        int l=lower_bound(a+1,a+1+n,b[i])-a;
        int r=upper_bound(a+1,a+1+n,b[i])-a-1;
        int cnt=r-l+1;
        cnt=k-cnt;
        if(cnt<=0) {
            ans=0;break;
        }
        else {
            LL c1=(b[i]-1)*(l-1)-c[l-1];
            if(l-1>=cnt){
                c1+=cnt;
                ans=min(ans,c1);
            }
            else {
                c1+=(l-1);

                c1=c1+d[r+1]-(b[i]+1)*(n-r);

                c1=c1+(cnt-(l-1));
                //cout<<i<<','<<c1<<','<<d[r+1]<<endl;
                ans=min(ans,c1);
            }

            c1=d[r+1]-(b[i]+1)*(n-r);

            if(n-r>=cnt){
                c1+=cnt;
                ans=min(ans,c1);
            }
            else {
                c1+=(n-r);

                c1=c1+(b[i]-1)*(l-1)-c[l-1];

                c1=c1+(cnt-(n-r));
                ans=min(ans,c1);
            }
        }
    }
    printf("%lld\n",ans);

}