P9890 [ICPC2018 Qingdao R] Tournament

Alex_Wei · 2024-02-09 13:54:15 · 题解

P9890 [ICPC2018 Qingdao R] Tournament

构造好题。

因为任意一组构造在 k 变小时依然适用，所以我们需要对每个 n 找到有解的 k 的最大值。

正向构造：

• 第一步：两两配对。因为编号可以任意排列，所以 2k - 1 和 2k 匹配是字典序最小的。如果不是 2 的倍数，则办不到。
• 第二步：若 1 和 2k - 1 配对，则 2 和 2k 配对；反之若 1 和 2k 配对，则 2 和 2k - 1 配对。这相当于将 2k - 1 和 2k 看成一组，两组之间配对，总共可以贡献两轮。如果不是 4 的倍数，则办不到。
• 以此类推，第 i 步会将第 i - 1 步的大小为 2 ^ {i - 1} 的结构两两匹配，形成大小为 2 ^ i 的结构并贡献 2 ^ {i - 1} 轮，要求 2 ^ i\mid n。

综上，设 p 为最大的能整除 n 的 2 的幂，即 n 在二进制下最低位的 1，则 k_{\max} = 1 + \cdots + 2 ^ {p - 1} = 2 ^ p - 1​。注意上述推导只是感性理解，不构成严谨证明。可以尝试通过 “题述限制要求小结构合并时必须成对，得到大结构的大小为 2 的幂” 的思路进行证明，具体细节留给读者思考。

反向构造：设 f(a, b) = i 表示 a 和 b 在第 i 轮决斗，则题述要求等价于：若 f(a, b) = f(c, d) = i 且 f(a, c) = j，则 f(b, d) = j。根据 f 的该种性质，容易想到一个合理的二元运算符：异或。令 f(a, b) = (a - 1)\oplus (b - 1)，则 a 在第 i 轮的对手为 ((a - 1) \oplus i) + 1。这给出了 i < 2 ^ p 时的构造：当 i = 2 ^ p 时，((n - 1)\oplus 2 ^ p) + 1 = ((n - 1) + p) + 1 = n + p，不合法。

容易证明这样构造得到的是字典序最小解。

时间复杂度 \mathcal{O}(n\cdot \min(n, k))。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

// ---------- templates above ----------

int n, k;
void solve(int T) {
  cin >> n >> k;
  if(k >= (n & -n)) cout << "Impossible\n";
  else {
    for(int i = 1; i <= k; i++) {
      for(int a = 1; a <= n; a++) {
        cout << ((a - 1) ^ i) + 1 << " ";
      }
      cout << "\n";
    }
  }
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  cin >> T;
  while(T--) solve(T);
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/