题面
CF https://codeforces.com/problemset/problem/429/E
洛谷 https://www.luogu.org/problemnew/show/CF429E
题解
欧拉回路有这样一个性质, 如果把所有点在平面内排成一行, 路径看成区间的覆盖, 那么每个点被从左往右的覆盖次数等于从右往左的覆盖次数.
发现这题很类似上面这个东西.
将 \(L\) 向 \(R+1\) 连边, 但是不能直接做欧拉回路, 因为图不连通.
找到度数为奇数的所有点, 把相邻的两个两两配对, 然后在他们之间连条边, 然后求解欧拉回路.
因为这样子配对完之后新增的区间不交, 令黑色区间为 \(+1\), 白色区间为 \(-1\), 那么除了相邻两个奇度数点之间的区间外, 其他区间的权值和为 \(0\), 而奇度数之间的区间的绝对值为 \(1\).
那么这个问题就解决完了.
还是注意即是这样子连完了边还可能不连通, 所以每个连通块都要跑一遍.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define MAX 400100
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- int n,L[MAX],R[MAX];
- int S[MAX],top;
- struct Line{int v,next;}e[MAX];
- int h[MAX],cnt=2,dg[MAX];
- inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;dg[v]+=1;}
- int vis[MAX];bool book[MAX];
- void dfs(int u)
- {
- for(int &i=h[u];i;i=e[i].next)
- {
- int v=e[i].v,j=i;if(book[i>>1])continue;
- book[i>>1]=true;dfs(v);vis[j>>1]=u<v;
- }
- }
- int main()
- {
- n=read();
- for(int i=1;i<=n;++i)L[i]=read(),R[i]=read();
- for(int i=1;i<=n;++i)S[++top]=L[i],S[++top]=L[i]-1;
- for(int i=1;i<=n;++i)S[++top]=R[i],S[++top]=R[i]+1;
- sort(&S[1],&S[top+1]);top=unique(&S[1],&S[top+1])-S-1;
- for(int i=1;i<=n;++i)L[i]=lower_bound(&S[1],&S[top+1],L[i])-S;
- for(int i=1;i<=n;++i)R[i]=lower_bound(&S[1],&S[top+1],R[i])-S;
- for(int i=1;i<=n;++i)Add(L[i],R[i]+1),Add(R[i]+1,L[i]);
- for(int i=1,lst=0;i<=top;++i)if(dg[i]&1)lst?Add(i,lst),Add(lst,i),lst=0:lst=i;
- for(int i=2;i<cnt;i+=2)if(!book[i>>1])dfs(e[i].v);
- for(int i=1;i<=n;++i)printf("%d",vis[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2973878.html