P10441 [JOISC 2024] 乒乓球 题解

Description

构造一个点数为 $n$ 的竞赛图，满足其中三元环的个数为 $m$。

$n\leq 5000$。

Solution

首先竞赛图的三元环个数是可以根据每个点的入度/出度求的。具体地，设 $deg_i$ 表示 $i$ 的出度，则三元环个数为 $\binom{n}{3}-\sum{\binom{deg_i}{2}}$。

考虑怎么判断有无解。

注意到如果 $deg_i+1<deg_j$，那么让 $deg_i\leftarrow deg_i+1,deg_j\leftarrow deg_j-1$ 一定能让三元环数最多，所以度数越均匀，三元环数就越多。所以三元环最多的情况下 $deg_i$ 一定等于 $\lfloor\frac{n}{2}\rfloor$ 或者 $\lceil\frac{n}{2}\rceil$，于是就能求出最多的三元环数了。

设 $f_n$ 表示 $n$ 个点的图三元环数量的最大值，结论是如果 $m>f_n$ 则无解，否则有解。

构造就考虑先把初始度数设为数量最大时的情况，然后每次选择 $deg_i=deg_j$，让 $deg_i\leftarrow deg_i-1,deg_j\leftarrow deg_j+1$，会让三元环数减一。如果选不出来，就说明 $deg=\{0,1,2,\ldots,n-1\}$，此时三元环数为 $0$，不需要再调整了。

由于每次操作可以看成选两个度数相等的点，将它们之间的边取反，并且初始状态一定能构造，所以最终也可以构造出来。

现在得到了每个点的度数，构造竞赛图就考虑每次选择度数最小的点 $i$，向其余任意 $deg_i$ 个点连从 $i$ 出发的边，剩下的 $n-1-deg_i$ 个点就连到达 $i$ 的边，然后把 $i$ 删掉即可。

但是 $m$ 可能到 $O(n^3)$ 级别，暴力调整度数会超时。注意到 $f(n)-f(n-1)$ 为 $O(n^2)$ 级别，所以只需要选择最小的 $k$ 满足 $f(k)\geq m$，然后构造大小为 $k$ 三元环数为 $m$ 的图，然后对剩余的点连出一个有向无环图即可。

时间复杂度：$O(n^2\log n)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 5e3 + 5;

int n, m;
bool g[kMaxN][kMaxN];

int C(int n) { return 1ll * n * (n - 1) / 2; }

int calc(int n) {
  if (n % 2 == 1) return 1ll * n * (n - 1) * (n - 2) / 6 - 1ll * n * C((n - 1) / 2);
  else {
    int k = (n - 1) / 2, cnt2 = C(n) - k * n, cnt1 = n - cnt2;
    return 1ll * n * (n - 1) * (n - 2) / 6 - (1ll * cnt1 * C(k) + 1ll * cnt2 * C(k + 1));
  }
}

void construct(int n, int m) {
  static int cnt[kMaxN] = {0}, deg[kMaxN];
  std::fill_n(cnt, n - 1, 0);
  if (n % 2 == 1) {
    cnt[(n - 1) / 2] = n;
  } else {
    int k = (n - 1) / 2, cnt2 = C(n) - k * n, cnt1 = n - cnt2;
    cnt[k] = cnt1, cnt[k + 1] = cnt2;
  }
  std::priority_queue<int> q;
  for (int i = 1; i < n - 1; ++i)
    if (cnt[i] >= 2)
      q.emplace(i);
  for (int i = 1; i <= m; ++i) {
    int x = q.top(); q.pop();
    cnt[x] -= 2, ++cnt[x - 1], ++cnt[x + 1];
    if (cnt[x] >= 2) q.emplace(x);
    if (cnt[x - 1] == 2 && x - 1 >= 1) q.emplace(x - 1);
    if (cnt[x + 1] == 2 && x + 1 < n - 1) q.emplace(x + 1);
  }
  int c = 0;
  static int tmp[kMaxN];
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= cnt[i]; ++j)
      deg[++c] = i, tmp[c] = i;
  }
  // std::cerr << n << ' ' << m << " : ";
  // for (int i = 1; i <= n; ++i) std::cerr << deg[i] << " \n"[i == n];
  for (int i = 1; i <= n; ++i) {
    std::vector<int> vec;
    assert(i + deg[i] <= n);
    // std::cerr << i << ' ' << deg[i] << '\n';
    for (int j = i + 1; j <= n; ++j) vec.emplace_back(j);
    std::sort(vec.begin(), vec.end(), [&] (int x, int y) { return deg[x] < deg[y]; });
    for (int j = 0; j < vec.size(); ++j) {
      int x = vec[j];
      if (j < deg[i]) g[i][x] = 1;
      else g[x][i] = 1, --deg[x];
    }
  }
  // for (int i = 1; i <= n; ++i) {
  //   assert(std::count(g[i] + 1, g[i] + 1 + n, 1) == tmp[i]);
  // }
}

void dickdreamer() {
  std::cin >> n >> m;
  if (calc(n) < m) return void(std::cout << "No\n");
  for (int i = 1; i <= n; ++i)
    std::fill_n(g[i] + 1, n, 0);
  for (int k = 0; k <= n; ++k) {
    if (calc(k) >= m) {
      construct(k, calc(k) - m);
      for (int i = 1; i <= n; ++i)
        for (int j = std::max(i + 1, k + 1); j <= n; ++j)
          g[i][j] = 1;
      break;
    }
  }
  std::cout << "Yes\n";
  // int sum = 1ll * n * (n - 1) * (n - 2) / 6;
  // for (int i = 1; i <= n; ++i) sum -= C(std::count(g[i] + 1, g[i] + 1 + n, 1));
  // std::cerr << sum << '\n';
  // for (int i = 1; i <= n; ++i, std::cerr << '\n')
  //   for (int j = 1; j <= n; ++j)
  //     std::cerr << g[i][j];
  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j < i; ++j)
      std::cout << g[i][j];
    std::cout << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}