题目链接:https://www.luogu.com.cn/problem/CF547D
简要题意:
- 平面上有n个整点
- 要求你把整点黑白染色,使得每一行每一列黑色点的个数-白色的个数的绝对值不超过1
构造好题,想半天一点头绪都没有
有以下两种解法:
1.看到黑白染色想到二分图
考虑把每一行之间的点两两随机连边,剩下的点(最多一个)不用管,列之间同理
可以发现我们连的一张二分图,因为每个点最多连一条横向边和一条纵向边,任何一个环都一定是横纵交错的,即不可能出现奇环
所以对二分图黑白染色即可,因为每行最多剩下一个点任选,所以合法.
2.考虑化点为边
把每个点对应的横纵坐标连边
于是问题便成了给定一张无向图,要求给边定向使得每个点入度出度相差不超过1
看到度数,想到欧拉回路,对于每个度数是奇数的点向0连一条边
因为总度数是偶数,所以度数是奇数的店一定是偶数个,所以0的度数也是偶数
跑欧拉回路即可,横->纵,黑,纵->横,白,0可以随便归为横坐标或者纵坐标.(反正这条边不计入答案)
代码写的是第二种
/*Mike and Fish*/ #include<bits/stdc++.h> using namespace std; #define ll long long int read(){ char c = getchar(); int x = 0; while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar(); return x; } const int N = 2e5 + 10; const int M = 1e6 + 10; int head[M],tot; struct Edge{ int nxt,point; }edge[M<<1]; int deg[M]; void add_edge(int u,int v){ edge[++tot].nxt = head[u]; edge[tot].point = v; head[u] = tot; deg[v] ^= 1; } int n; bool used[M]; int c[M]; bool vis[M]; void euler(int u){ vis[u] = 1; for(int &i = head[u]; i ; i = edge[i].nxt){ int v = edge[i].point; if(used[i]) continue; used[i] = used[i^1] = 1; c[i>>1] = (u < N); euler(v); } } int main(){ n = read(); tot = 1; for(int i = 1; i <= n; ++i){ int u = read(),v = read(); add_edge(u,v+N); add_edge(v+N,u); } for(int i = 1; i < 2 * N; ++i) if(deg[i]) add_edge(0,i),add_edge(i,0); for(int i = 1; i < N; ++i){ if(!vis[i]) euler(i); } for(int i = 1; i <= n; ++i) printf("%c",c[i]?'b':'r'); return 0; }