shadowice1984 的博客

shadowice1984 的博客

题解 CF547D 【Mike and Fish】

posted on 2019-02-25 17:39:57 | under 题解 |

标算是什么数学归纳法+带加删边的欧拉回路……,复杂度是$O(nlogn)$的

这个做法过于硬核了,我们不如来想想亲民一些的乱搞做法(没准是对的?)

(反正这个做法我既不会证也不会叉,欢迎dalao来叉或者来证)

对于x坐标相同的点,我们把这些点两两配对,如果剩下点则不管,然后在每一对点之间连一条边

对于y坐标相等的点,我们也把这些点两两配对,如果剩下点则不管,然后在每一对点之间连一条边

最后对得到的图进行红蓝染色(其实就是黑白染色)就可以得到我们的方案了

证明也很简单,如果我们红蓝染色成功,那么对于每一个x或者y坐标来讲最多剩下一个红点或者蓝点

所以这个算法gg的时候就是我们红蓝染色失败了,也就是说我们连出了奇环……,不知道有没有dalao可以给出一组连出奇环的方案

上代码~

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