Codeforces Round #629 (Div. 3)解题报告

A.Divisibility Problem

题意：
$给定 a 和 b ，每次 a 可以加 1 ，问加多少的时候 a 能整除 b$
题解：
$直接 (a <mtext> </mtext> - <mtext> </mtext> a % b) 就可以了，特判一下原本就能取余的情况$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        if(a%b){
            cout<<b-(a%b)<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}

B. K-th Beautiful String

题意：
$一个字符串包含 n - 2 个 a 和 2 个 b$
$现在需要该字符串的第 k 字典序$
题解：
$可以先确定第一个 b 的位置$
$如果第一个 b 在 n - i 的位置，第二个在最后$
$那么这之前一共存在 i * (i + 1) / 2 种情况$
$所以只要找到小于等于 k 的最大值$
$然后再把第 2 个 b 左移 k - i * (i + 1) / 2 位就可以了$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        ll i;
        for(i=1;i<=n;i++)
            if(i*(i+1)/2>=k)break;
        i--;
        ll t=i*(i+1)/2;
        ll x=k-t-1;
        i++;
        for(int j=1;j<=n;j++){
            if(j==n-i||j==n-x)cout<<'b';
            else cout<<'a';
        }
        cout<<endl;
    }
    return 0;
}

C. Ternary XOR

题意：
$假设存在一种符号 ⊙ 如果 c = a ⊙ b$
$那么 c_{i} = (a_{i} + b_{i}) % 3$
$其中 c_{i}, a_{i}, b_{i} 表示三个数中的每一位$
$给定数的长度 n 和 a ⊙ b 的结果 x$
$让你求得 a, b 并且需要使得 m a x (a, b) 最小$
题解：
$循环每一位$
$如果是 2 ， a 和 b 各自得到一个 1$
$如果是 0 ， a 和 b 各自该位为 0$
$如果是 1 ，退出循环，并把 1 给 a ，然后剩下所有数都给 b$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;string s;
        cin>>n>>s;
        string a,b;
        int i;
        for(i=0;i<n;i++){
            if(s[i]=='2'){
                a+='1';
                b+='1';
            }
            else if(s[i]=='0'){
                a+='0';
                b+='0';
            }
            else break;
        }
        if(i<n){
            a+=s[i];
            b+='0';
        }
        for(i++;i<n;i++){
            a+='0';
            b+=s[i];
        }
        cout<<a<<endl<<b<<endl;
    }
    return 0;
}

D. Carousel

题意：
$给一个环，环每个点有一种动物$
$要求给动物上色，相邻的不同的动物不能上相同的颜色$
题解：
$如果只有一种动物，全部上一种颜色$
$如果有两种，两种动物各上一种颜色，一共两种$
$如果大于两种，首先判断 n 奇偶性$
$如果为偶数，按 1212 \dots \dots 1212 排即可，两种颜色$
$如果为奇数，再按 1212 排就会出现首尾相同，但是如果首尾的动物是不同的就会出现非法情况$
$所以此时就在序列中找是否有连续相同的动物，在这个位置连续使用一个颜色两次，就可以使得首尾的颜色不相同，这样总共为两种颜色$
$如果找不道连续相同的动物，那么就是三种颜色，按 12 排列把最后一个改成 3 即可$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        set<int> s;
        for(int i=1;i<=n;i++){cin>>a[i];s.insert(a[i]);}
        if(s.size()==1){
            cout<<1<<endl;
            for(int i=1;i<=n;i++)
                cout<<1<<' ';
            cout<<endl;
            continue;
        }
        if(s.size()==2){
            vector<int> v;
            cout<<2<<endl;
            for(auto i:s)v.pb(i);
            for(int i=1;i<=n;i++)
                if(a[i]==v[0])cout<<1<<' ';
                else cout<<2<<' ';
            cout<<endl;
            continue;
        }
        if(n%2==0||a[n]==a[1]){
            cout<<2<<endl;
            for(int i=1;i<=n;i++)
                if(i&1)cout<<1<<' ';
                else cout<<2<<' ';
            cout<<endl;
        }
        else{
            int i;
            for(i=2;i<=n;i++)
                if(a[i]==a[i-1])break;
            if(i>n){
                cout<<3<<endl;
                for(int i=1;i<n;i++)
                    if(i&1)cout<<1<<' ';
                    else cout<<2<<' ';
                cout<<3<<endl;
            }
            else{
                cout<<2<<endl;
                int cnt=1;
                for(int j=1;j<=n;j++){
                    if(j==i)cnt^=1;
                    if(cnt)cout<<1<<' ';
                    else cout<<2<<' ';
                    cnt^=1;
                }
                cout<<endl;
            }
        }
    }
    return 0;
}

E. Tree Queries

题意：
$给一棵树，然后有 m 次询问$
$每次询问给出 k 个点，问是否能找到一条从根出发的简单路径$
$包含这些点或者这些点到这个路径的距离为 1$
题解：
$想找到非法情况，肯定是因为有两个点他们最近根的两棵子树上并且都不是这个根的直接子节点$
$所以直接采用 L C A ，从最深点开始找，两个点到他俩 l c a 的距离是否出现同时大于 1 的情况$
$如果有则 N O ，否则输出 Y E S$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int a[maxn];
int n,depth[maxn], f[maxn][50];
int from[maxn], to[maxn << 1], nxt[maxn << 1], cnt,Log[maxn];
//链式前向星加边
void addEdge (int u, int v) {
    to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt;
}
//计算深度&计算祖先
void dfs (int u, int fa) {
    depth[u] = depth[fa] + 1;
    for (register int i = 1; i <= Log[n]; ++i) {
        if ((1 << i) > depth[u]) break;
        f[u][i] =  f[f[u][i - 1]][i - 1];
    }
    for (register int i = from[u]; i; i = nxt[i]) {
        ll v = to[i];
        if (v == fa) continue;
        f[v][0] = u;
        dfs (v, u);
    }
}
//计算LCA
inline int LCA (int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    //我们默认x为更深的那个点
    for(register int i = Log[n] ; i >= 0 ; --i)
		if(depth[x] - (1 << i) >= depth[y]) x = f[x][i];
    //将x跳到和y同一深度上
    if (x == y) return x;
    for (register int i = Log[n]; i >= 0; --i)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    //一起向上跳
    return f[x][0];
    //不难看出，此时两个点均在其LCA的下方，往上跳一次即可
}
void init(){
	Log[0] = -1;
    for (register int i = 1, u, v; i < n; ++i) {
        cin>>u>>v;
        addEdge (u, v); addEdge(v, u);
        Log[i] = Log[i >> 1] + 1;
    }
    Log[n] = Log[n >> 1] + 1;
}
int dis(int p , int q){return depth[p] + depth[q] - 2 * depth[LCA(p , q)];}
bool cmp(int a,int b){
    return depth[a]>depth[b];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int m;
    cin>>n>>m;
    init();dfs(1,0);
    while(m--){
        int k;
        cin>>k;
        for(int i=1;i<=k;i++)cin>>a[i];
        sort(a+1,a+1+k,cmp);
        bool f=0;
        for(int i=2;i<=k;i++){
            int r=LCA(a[i],a[i-1]);
            if(dis(r,a[i-1])>1&&dis(r,a[i])>1){f=1;break;}
        }
        if(f)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

F. Make k Equal

题意：
$给定长度为 n 的数组$
$每次可以使最大数加一，或者最小数减一$
$问最少多少次操作可以获得 k 个相等的数$
题解：
$首先将数组排序，计算出前缀和后缀和$
$然后循环判断找出变成 k 个 a_{i} 所需要的次数，取最小$
$对于每个数，如果他的左边或者右边有 k - 1 个数$
$如果是左边让所有数变成 a_{i} - 1 ，使用前缀和计算次数$
$如果是右边让所有数变成 a_{i} + 1 ，使用后缀和计算次数$
$然后加上 k - 1, 也就是把他们变成 a_{i} + 1 或 a_{i} - 1 次数$
$如果两边都不够，就把左边全部变成 a_{i} - 1, 右边 a_{i} + 1$
$同时使用前缀和后缀和计算次数，然后加上 k - 1$
$最后在这些里取最小，为了排除直接有相等的情况，如果这个值小于 0 ，那么就变零$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll a[maxn],s1[maxn],s2[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int cnt=1;
    for(int i=1;i<=n;i++){
        s1[i]=s1[i-1]+a[i];
        if(a[i]==a[i-1])cnt++;
        else cnt=1;
        if(cnt>=k){cout<<0<<endl;return 0;}
    }
    for(int i=n;i>=1;i--)
        s2[i]=s2[i+1]+a[i];
    ll ans=inf*inf;
    for(int i=1;i<=n;i++){
        ll tmp=inf*inf;
        if(i>=k)tmp=min(tmp,(a[i]-1)*(i-1)-s1[i-1]+k-1);
        if(n-i+1>=k)
            tmp=min(tmp,s2[i+1]-(a[i]+1)*(n-i)+k-1);
        if(i<k&&n-i+1<k){
            tmp=(a[i]-1)*(i-1)-s1[i]+s2[i]-(a[i]+1)*(n-i)+k-1;
        }
        if(tmp<0)tmp=0;
        ans=min(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}