D - Points Construction Problem
D 构造
题意
有一个无限大的白色网格,要求你涂黑 n 个点,构造 m 个异色点对,求这个点序列。
思路
我们将黑点想象成黑色正方形,异色点对数想象成边长。那么这个图可以看成由多个 ”黑色正方形“ 构成的黑色多边形组成。
先考虑上界:由于一个黑色正方形最多有 4 条边,因此 m >= 4n 时无解。留意到,黑色多边形的边长一定是偶数,因此奇数时无解。
再考虑下界:一个 a x b 黑色矩形,最多提供 2 (a + b) 个异色点对。挖掉它的边边角角,由小学数学可知,边长不变。有了这个性质,就很方便了。
我们可以将 n 个点,构造成 a x b 的黑色矩形,然后挖掉它的边边角角,就可以得到 n 个点时,最小异色点对(边长最小)的点序列,记现在矩形的边长为 minM。
然后我们来扩展它的边长:
1、找最右上方的黑色正方形, 记录它邻接的黑色正方形数 p
2、将这个黑色正方形放到无穷远处
3、minM += 2 * p (边长增加那么多)
4、如果当前边长大于 m,则停止扩展,否则继续执行1
当扩展完成后,当前边长有可能比目标边长 m 多 2,因此,我们随便选一个无穷远的黑色正方形,将它放到恰与一个黑色正方形邻接的地方就可以了。
时间复杂度 O(n)
代码
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int DX[] = {-1, 0, 1, 0}; const int DY[] = {0, 1, 0, -1}; set<pii, greater<pii>> ans; int deg(pii p) { int cur = 0; for (int i = 0; i < 4; ++i) cur += ans.count(pii{p.first + DX[i], p.second + DY[i]}); return cur; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t, n, m; cin >> t; while (t--) { ans.clear(); cin >> n >> m; if (m > 4 * n || m % 2) { cout << "No\n"; continue; } int minM = -1, minA, minB; for (int i = 1; i <= n; ++i) { int j = (n + i - 1) / i; if (minM == -1 || 2 * (i + j) < minM) { minA = i; minB = j; minM = 2 * (i + j); } } if (m < minM) { cout << "No\n"; continue; } for (int i = 1; i <= minA && ans.size() != n; ++i) for (int j = 1; j <= minB && ans.size() != n; ++j) ans.emplace(i, j); int gen = 0; while (minM < m) { auto p = *ans.begin(); ans.erase(p); minM += deg(p) * 2; p.first = p.second = --gen; ans.emplace(p); } if (minM != m) { auto p = *ans.rbegin(); ans.erase(p); auto q = *ans.rbegin(); for (int i = 0; i < 4; ++i) { pii p = {q.first + DX[i], q.second + DY[i]}; if (deg(p) == 1) { ans.emplace(p); break; } } } cout << "Yes\n"; for (auto p: ans) { cout << p.first << ' ' << p.second << "\n"; } } return 0; }