题解 | D-Points Construction Problem

https://www.cnblogs.com/zrzring/p/NC55994D.html

将图上恰好 $nn$ 个点染成黑色，使得图上相邻的黑白点对数量恰好为 $mm$

考虑 $nn$ 个黑点如果不相邻，则两个点的贡献互不影响

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

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

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

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

且在上述过程中，我们不难发现贡献一直都为偶数，则 $mm$ 为奇数的时候一定输出 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;
}