题解：P10441 [JOIST 2024] 乒乓球 / Table Tennis

· · 题解

首先需要先知道竞赛图的一些性质：记 \deg_i 表示第 i 个点的出度，则有结论：

竞赛图的三元环的数量为 \binom n3-\sum\limits_{i=1}^n\binom{\deg_i}2。

证明考虑任意三个点要么构成三元环要么构成传递的关系（A\to B,B\to C,A\to C）。因此考虑容斥，总方案数肯定是 \binom n3 而对每个点 u 从 u 出发任意选择 u 的两个出边，这两个出边连向的点的边指向是无所谓的，无论怎么指都必然形成传递关系，选 u 出发的两个点的方案数显然就是 \binom{\deg_u}2，对所有 u 求和后加上容斥部分，最终可得答案为 \binom n3-\sum\limits_{i=1}^n\binom{\deg_i}2。

然后再考虑 n 个点竞赛图三元环数量最多是多少。因为 \binom{\deg}2 是一个凸函数，因此所有点的 \deg 值越接近最终得到的三元环的数量就越多。简单计算后可得到下面的重要结论：

对 n 个点的竞赛图而言，其三元环数量的最大值为：

  • 若 2\mid n，则答案为 \frac{n(n^2-4)}{24}。
  • 若 2\nmid n，则答案为 \frac{n(n^2-1)}{24}。

然后考虑在此基础上调整，只要找出每次恰好减少一个三元环的调整方法就可以给出构造。找到当前图上两个出度为 d 的点，然后考虑将这两个点之间的边反向，此时两个点的出度必然会分别变为 d-1 和 d+1，简单计算后可得这样三元环将减少的数量恰好为 \binom{d+1}2+\binom{d-1}2-2\binom d2=1。然后容易发现如果不存在这样的两个点，则此时竞赛图必然形如一张 dag，此时不存在任何三元环。因此容易证明上述调整策略的正确性。

但是真的一个一个调整过去显然时间复杂度爆炸了，考虑优化。记 F(n) 表示所有 n 个点的竞赛图中，三元环数量最多是多少。因为 F(n) 函数有单调性因此考虑二分找出最小的 k 满足 F(k)\ge m 然后只对这 k 个点进行构造，显然此时需要调整的次数不超过 F(k)-F(k-1)\sim O(k^2) 级别。而其余 n-k 个点只需要全部让前 k 个点的边全都连向她们，这 n-k 个点内部的连边也形成一张 dag 的形式就可以保证不会多出任何多余的三元环。此时问题在于如何对一个合法的出度序列构造出一张合法的竞赛图。考虑 Havel-Hakimi 构造：

每次选择剩余出度最小的点 u，设该点的出度为 d，则：

  • 让 u 连向当前其他点中出度最小的 d 个点。
  • 其他所有没有被连的点全部连一条连向 u 点的边，同时这些点的出度减少 1。
  • 删除点 u，并继续递归构造直到所有点都已经被加入图中为止。

容易证明该算法的正确性。因此整个算法的时间复杂度被优化到 O(n^2) 可以通过该题。

namespace lowspeed_song {

mt19937_64 mt(time(0));

inline void init() {
}

inline int F(int n) {
    if (n & 1) return n * (n * n - 1) / 24;
    return n * (n * n - 4) / 24;
}

int vis[N], cnt[N], ord[N], buc[N], pre[N];

char mp[5010][5010];

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n, m; cin >> n >> m;
    if (m > F(n)) { cout << "No\n" ; return; }
    for (int i = 0; i <= n + 1; ++i) vis[i] = cnt[i] = 0;
    int k = 1; while (F(k) < m) ++k;
    int o = k * (k - 1) / 2 - k * ((k - 1) / 2);
    cnt[(k - 1) / 2] = k - o, cnt[(k + 1) / 2] = o;
    stack<int> stk;
    for (int i = 0; i < k; ++i)
        if (cnt[i] > 1) vis[i] = 1, stk.emplace(i);
    for (int i = 0; i < F(k) - m; ++i) {
        int o = stk.top(); stk.pop(), vis[o] = 0;
        cnt[o] -= 2, ++cnt[o - 1], ++cnt[o + 1];
        for (int j : {o - 1, o, o + 1})
            if (cnt[j] > 1 && !vis[j]) vis[j] = 1, stk.emplace(j);
    } vector<int> deg = {0};
    for (int i = 0; i < k; ++i) while (cnt[i]--) deg.emplace_back(i);
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < i - 1; ++j)
            if (i <= k) mp[i][j] = '0';
            else mp[i][j] = '1';
    } for (int i = k; i > 1; --i) {
        for (int j = 0; j <= i + 1; ++j) buc[j] = 0;
        for (int j = 1; j <= k; ++j) if (deg[j] >= 0) ++buc[deg[j]];
        pre[0] = 0; for (int j = 1; j <= k; ++j) pre[j] = pre[j - 1] + buc[j - 1];
        for (int j = 1; j <= k; ++j) if (deg[j] >= 0) ord[++pre[deg[j]]] = j;
        for (int j = 2; j <= i; ++j) {
            if (ord[1] > ord[j]) {
                if (j <= deg[ord[1]] + 1) mp[ord[1]][ord[j] - 1] = '1';
                else mp[ord[1]][ord[j] - 1] = '0', --deg[ord[j]];
            } else {
                if (j <= deg[ord[1]] + 1) mp[ord[j]][ord[1] - 1] = '0';
                else mp[ord[j]][ord[1] - 1] = '1', --deg[ord[j]];
            }
        } deg[ord[1]] = -1; 
    } cout << "Yes\n";
    for (int i = 2; i <= n; ++i, cout << '\n')
        for (int j = 0; j < i - 1; ++j) cout << mp[i][j];
}

} // namespace lowspeed_song