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; }

總結

以上是生活随笔為你收集整理的CF429E Points and Segments（欧拉回路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。