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;
}