自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:38:02，当前版本为作者最后更新于2023-11-03 16:31:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 染色使得……相等 / 绝对值之差 $\leq 1$ 等问题可以考虑欧拉回路。

首先可以根据挡板的到达关系建图：

• 设 $i$ 表示挡板 $i$ 朝下的一面，$i'$ 表示挡板 $i$ 朝上的一面。
• 我们建出的图由若干环和链构成。
• 我们的目标是给挡板染为四种颜色，令 $i, i'$ 的颜色为挡板 $i$ 的颜色，则我们希望每个环内每一种颜色的点的个数相同且为偶数。

若存在一个环的长度 $\bmod \ 8 \neq 0$，一定无解。

否则，我们来尝试构造一种方案。能染成四种颜色的必要条件为能染成两种颜色，于是我们先来考虑两种颜色怎么做。

直接在这张图上操作十分困难，考虑点边互化：我们尝试将一个挡板转化成一条边，边的颜色为挡板的颜色。

那么点是什么呢？注意到我们关心的是环内的颜色，考虑把环转化为点，则我们可以在一个挡板的两面所属的两个环对应的点间连边（这里我们先假定原图各连通块全都是环），则问题变为：

• 给定一张无向图。
• 给边黑白染色，使得每个点的出边中黑白颜色相等。

考虑给边定向，设黑边指向当前点、白边从当前点出发，则目标变为让每个点出入度相等。

“出入度相等”让我们想到有向图存在欧拉回路的判断条件，则我们直接在原无向图上跑出一条欧拉回路，对回路上的边黑白染色即可。

由于一个环对应点的度数为环上点数，则一定有解。

接下来考虑染成四种颜色怎么做。我们首先跑一遍两种颜色的情况，注意到把两种颜色的边各自构成的子图中每个点的度数分别 $\bmod \ 4 = 0$，于是在两个子图中各自再跑一遍欧拉回路黑白染色即可。

最后来考虑有连通块为链的情况。我们期待可以将其视作环处理，考虑建一个超级源点，钦定这些链上的点全部属于超级源点对应的环。若超级源点的度数 $\bmod \ 8 \neq 0$，我们强行连一些自环即可。

对 $x, y$ 两维分别排序即可建出最初的图。时间复杂度为 $O(n \log n)$。

代码：

#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct {
	int id;
	int type;
	int x;
	int y;
} Point;

typedef struct {
	int nxt;
	int end;
} Edge;

typedef struct {
	int cnt = 0;
	int head[1000007];
	int deg[1000007];
	Edge edge[2000007];
	
	inline void add_edge(int start, int end){
		cnt++;
		edge[cnt].nxt = head[start];
		head[start] = cnt;
		edge[cnt].end = end;
		deg[start]++;
	}
} Graph;

int top, loop = 0, op;
Graph g1, g2;
int stk[1000007], belong[1000007], cur_edge[1000007], color[500007], ans[500007];
bool vis1[1000007], vis2[1000007], vis3[1000007];
Point point[500007];

inline void init(int n, int m){
	op = 0;
	for (register int i = 0; i <= n; i++){
		cur_edge[i] = g2.head[i];
		vis2[i] = false;
	}
	for (register int i = 1; i <= m; i++){
		vis3[i] = false;
	}
}

inline int read(){
	int sign = 1, ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') sign = -sign;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return sign * ans;
}

inline int get_type(){
	char ch;
	do {
		ch = getchar();
	} while (ch != '/' && ch != '\\');
	return ch == '/' ? 0 : 1;
}

bool cmp1(const Point a, const Point b){
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool cmp2(const Point a, const Point b){
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

void dfs1(int u, int father){
	if (vis1[u]){
		loop++;
		while (top > 0){
			belong[stk[top--]] = loop;
		}
		return;
	}
	vis1[u] = true;
	stk[++top] = u;
	for (register int i = g1.head[u]; i != 0; i = g1.edge[i].nxt){
		int x = g1.edge[i].end;
		if (x != father) dfs1(x, u);
	}
}

void dfs2(int u){
	vis2[u] = true;
	for (register int i = cur_edge[u]; i != 0; i = g2.edge[cur_edge[u]].nxt){
		int id = (i + 1) / 2;
		cur_edge[u] = i;
		if (!vis3[id]){
			vis3[id] = true;
			dfs2(g2.edge[i].end);
			color[id] = op;
			op ^= 1;
		}
	}
}

void dfs3(int u, int goal){
	vis2[u] = true;
	for (register int i = cur_edge[u]; i != 0; i = g2.edge[cur_edge[u]].nxt){
		int id = (i + 1) / 2;
		cur_edge[u] = i;
		if (color[id] == goal && !vis3[id]){
			vis3[id] = true;
			dfs3(g2.edge[i].end, goal);
			ans[id] = ((goal << 1) | op) + 1;
			op ^= 1;
		}
	}
}

int main(){
	int n = read(), m = n * 2;
	for (register int i = 1; i <= n; i++){
		point[i].x = read();
		point[i].y = read();
		point[i].type = get_type();
		point[i].id = i;
	}
	sort(point + 1, point + n + 1, cmp1);
	for (register int i = 1; i <= n; ){
		int nxt = i;
		while (nxt < n && point[i].x == point[nxt + 1].x) nxt++;
		for (register int j = i; j < nxt; j++){
			g1.add_edge(point[j].id + n, point[j + 1].id);
			g1.add_edge(point[j + 1].id, point[j].id + n);
		}
		i = nxt + 1;
	}
	sort(point + 1, point + n + 1, cmp2);
	for (register int i = 1; i <= n; ){
		int nxt = i;
		while (nxt < n && point[i].y == point[nxt + 1].y) nxt++;
		for (register int j = i; j < nxt; j++){
			if (point[j].type == 0){
				if (point[j + 1].type == 0){
					g1.add_edge(point[j].id, point[j + 1].id + n);
					g1.add_edge(point[j + 1].id + n, point[j].id);
				} else {
					g1.add_edge(point[j].id, point[j + 1].id);
					g1.add_edge(point[j + 1].id, point[j].id);	
				}
			} else if (point[j + 1].type == 0){
				g1.add_edge(point[j].id + n, point[j + 1].id + n);
				g1.add_edge(point[j + 1].id + n, point[j].id + n);
			} else {
				g1.add_edge(point[j].id + n, point[j + 1].id);
				g1.add_edge(point[j + 1].id, point[j].id + n);
			}
		}
		i = nxt + 1;
	}
	for (register int i = 1; i <= m; i++){
		if (!vis1[i]){
			top = 0;
			dfs1(i, 0);
		}
	}
	for (register int i = 1; i <= n; i++){
		g2.add_edge(belong[i], belong[i + n]);
		g2.add_edge(belong[i + n], belong[i]);
	}
	for (register int i = 1; i <= loop; i++){
		if (g2.deg[i] % 8 != 0){
			printf("-1");
			return 0;
		}
	}
	while (g2.deg[0] % 8 != 0) g2.add_edge(0, 0);
	init(loop, n);
	for (register int i = 0; i <= loop; i++){
		if (!vis2[i]) dfs2(i);
	}
	init(loop, n);
	for (register int i = 0; i <= loop; i++){
		if (!vis2[i]) dfs3(i, 0);
	}
	init(loop, n);
	for (register int i = 0; i <= loop; i++){
		if (!vis2[i]) dfs3(i, 1);
	}
	for (register int i = 1; i <= n; i++){
		printf("%d ", ans[i]);
	}
	return 0;
}