牛客 55994 2023牛客五一集训派对day3 D Points Construction Problem-526互联

D-Points Construction Problem_2023牛客五一集训派对day3 (nowcoder.com)

将图上恰好 \(n\) 个点染成黑色，使得图上相邻的黑白点对数量恰好为 \(m\)

考虑 \(n\) 个黑点如果不相邻，则两个点的贡献互不影响

考虑相邻的情况，我们把相邻的点连边，则贡献为每一个连通块的贡献的和，我们用一个二元组表示一个连通块的大小和贡献 \((x, y)\)

若一个连通块大小为 \(n\)，则其贡献最大为 \(2n + 2\)，如果初始的 \(m > 2n + 2\)，我们可以从中分出一个单独的块 \((1, 4)\)，最后一定会剩余 \((n, m)\) 保证 \(m \leq 2n + 2\)

考虑将剩下的 \((n, m)\) 归为一个连通块，我们可以发现一个结论，如果连通块中每存在一个 \(2\times 2\) 的子矩阵，该连通块的贡献在 \(2n + 2\) 的基础上减 \(2\)，于是我们可以贪心的让 \(2\times 2\) 的子矩阵尽可能多

若剩下的 \((n, m)\) 无法归为一个连通块，即 \(m\) 小于 \(n\) 能提供的贡献的下界，而将其分为更多的连通块，一定比 \(n\) 个点形成一个连通块贡献要多，于是我们只需要判断归为一个连通块是否合法即可

且在上述过程中，我们不难发现贡献一直都为偶数，则 \(m\) 为奇数的时候一定输出 No

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>

#define i64 long long

inline i64 read() {
	bool sym = 0; i64 res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

struct ANS {
	int x, y;
};

int main() {
	int T = read();
	while (T--) {
		int n = read(), m = read(), t = 1, cnt = 0;
		ANS ans[n + 1];
		if (m > 4 * n) {printf("No\n"); continue;}
		if (n == 1 && m == 2) {printf("No\n"); continue;}
		if (m % 2 == 1) {printf("No\n"); continue;}
		while (m > 2 * n + 2) {
			m -= 4; n--; ans[++cnt] = {t, t}; t++;
		}
		int inf = 1000, k = (2 * n + 2 - m) / 2;
		if (!k) {
			printf("Yes\n");
			for (int i = 1; i <= n; i++) ans[++cnt] = {inf + t, inf + t + i - 1};
			for (int i = 1; i <= cnt; i++) printf("%d %d\n", ans[i].x, ans[i].y);
			continue;
		}
		for (int i = 1; n && k; i++) {
			for (int j = 1; n && k && j <= i - 1; j++) {
				if (j != 1) k--; n--;
				ans[++cnt] = {inf + i, inf + j};
			}
			for (int j = 1; n && k && j <= i; j++) {
				if (j != 1) k--; n--;
				ans[++cnt] = {inf + j, inf + i};
			}
		}
		if (k) {printf("No\n"); continue;}
		for (int i = 1; i <= n; i++) ans[++cnt] = {inf + 1, inf - i + 1};
		printf("Yes\n");
		for (int i = 1; i <= cnt; i++) printf("%d %d\n", ans[i].x, ans[i].y);
	}
	return 0;
}

construction problem points 55994