• A. Johnny and Contribution
• B. Johnny and His Hobbies
• C. Johnny and Megan's Necklace

https://codeforces.com/contest/1361 (opens new window)

A. Johnny and Contribution

题面看不懂系列。

给定一个无向图，要求给所有点标上号（topic number）并且规则是，对于选中的那个点，它的标号为没在邻居的标号中出现的最小正整数（忽略暂时没标号的邻居）。问最终能不能让每个点的标号依次为 $t_1,t_2,...,t_n$，能的话要给出标号顺序。

贪心贪心贪心，每个点按照 $t$ 值从小到大进行操作即可。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=500010; typedef long long ll; const int inf=~0u>>2; 
vector<int> a[N];
struct node{int t,p;}w[N];
int lab[N];
int n,m;
vector<int> v;
int mex(int x){ //返回邻居中没有出现过的最小的正整数
    v.clear();
    for(auto p:a[x])
    if(lab[p])
        v.push_back(lab[p]);
    sort(v.begin(),v.end());
    unique(v.begin(),v.end());
    repeat(i,0,v.size())
    if(v[i]!=i+1)
        return i+1;
    return v.size()+1;
}
signed main(){
    cin>>n>>m;
    while(m--){
        int x,y; cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    repeat(i,0,n){
        cin>>w[i].t;
        w[i].p=i+1;
    }
    sort(w,w+n,[](node a,node b){return a.t<b.t;});
    repeat(i,0,n){
        int t=mex(w[i].p);
        if(t!=w[i].t)
            cout<<-1<<endl,exit(0);
        lab[w[i].p]=w[i].t;
    }
    repeat(i,0,n)cout<<w[i].p<<' ';
    return 0;
}

B. Johnny and His Hobbies

这波啊，这波是贪心贪心贪心 qwqqqqq。

第一步排除 $p=1$ 的情况（直接输出 $n\%2$）。

从大到小遍历 $p^{k_i}$，对于某个 $p^{k_i}$，如果 $difference$ 大于 0 就减去 $p^{k_i}$，否则加上。这么搞就是最优解辣。

• 当然 $difference$ 这么大肯定是不能直接算的。方法可能不唯一，我就介绍我的思路。由于 $difference$ 可以被好多 $p$ 整除，我们把 $difference$ 写成 $a\cdot p^b$ 的形式（其中 $b$ 等于当前访问的 $k_i$）。然后我们发现，如果 $a$ 大于 1e6，或者小于 -1e6，那么后续的操作都不可能使 $a$ 从正变零，或者从负变零。所以 $a$ 大于 1e6 就把它赋值为 1e6，小于 -1e6 就赋值为 -1e6 就行了，这波操作可以防止 $a$ 超 long long 范围。
• 至于为什么是贪心呢，因为在贪心的过程中，不可能出现加/减一个数导致 $difference$ 符号改变的情况（必须经过 0），所以贪，就硬贪。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define fi first
#define se second
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
typedef long long ll;
#define int ll
const int N=1000010; const int inf=~0u>>2; 
const int mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
int a[N];
int T,n,p;
int ans,dif,nowpos; //dif是题解里的a，nowpos就是题解里的b
void move_to(int x){ //一波操作使nowpos变成x
    (ans*=qpow(p,nowpos-x))%=mod;
    if(dif){
        repeat(i,0,nowpos-x){
            dif=max(min(dif*p,N),-N);
            if(abs(dif)==N)break;
        }
    }
    nowpos=x;
}
void push(int x){ //处理p^x这个数，更新答案
    move_to(x);
    if(dif>0)ans--,dif--;
    else ans++,dif++;
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>p;
        repeat(i,0,n)
            cin>>a[i];
        if(p==1){cout<<n%2<<endl; continue;}
        sort(a,a+n,greater<int>());
        ans=dif=0; nowpos=N;
        repeat(i,0,n)
            push(a[i]);
        move_to(0);
        cout<<(ans%mod+mod)%mod<<endl;
    }
    return 0;
}

C. Johnny and Megan's Necklace

我们发现答案的第一行（记作 $k$），其实只有 21 种情况（0 到 20），所以就从小到大搞一搞。

既然我们固定了 $k$，那么我们就能用并查集快速算出哪些珍珠（pearl）是可以互相连接在一起的。我们把这样的珍珠集合看作顶点，把胶水（glue）看成边，那么求项链实际上就是求这个图的欧拉回路。

• 欧拉回路是否存在取决于：是否连通并且所有顶点的度为偶数。
• 求欧拉路径实际上就是求 dfs 退出序，要学欧拉路径的话不要看我代码学，因为我也几乎看不懂我在写些什么了。
• 那么，怎么用并查集处理哪些珍珠是可以连接的呢？一种方法是对后 k 位数进行排序然后相邻的进行判断。这个方法的复杂度比较大。事实上，如果对每个珍珠的二进制数进行颠倒，比如 1011 颠倒为 110100000...0（总共 20 位），这么做后只要一次排序就行了。而且并查集也不用每次都初始化，美滋滋（虽然我的代码还是 2448ms，好慢啊，自带大常数）。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define fi first
#define se second
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=1000010;
int T,n,p;
struct DSU{
    int a[N],sz[N];
    void init(int n){
        iota(a,a+n+1,0);
        fill(sz,sz+n+1,1);
    }
    int fa(int x){
        return a[x]==x?x:a[x]=fa(a[x]);
    }
    bool query(int x,int y){ //查找
        return fa(x)==fa(y);
    }
    void join(int x,int y){ //合并
        x=fa(x),y=fa(y);
        if(x==y)return;
        if(sz[x]>sz[y])swap(x,y);
        a[x]=y;
        sz[y]+=sz[x];
    }
}d,d2; //d维护了题解里的那个概念，d2维护了是否为连通图
struct node{int x,p;}a[N];
string s;

namespace getans{
vector<int> a[N];
typedef pair<int,int> pii;
vector<pii> ans;
bool vis[N];
void dfs(int i){ //dfs求欧拉回路
    while(!a[i].empty()){
        int x=a[i].back(),y=x^1,p=x/2;
        a[i].pop_back();
        if(vis[p])continue; vis[p]=1; 
        dfs(d.fa(y));
        ans.push_back({x+1,y+1});
    }
}
void getans(){ //输出答案
    repeat(i,0,n){
        int x=i*2,y=i*2+1;
        a[d.fa(x)].push_back(x);
        a[d.fa(y)].push_back(y);
    }
    dfs(d.fa(0));
    repeat_back(i,0,ans.size())cout<<ans[i].fi<<' '<<ans[i].se<<' ';
}
}

signed main(){
    cin>>n;
    repeat(i,0,n*2){
        cin>>a[i].x; s=bitset<20>(a[i].x).to_string();
        reverse(s.begin(),s.end());
        a[i].x=bitset<20>(s).to_ulong();
        a[i].p=i;
    }
    d.init(n*2);
    d2.init(n*2);
    sort(a,a+n*2,[](node a,node b){return a.x<b.x;});
    repeat(i,0,n)d2.join(i*2,i*2+1);
    
    repeat(k,0,21){
        repeat(i,0,n*2-1){
            if((a[i].x>>k)==(a[i+1].x>>k))
                d.join(a[i].p,a[i+1].p),
                d2.join(a[i].p,a[i+1].p);
        }
        int f=true;
        if(d2.sz[d2.fa(0)]!=n*2)f=false;
        repeat(i,0,n*2)
            if(d.sz[d.fa(i)]%2==1)f=false;
        if(f){
            cout<<20-k<<endl;
            getans::getans();
            break;
        }
    }
    return 0;
}