Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 C题题解

首先，我们将题目理解成若\(i\)与\(j\)距离恰好为\(3\)，则不可能\(p_i \equiv p_j \equiv 1 \space or \space 2 (\bmod 3)\)。这就相当于我们要构造一个大小为\([\frac{n + 1}{3}]\)的点集\(A_2\)，用来放所有模3余2的数，再构造一个大小为\([\frac{n + 2}{3}]\)的点集\(A_1\)，用来放所有模3余1的数。需要满足这两个集合交集为空，且若\(i\)与\(j\)距离为\(3\)，则它们不在同一个集合内。

发现距离为\(3\)的点连成的图性质是不好的，唯一好的性质就是：它是二分图。我们不妨大胆地把条件加强为：构造这样的点集\(A_1, A_2\)，使得它们全部再二分图的同一边。

我们把树按深度奇偶染色，不妨设染一种颜色的点数为\(X\)，另一种为\(Y\)，且\(X \leq Y\)。

若\(X \ge [\frac{n + 1}{3}]\)且\(Y \ge [\frac{n + 2}{3}]\)，我们就在\(X\)中任意取\([\frac{n + 1}{3}]\)个点作为\(A_2\)，在\(Y\)中任意取\([\frac{n + 2}{3}]\)个点作为\(A_1\)即可。

否则我们容易证明\(Y \ge [\frac{n + 1}{3}] + [\frac{n + 2}{3}]\)，在\(Y\)中任意找两个集合的点即可。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

template <class T>

void read (T &x) {

	int sgn = 1;

	char ch;

	x = 0;

	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;

	if (ch == '-') ch = getchar(), sgn = -1;

	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';

	x *= sgn;

}

template <class T>

void write (T x) {

	if (x < 0) putchar('-'), write(-x);

	else if (x < 10) putchar(x + '0');

	else write(x / 10), putchar(x % 10 + '0');

}

struct edge {

	int to, nxt;

} tree[N << 1];

int n, col[N], head[N], perm[N], cnt = 0, cnt0 = 0, cnt1 = 0;

void addedge (int u, int v) {

	edge e = {v, head[u]};

	tree[head[u] = cnt++] = e;

} 

void dfs (int u, int fa) {

	for (int i = head[u]; ~i; i = tree[i].nxt) {

		int v = tree[i].to;

		if (v != fa) {

			col[v] = col[u] ^ 1;

			dfs(v, u);

		}

	}

}

int main () {

	read(n);

	for (int i = 1; i <= n; i++) head[i] = -1;

	for (int i = 1; i < n; i++) {

		int u, v;

		read(u), read(v);

		addedge(u, v), addedge(v, u);

	}

	col[1] = 0, dfs(1, 0);

	for (int i = 1; i <= n; i++) {

		if (col[i] == 0) cnt0++;

		else cnt1++;

	}

	if (cnt0 > cnt1) {

		for (int i = 1; i <= n; i++) col[i] ^= 1;

		swap(cnt0, cnt1);

	}

	int bound0 = n / 3, bound1 = (n + 1) / 3, bound2 = (n + 2) / 3;

	if (cnt0 >= bound1 && cnt1 >= bound2) {

		int tot0 = 0, tot1 = 0, tot2 = 0;

		for (int i = 1; i <= n; i++) {

			if (col[i] == 0) {

				if (tot2 >= bound1) perm[i] = 3 * ++tot0;

				else perm[i] = 3 * ++tot2 - 1;

			}

			else {

				if (tot1 >= bound2) perm[i] = 3 * ++tot0;

				else perm[i] = 3 * ++tot1 - 2;

			}

		}

	}

	else {

		int tot0 = 0, tot1 = 0, tot2 = 0;

		for (int i = 1; i <= n; i++) {

			if (col[i] == 0) perm[i] = 3 * ++tot0;

			else {

				if (tot1 < bound2) perm[i] = 3 * ++tot1 - 2;

				else if (tot2 < bound1) perm[i] = 3 * ++tot2 - 1;

				else perm[i] = 3 * ++tot0;

			}

		}

	}

	for (int i = 1; i <= n; i++) write(perm[i]), putchar(' ');

	putchar('\n');

	return 0;

}

巴特西

Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 C题题解

最新文章

热门文章