http://www.elijahqi.win/archives/3932 大家都知道，熊爱鱼。但是迈克是一只奇怪的熊，他讨厌鱼！更奇怪的是，他有无数的蓝色和红色的鱼。 他在平面上标出了 n n 个不同的点。第 ii 个是点 (xi,yi) ( x i , y i ) 。他想在每一点都放一条鱼，使得每一条水平线或垂直线上的红鱼和蓝鱼的数量相差最多1。 他不能找到一种方式来执行，所以请你帮助他。 输入的第一行包含整数 n(1≤n≤2×105) n ( 1 ≤ n ≤ 2 × 10 5 ) 。 接下来的 n n 行包含的每个点的信息，第 ii 行包含两个整数 xi x i 和 yi y i ,（ 1≤xi,yi≤2×105 1 ≤ x i , y i ≤ 2 × 10 5 ），表示第 i i 个点的坐标。 保证至少有一个符合题意的答案。 将答案输出为n个字符r（红色）或b（蓝色）的序列，其中第 ii 个字符表示 i i <script type="math/tex" id="MathJax-Element-36">i</script> 点中的“鱼”的颜色。
我们考虑把每一排每一列分别看成一个点 然后我们每个点就是勾连起这样两个点的一个桥梁
要求给这些点染色 使得一行一列内不同颜色的差的绝对值小于等于1
把不同颜色看成针对这个点不同的出边或者入边
那么欧拉图的性质就是入度和出度是相等的 但是有可能出现度数是奇数的情况 不妨我们两两给他们配对起来这样跑一遍欧拉图 最后把那些多余的边删除即可 强行钦定 边的方向为什么颜色即可
这题如果不加“类似当前弧优化” 是tle的
#include<bits/stdc++.h> using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int N=8e5+10; struct node{ int y,next,x; }data[N<<2]; int q1[N],q2[N],n1,n2,num=1,in[N],x[N],y[N],n,h[N]; bool visit[N],vis[N];int q[N<<1],top;char s[N]; inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].x=x; } inline void dfs(int x){ vis[x]=1; for (int &i=h[x];i;i=data[i].next){ int id=i; int y=data[i].y;if (visit[i]||visit[i^1]) continue; visit[i]=visit[i^1]=1;dfs(y);q[++top]=id; } } int main(){ freopen("cf.in","r",stdin); double t1=clock(); n=read(); for (int i=1;i<=n;++i) x[i]=read(),y[i]=read(),q1[++n1]=x[i],q2[++n2]=y[i]; sort(q1+1,q1+n1+1);sort(q2+1,q2+n2+1); n1=unique(q1+1,q1+n1+1)-q1-1;n2=unique(q2+1,q2+n2+1)-q2-1; for (int i=1;i<=n;++i) x[i]=lower_bound(q1+1,q1+n1+1,x[i])-q1, y[i]=lower_bound(q2+1,q2+n2+1,y[i])-q2,y[i]+=n1; for (int i=1;i<=n;++i) insert1(x[i],y[i]),insert1(y[i],x[i]),++in[x[i]],++in[y[i]]; int nm=num,last=-1; //for (int i=2;i<=nm;++i) printf("%d %d\n",data[i].x,data[i].y); for (int i=1;i<=n1+n2;++i){ if (in[i]&1){ if (last==-1){ last=i;continue; } insert1(last,i);insert1(i,last);last=-1; } } double t2=clock();if((t2-t1)/CLOCKS_PER_SEC>1) printf("%f\n",(t2-t1)/CLOCKS_PER_SEC); for (int i=1;i<=n1+n2;++i) if (!vis[i]) dfs(i); for (int i=1;i<=top;++i){ if (q[i]>nm) continue; int id=q[i];(id&1)?s[id>>1]='b':s[id>>1]='r'; }printf("%s",s+1); return 0; }