题解 CF547D 【Mike and Fish】

shadowice1984

2019-02-25 17:39:57

Solution

标算是什么数学归纳法+带加删边的欧拉回路……,复杂度是$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; } ```