题解 CF547D 【Mike and Fish】
shadowice1984
2019-02-25 17:39:57
标算是什么数学归纳法+带加删边的欧拉回路……,复杂度是$O(nlogn)$的
这个做法过于硬核了,我们不如来想想亲民一些的乱搞做法(没准是对的?)
(反正这个做法我既不会证也不会叉,欢迎dalao来叉或者来证)
对于x坐标相同的点,我们把这些点**两两配对**,如果剩下点则不管,然后在每一对点之间连一条边
对于y坐标相等的点,我们也把这些点**两两配对**,如果剩下点则不管,然后在每一对点之间连一条边
最后对得到的图进行红蓝染色(其实就是黑白染色)就可以得到我们的方案了
证明也很简单,如果我们红蓝染色成功,那么对于每一个x或者y坐标来讲最多剩下一个红点或者蓝点
~~所以这个算法gg的时候就是我们红蓝染色失败了,也就是说我们连出了奇环……,不知道有没有dalao可以给出一组连出奇环的方案~~
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+10;typedef long long ll;
int v[N];int x[N];int ct;int al[N];int col[N];int n;
int lstu[N];int lstv[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs(int u,int tw)
{col[u]=tw;for(int i=al[u];i;i=x[i])if(col[v[i]]==-1)dfs(v[i],tw^1);}
int main()
{
scanf("%d",&n);for(int i=1;i<=n;i++)col[i]=-1;
for(int i=1,x,y;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(lstu[x]){add(lstu[x],i),add(i,lstu[x]),lstu[x]=0;}else lstu[x]=i;
if(lstv[y]){add(lstv[y],i),add(i,lstv[y]),lstv[y]=0;}else lstv[y]=i;
}for(int i=1;i<=n;i++)if(col[i]==-1)dfs(i,0);
for(int i=1;i<=n;i++)putchar((col[i])?'r':'b');return 0;
}
```