CF547D Mike and Fish

IOI2020集训队作业

为什么CF题会有一些奇怪的插图?

Orz

给定 $n$ 个整点。
你要给每个点染成红色或蓝色。
要求同一水平线或垂直线上两种颜色的数量最多相差 $1$ 。
$n,x_i, y_i \le 2 \times 10^5$ 。

一眼看上去真的很难判断是什么算法,如果是DP的话,那我们要记的状态可能有点复杂?

如果是贪心暴力的话...后效性?而且染色不一定有最优的啊

另外还要输出方案,好像图论算法就很不错?

先考虑建图,由网络流24题不难发现我们可以建行点和列点,然后同一行列有点我们就连一条边

边的方向?会不会就是点的颜色呢??/jk

如果就是点的颜色,我们就是要给每条边定向了,之前做的边定向题好像都转化成欧拉回路了!

那么我们这个题也可以,因为如果一个点是奇度数点,入度出度差1!是偶度数点则入度出度相等

而我们要欧拉回路还需要再建一个虚拟点,然后所有奇度数点向他连边.....不难发现他的度数一定是偶数

这样就做完了///

code:

#include<iostream>
#include<cstdio>
#include<cstring>
const int MAXN = 1e6 + 7;
int n, m;
int ccnt, home[MAXN], nxt[MAXN], to[MAXN], vis[MAXN], deg[MAXN], res[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = BUF_SIZE + buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	++deg[x];
}

inline void dfs(int u) {
	//printf("%d ", u);
	for(int &i = home[u], e; i; i = nxt[i]) {
		int v = to[i];
		if(!vis[e = i >> 1]) {
            //你会发现这其实是让同一条无向边只被标记一次
            //比如2,3>>1都是1,也就其中一个会被标记
			vis[e] = 1;
			if(e <= n)res[e] = i & 1;
			dfs(to[i]);

		}
	}
}

int main() {
	//freopen("test.in", "r", stdin);
	n = read();
	ccnt = 1;
	//puts("QWQ");
	for(int i = 1, u, v; i <= n; ++i) {
		u = read();
		v = read() + 200000;//这个是列点
		ct(u, v);
		ct(v, u);
	}
	//puts("QAQ");
	for(int i = 1; i <= 400000; ++i)
		if(deg[i] & 1)ct(0, i), ct(i, 0);//虚拟点起效
	for(int i = 1; i <= 400000; ++i) {
		dfs(i); //if(i % 10000 == 0)printf("%d\n", i); //枚举每行每列

	}
	//printf("%d?\n", n);
	for(int i = 1; i <= n; ++i)putchar(res[i] ? 'b' : 'r');
	return 0;
}

金色暗影封面图很快就有的~

夏晓光(loveJY)的博客

P5284 [十二省联考2019]字符串问题