这题很奇怪啊，思路没问题但是自己写的有问题
碰到大数据总是T，也不知道错在哪里（也许是爆栈了？）
从小到大枚举答案k
那么所有连接的边至少是2^k的倍数
这种模型可以想到欧拉回路；
图上2^k个点，对应权值是[0..2^k-1]，每个大珠子看成一条边，u,v就是小珠子%2^k后的值
图建起来后判一下是否是欧拉回路就行
/* 从小到大枚举答案k 那么所有连接的边至少是2^k的倍数 这种模型可以想到欧拉回路； 图上2^k个点，对应权值是[0..2^k-1]，每个大珠子看成一条边，u,v就是小珠子%2^k后的值 图建起来后判一下是否是欧拉回路就行 */ #include<bits/stdc++.h> using namespace std; #define N 2400005 int n,a[N],b[N]; struct Edge{ int to,nxt,id; }e[N]; int head[N],tot,vis[N],d[N],vv[N]; vector<int>ans,last; void init(int k){ ans.clear(); for(int i=0;i<(1<<k);i++)d[i]=vv[i]=0; tot=0; memset(head,-1,sizeof head); } void add(int u,int v){ e[tot].to=v;e[tot].nxt=head[u];vis[tot]=0; head[u]=tot++; } void dfs1(int u){ vv[u]=1; for(int i=head[u];i!=-1;i=e[i].nxt)if(!vv[e[i].to])dfs1(e[i].to); } void dfs(int u){ //if(n==5e5)cout<<u<<" "; for(int i=head[u];i!=-1;i=e[i].nxt){ if(vis[i])continue; vis[i]=vis[i^1]=1; int v=e[i].to; --d[v];--d[u]; dfs(v); ans.push_back(i^1); } } int judge(int k){ //if(n==5e5)cout<<k<<‘\n‘; init(k); int s=-1; for(int i=1;i<=n;i++){ int mask=(1<<k)-1; int u=a[i]&mask,v=b[i]&mask; add(u,v);add(v,u); d[u]++;d[v]++; } for(int i=0;i<(1<<k);i++)if(s<0 && d[i]){s=i;break;} for(int i=0;i<(1<<k);i++)if(d[i]%2)return 0; dfs1(s); for(int i=0;i<(1<<k);i++)if(vv[i]==0 && d[i]!=0)return 0; dfs(s); return 1; } int main(){ //freopen("1.txt","w",stdout); cin>>n; for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]); /* n=5e5; a[1]=1048575;b[1]=0; for(int i=2;i<=n;i++)a[i]=i*2-1,b[i]=i*2; */ int k=0,L=1,R=20,mid; for(int mid=L;mid<=R;mid++){ if(judge(mid)){ k=mid; last=ans,ans.clear(); } if(n==5e5){ //cout<<k<<\n; } } if(k==0){ cout<<0<<‘\n‘; for(int i=1;i<=n;i++)printf("%d %d ",i*2-1,i*2); return 0; } cout<<min(20,k)<<‘\n‘; for(auto x:last){ printf("%d %d ",x+1,(x^1)+1); } }
ac代码
#include<bits/stdc++.h> using namespace std; #define F(i,a,b) for(int i=a;i<=(b);++i) #define F2(i,a,b) for(int i=a;i<(b);++i) #define dF(i,a,b) for(int i=a;i>=(b);--i) #define debug(...) fprintf(stderr,__VA_ARGS__) #define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) #define MN 1048583 #define MM 1000005 #define ll long long #define mod 998244353 #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3f typedef pair<int,int> pii; #define pb push_back #define mkp make_pair #define fi first #define se second int n,v; int a[MN],b[MN],d[MN],vis[MN]; int h[MN],nxt[MM],to[MM],ve[MM],tot; inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;ve[tot]=0;h[x]=tot;} void dfs(int u){ vis[u]=1; for(int i=h[u];i;i=nxt[i])if(!vis[to[i]])dfs(to[i]); } int stk[MN],tp; void eul(int u){ if(n==5e5)cout<<u<<" "; for(int &i=h[u];i;i=nxt[i]){ if(ve[i])continue; ve[i]=ve[i^1]=1; int e=i^1; eul(to[i]); stk[++tp]=e; } } int main(){ v=1<<20,tot=1; scanf("%d",&n); F(i,1,n)scanf("%d%d",a+i,b+i); int ans=-1; n=5e5; a[1]=1048575;b[1]=0; for(int i=2;i<=n;i++)a[i]=i*2-1,b[i]=i*2; F(j,1,20){ // printf("j=%d\n",j); int x=(1<<j)-1; F(i,1,n)ins(a[i]&x,b[i]&x),ins(b[i]&x,a[i]&x),++d[a[i]&x],++d[b[i]&x]/*,printf("%d--%d\n",a[i]&x,b[i]&x)*/; int gg=0; F2(i,0,v)if(d[i]&1)gg=1; if(!gg){ F2(i,0,v)if(d[i]&&!vis[i]){dfs(i);break;} F2(i,0,v)if(d[i]&&!vis[i])gg=1; } if(gg){ ans=j-1; break; } tp=0; F2(i,0,v)if(d[i]){eul(i);break;} // F(i,1,tp)printf("%d,",stk[i]);puts(""); F2(i,0,v)vis[i]=h[i]=d[i]=0; tot=1; } if(ans==-1)ans=20; printf("%d\n",ans); F(i,1,n)printf("%d %d ",stk[i]-1,(stk[i]^1)-1); return 0; }
原文：https://www.cnblogs.com/zsben991126/p/13049257.html
