自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:52:45，当前版本为作者最后更新于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
*/