CF429E Points and Segments（欧拉回路）
发布时间
阅读量：
阅读量
CF429E Points and Segments
给定n 条线段[l_i,r_i] ,然后给这些线段红蓝染色，求最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的绝对值不大于1
首先见到绝对值不大于1我们就容易想到欧拉回路，因为欧拉回路可以用来构造恰好相等，然后通过一些另加的边或者已经有的其他限制就可以构造出绝对值小于等于1，然后考虑先将n条线段离散化，将其转化为左闭右开的形式，然后排序去重，这样每个节点就对应了一种线段覆盖状态，总的点数是O(n)级别的，然后将对应左右端点连边，如果能够欧拉回路那么就相当于是构造图的一个环划分，那么将向右视作红色，向左视作蓝色，那么所有点红蓝被覆盖次数的差应该是0。
但是需要考虑图上有奇度数点的情况，可以发现这样的点的个数一定是偶数，所以我们从左到右x_1->x_2,x_3->x_4...这样连边，可以让所有点的度数变为偶数，这样求解欧拉回路之后，去掉这些边，每个个点最多被删去一种颜色一次，所以绝对值一定小于等于1.
#include<bits/stdc++.h>
#define LL long long
#define V inline void
#define I inline int
#define FOR(i,a,b) for(register int i=a,end##i=b;i<=end##i;++i)
#define REP(i,a,b) for(register int i=a,end##i=b;i>=end##i;--i)
#define go(i,x) for(int i=hed[x];i;i=e[i].pre)
using namespace std;
inline int read()
{
char x='\0';
int fh=1,sum=0;
for(x=getchar();x<'0'||x>'9';x=getchar())if(x=='-')fh=-1;
for(;x>='0'&&x<='9';x=getchar())sum=sum*10+x-'0';
return fh*sum;
}
const int N=2e5+9;
const int M=5e5+9;
int n,l[N],r[N],b[N],bcnt;
int nd[N],ncnt;
struct lian{
int to,pre,id;
bool flag;
}e[M<<1];
int hed[N],lcnt=1;
V jlian(int x,int y,int id)
{
e[++lcnt]={y,hed[x],id};
hed[x]=lcnt;
}
int du[N],es[N],et[N];
bool vis[N];
V dfs(int x)
{
vis[x]=true;
for(int &i=hed[x];i;i=e[i].pre)
{
int to=e[i].to;
if(e[i].flag)continue;
e[i].flag=e[i^1].flag=true;
es[e[i].id]=x,et[e[i].id]=to;
dfs(to);
}
}
int main()
{
n=read();
FOR(i,1,n)
{
l[i]=read(),r[i]=read()+1;
b[++bcnt]=l[i],b[++bcnt]=r[i];
}
sort(b+1,b+bcnt+1);
bcnt=unique(b+1,b+bcnt+1)-b-1;
FOR(i,1,n)
{
l[i]=lower_bound(b+1,b+bcnt+1,l[i])-b;
r[i]=lower_bound(b+1,b+bcnt+1,r[i])-b;
jlian(l[i],r[i],i),jlian(r[i],l[i],i);
du[l[i]]++,du[r[i]]++;
}
FOR(i,1,bcnt)if(du[i]&1)nd[++ncnt]=i;
for(int i=1;i<=ncnt;i+=2)
{
jlian(nd[i],nd[i+1],n+1);
jlian(nd[i+1],nd[i],n+1);
}
FOR(i,1,bcnt)if(!vis[i])dfs(i);
FOR(i,1,n)
{
if(es[i]<et[i])printf("1%c",(i==n)?'\n':' ');
else printf("0%c",(i==n)?'\n':' ');
}
return 0;
}
全部评论 (0)
还没有任何评论哟~