Codeforces Round #647 (Div. 1) C - Necklace(欧拉回路+异或性质+虚点+缩点+lambda表达式的写法)_欧拉回路 codeforces

题目

n(n<=5e5)段项链，第i段左端ai右端bi(0<ai,bi<2^20)，

两段项链ij可以拼接在一起，中间产生的值是i的一端u和j的一端v所产生的贡献，

贡献计算方式是最大的k，满足(u^v)%(1<<k)=0，即最大的k满足2的k次方能被u异或v的值整除，

特别的，如果u=v，k被记作20，

要求把i串项链串成一串项链时，链上最小的贡献的最大

输出这个贡献，并输出最终的项链上的珠子是怎么摆放的，第i段左端珠子边号2*i，右端边号2*i+1

思路来源

https://www.cnblogs.com/heyuhhh/p/13051654.html

题解

考虑(u^v)%(1<<k)=0，有u%(1<<k)=v%(1<<k)

由于k最大为20，倒序枚举k，如果项链i一端和项链j一端的%(1<<k)余数相同说明可连，

为了防止连过多边，建完全剩余系虚点[0,(1<<k)-1]，由u连向u%(1<<k)，v连向v%(1<<k)

此外，由于u-v是原项链上的链，必经，所以把第i条项链u-v这一条边缩成一个点i，

为了防止点号冲突，对点i的点号加1<<k处理

这样从原项链走到另一条项链，对应了走向虚点和从虚点出来两条边，

这样建好图之后，要构成一个环，就是访问图上所有边的欧拉回路问题

因为图里的边号都是一个虚点一个实点，实点只有一条边，所以令边号=实点号，这样方便输出实点号

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<set>
#include<algorithm>
#include<functional>
using namespace std;
typedef pair<int,int> P;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sci(x) scanf("%d",&(x))
#define pb push_back
#define fi first
#define se second
const int N=5e5+10;
int n,a[N],b[N];
int main()
{
	scanf("%d",&n);
	rep(i,0,n-1)sci(a[i]),sci(b[i]);
    per(k,20,0){
        int up=1<<k;
        vector<vector<P> > e(up+n);//a[i]-b[i] 看成一个点i 连向对应的只需低k位的虚点
        rep(i,0,n-1){//(u^v)%(1<<k)==0 (u%(1<<k))==(v%(1<<k))
            e[a[i]&(up-1)].pb(P(i+up,2*i));//2*i 既是点号也是边号
            e[i+up].pb(P(a[i]&(up-1),2*i));//为了防止点号冲突 对i加up处理
            e[b[i]&(up-1)].pb(P(i+up,2*i+1));
            e[i+up].pb(P(b[i]&(up-1),2*i+1));
        }
        bool ok=1;
        rep(i,0,up+n-1){//奇度 无解
            if(e[i].size()%2){
                ok=0;
                break;
            }
        }
        if(!ok)continue;
        vector<int> ans;
        vector<bool> vis(2*n);
        function <void(int,int)> dfs=[&](int u,int fa){//lambda表达式
            while(e[u].size()){
                P x=e[u].back();e[u].pop_back();//弧优化
                int v=x.fi,id=x.se;
                if(!vis[id]){
                    vis[id]=1;
                    dfs(v,id);
                }
            }
            if(fa!=-1)ans.pb(fa);//既是当前边号 也是一端的点号
        };
        rep(i,0,up+n-1){
            if(e[i].size()){
                dfs(i,-1);
                break;
            }
        }
        if(ans.size()<2*n)continue;//图不连通 无解
        printf("%d\n",k);
        for(auto x:ans){
            printf("%d ",x+1);
        }
        puts("");
        break;
    }
	return 0;
}