Codeforces Round #629 (Div. 3) 总结

废话

前期题过得还是有点慢

题解

A

直接数出余数的补就好

#include <bits/stdc++.h>
using namespace std;

int a,b,t;

signed main() {
    cin>>t;
    while(t--) {
        cin>>a>>b;
        cout<<(b-a%b)%b<<endl;
    }
}

B

给这些串分个类，很容易发现没类的个数依次是 (1,2,3,dots)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;

int t,n,k;

signed main() {
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--) {
        cin>>n>>k;
        int pos=1;
        while(k>pos) k-=pos, ++pos;
        ++pos;
        int q=k;
        for(int i=n;i>=1;--i) cout<<((i==pos||i==q)?'b':'a');
        cout<<endl;
    }
}

C

从第一个 (1) 之后，将所有的数字倒到另一边

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;

char c[N],a[N],b[N];

int t,n;

signed main() {
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--) {
        cin>>n>>c+1;
        int fg=0;
        for(int i=1;i<=n;i++) {
            if(fg==0) {
                if(c[i]=='1') {
                    a[i]='1';
                    b[i]='0';
                    fg=1;
                }
                else if(c[i]=='2') {
                    a[i]='1';
                    b[i]='1';
                }
                else {
                    a[i]='0';
                    b[i]='0';
                }
            }
            else {
                a[i]='0';
                b[i]=c[i];
            }
        }
        for(int i=1;i<=n;i++) cout<<a[i];
        cout<<endl;
        for(int i=1;i<=n;i++) cout<<b[i];
        cout<<endl;
    }
}

D

如果能二分图染色就输出颜色数，否则就输出 (3)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 400005;

int q,n,a[N],c[N],fail;
vector <int> g[N];

void dfs(int p) {
    for(int q:g[p]) {
        if(c[q]) {
            if(c[q]==c[p]) fail=1;
        }
        else {
            c[q]=3-c[p];
            dfs(q);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>q;
    while(q--) {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int fg=0;
        for(int i=1;i<n;i++) if(a[i]!=a[i+1]) fg=1;
        if(a[1]!=a[n]) fg=1;
        if(fg==0) {
            cout<<1<<endl;
            for(int i=1;i<=n;i++) cout<<1<<" ";
            cout<<endl;
            continue;
        }
        for(int i=1;i<n;i++) if(a[i]!=a[i+1]) {
            g[i].push_back(i+1);
            g[i+1].push_back(i);
        }
        if(a[1]!=a[n]) {
            g[1].push_back(n);
            g[n].push_back(1);
        }
        fail=0;
        for(int i=1;i<=n;i++) if(c[i]==0) {
            c[i]=1;
            dfs(i);
        }
        if(fail) {
            cout<<3<<endl;
            for(int i=1;i<n;i++) cout<<(i%2)+1<<" ";
            cout<<3<<endl;
        }
        else {
            cout<<2<<endl;
            for(int i=1;i<=n;i++) cout<<c[i]<<" ";
            cout<<endl;
        }
        for(int i=1;i<=n;i++) {
            a[i]=c[i]=0;
            g[i].clear();
        }
    }
}

E

给定一棵有根树，每次询问给定一个点集，问是否存在根到某点的链，使得点集中所有点到链的距离不大于 (1)。

将每次询问的结点按深度排序好，相邻的两个结点 (p,q) 一定满足 (d[p]-d[lca] le 1 or d[q]-d[lca] le 1)，其中 (lca=lca(p,q))

必要性显然，充分性考虑让毛毛虫的茎一直往差值大的那边走即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 200005;

vector <int> g[N];
int n,m,t1,t2,t3,dep[N],fa[N][20];

void dfs(int p) {
    for(int q:g[p]) {
        if(dep[q]) continue;
        dep[q]=dep[p]+1;
        fa[q][0]=p;
        dfs(q);
    }
}

int lca(int p,int q) {
    if(dep[p]<dep[q]) swap(p,q);
    for(int i=18;i>=0;--i) if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
    for(int i=18;i>=0;--i) if(fa[p][i]-fa[q][i]) p=fa[p][i],q=fa[q][i];
    if(p-q) return fa[p][0];
    else return p;
}

bool cmp(const int &p,const int &q) {
    return dep[p]<dep[q];
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        cin>>t1>>t2;
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }
    dep[1]=1;
    dfs(1);
    for(int i=1;i<=18;i++) {
        for(int j=1;j<=n;j++) {
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++) {
        int k;
        cin>>k;
        vector <int> vec;
        for(int j=0;j<k;j++) {
            int t;
            cin>>t;
            vec.push_back(t);
        }
        sort(vec.begin(),vec.end(),cmp);
        int fg=1;
        for(int j=1;j<k;j++) {
            int p=vec[j],q=vec[j-1];
            int l=lca(p,q);
            if(dep[p]-dep[l]>1 && dep[q]-dep[l]>1) fg=0;
        }
        cout<<(fg?"YES":"NO")<<endl;
    }
}

F

枚举选择一个中间点，计算把边上压到中间这条线上的答案

压的时候要考虑两边压和单边压的情况

（以下代码中的二分显得很累赘，纯粹为了偷懒而出现）

using namespace std;

#define int long long
const int N = 200005;

int n,k,a[N],pre[N],suf[N],ans=1e18;
map<int,int> mp;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    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=1;i<=n;i++) mp[a[i]]++;
    for(auto i:mp) if(i.second>=k) {
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++) {
        int x=a[i];
        int e=upper_bound(a+1,a+n+1,x)-lower_bound(a+1,a+n+1,x);
        int g=n-(upper_bound(a+1,a+n+1,x)-a)+1;
        int l=lower_bound(a+1,a+n+1,x)-a-1;
        int sg=suf[n-g+1];
        int sl=pre[l];
        int tmp=sg-g*x+l*x-sl-(n-k);
        ans=min(ans,tmp);
        if(n-l>=k) {
            int tx=sg-g*x-(n-l-k);
            ans=min(ans,tx);
        }
        if(n-g>=k) {
            int tx=l*x-sl-(n-g-k);
            ans=min(ans,tx);
        }
        //cout<<l<<" "<<e<<" "<<g<<endl;
    }
    cout<<max(0ll,ans);
}