题解：CF850D Tournament Construction

Felix72 · 2025-11-19 15:13:13 · 题解

考察兰道定理的证明。

首先由题目知兰道定理是充要条件，则直接 \text{DP} 出符合定理要求的得分序列即可。观察 f(x) = {x \choose 2} 和 g(x) = 30x 的增长速度可知最大的 n 在 60 左右，该部分复杂度为 O(n^2mA)，其中 A = \max\{a\}。

然后构造一个竞赛图。先令 i \to j 存在当且仅当 i > j，此时我们将得到得分序列 t。设最终得分序列需要为 s（已排序），则使用如下调整法构造：

• 找到最小的 t_p，使得 t_p < s_p。若有多个，找 p 最大的那一个；
• 找到 p 后面的最小 q，使得 t_q > s_q。
• 此时 t_p 和 t_q 差值至少是 2，则一定有点 x 满足路径 q \to x \to p 存在（否则差值最大是 1），反转这条路径，有 t_p \larr t_p + 1, t_q \larr t_q - 1；
• 结合兰道定理的必要性知最开始 t 的前缀和数组达到下界，且整个过程中 t 的前缀和数组的每个位置不大于 s 的对应位置，因此总能找到 p, q, x。这便是兰道定理充分性的证明。

/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 65;
int m, a[N], n, s[N], t[N]; bool dp[35][N][N * 35], mp[N][N];
inline bool check(int n, int sum) {return (sum >= n * (n - 1) / 2);}
inline void flip(int x, int y) {mp[x][y] ^= 1, mp[y][x] ^= 1;}
inline void take(int ID, int remain, int val)
{
    if(!ID && !remain && !val) return ;
    if(val >= a[ID] && dp[ID][remain - 1][val - a[ID]])
        take(ID, remain - 1, val - a[ID]), s[++n] = a[ID];
    else if(val >= a[ID] && dp[ID - 1][remain - 1][val - a[ID]])
        take(ID - 1, remain - 1, val - a[ID]), s[++n] = a[ID];
    else assert(0);
}
inline bool judge()
{
    for(int i = 1; i <= n; ++i) if(s[i] != t[i]) return true;
    return false;
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m;
    for(int i = 1; i <= m; ++i) cin >> a[i];
    sort(a + 1, a + m + 1);

    dp[0][0][0] = true;
    for(int i = 0; i <= m; ++i)
    {
        for(int j = 0; j <= 61; ++j)
        {
            for(int k = 0; k <= j * 30; ++k)
            {
                if(i && check(j + 1, k + a[i])) dp[i][j + 1][k + a[i]] |= dp[i][j][k];
                if(check(j + 1, k + a[i + 1])) dp[i + 1][j + 1][k + a[i + 1]] |= dp[i][j][k];
            }
        }
    }
    for(int i = 1; i <= 62; ++i)
    {
        bool flag = false;
        for(int j = 0; j <= i * 30; ++j)
            if(dp[m][i][j] && i * (i - 1) / 2 == j)
                {flag = true; take(m, i, j); break;}
        if(flag) break;
        if(i == 62) {cout << "=(" << '\n'; return 0;}
    }

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            mp[i][j] = true, ++t[i];
    while(judge())
    {
        int p = 0, q = 0;
        for(int i = 1; i <= n; ++i) if(t[i] < s[i]) {p = i; break;}
        while(t[p] == t[p + 1]) ++p;
        for(int i = p + 1; i <= n; ++i) if(t[i] > s[i]) {q = i; break;}
        if(mp[q][p]) flip(p, q), --t[q], ++t[p];
        else
        {
            for(int i = 1; i <= n; ++i)
            {
                if(mp[q][i] && mp[i][p])
                    {flip(q, i), flip(i, p); --t[q], ++t[p]; break;}
            }

        }
    }

    cout << n << '\n';
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
            cout << mp[i][j];
        cout << '\n';
    }
    return 0;
}
/*

*/