题解：P12606 碰碰车大战

· · 题解

Update 2025/7/25：为契合题目主题，增加文章《别样的构造大战》。

别样的构造大战

往下翻，有正常版题解。

一天，肚子的给我打来电话。他说："你敢不敢和我举行碰碰车大战？给定三个整数 n, m, k，构造 k 个 m 元组，满足每个元素在 [1, n] 中，且任意两个元组删去任意相同位置的一对元素后，剩下的部分都不相同。"我豪爽地答应了："我当然敢！周日下午在 xx 路 xx 大厦举行，谁不来谁就是怂货。"

我原本以为我恐吓了肚子的，肚子的应该躲在机房，不敢找我，可正当这时，我听见了音乐声，原来是我洛谷私信响了，一看，竟然是肚子的发来的输入样例：3 3 3。他还真有勇气，我轻蔑一笑，准备构造 3 个 3 元组，使每个元组的每个元素都相同：

1 1 1
2 2 2
3 3 3

可正当这时，肚子的打来电话："小废物，当 k 超过 n，你这方法不就被 hack 了？再不会正解你的锣鼓账号就要被我机惨了！"听到他对我的毒骂之后，我回击道："我要用 n 进制展开构造，前 m-1 个分量用 n 进制表示索引，最后一个分量由前 m-1 个分量的和模 n 决定，使任意两个元组至少有两个位置不同，再把你的 2147483647 个小号挂在同一场锣鼓月赛上并提交 AI 生成的代码，让你被封掉，你说好不好啊。"

他吓得没再回应我，可是到了周日，肚子的竟然又给我打电话了，他还真要和我举行构造大战，于是我按照约定，到达了 xx 大厦，可他已经等我很久了。

第一回合，我占上风，当 k \leq n 时，我直接输出 k 个元组，每个元组都是相同的数字：

for (int i = 1; i <= k; i++) {
    for (int j = 0; j < m; j++) {
        printf("%d ", i);
    }
    printf("\n");
}

肚子的还在手算 k=1 \times 10^5 的情况，他比不过我，到了第六回合，他就主动认输了。

第二回合，他开始占上风，构造出了一个 n=2, m=3, k=4 的情况。我也不甘示弱，我们僵持了 10^9+7 个回合，我由于轻敌地尝试：

// 错误示范：最后一个分量随便填
元组0: (1, 1, 1)
元组1: (1, 2, 2)
元组2: (2, 1, 2)
元组3: (2, 2, 1)

结果发现我的策略看似正确，但当 k=5 时，我无论如何都构造不出第五个元组，被他击败了。

从那时开始，我就不轻敌了，我认真研究他的套路，于是我总结出了一种方案：最后一个分量取前 m-1 个分量的和模 n 再加一，这样如果两个元组前 m-1 位只有一个位置不同，那么最后一个分量就会不同：

last = (sum(a[0] to a[m-2]) - 1) % n + 1;

第二天，我们举行第三局，他使用祖传暴力，对我发动猛烈的攻击，我们势均力敌，平分秋色，k \times m 最大 10^6 的数据规模使我们比了 998244353 个小时，也没分出胜负。

后来，他不知不觉的睡着了，我趁着这个好机会，一记凌车漂移，一飞冲天，精准地输出了所有元组：

// 对于k>n的情况
int d = m - 1;
for (long long i = 0; i < k; i++) {
    long long temp = i;
    // 将i转换成d位的n进制数
    for (int j = d-1; j>=0; j--) {
        a[j] = temp % n + 1;  // 映射到[1,n]
        temp /= n;
    }
    long long s = 0;
    for (int j = 0; j < d; j++) s += a[j];
    long long last = (s-1) % n + 1;  // 关键操作

    // 输出
    for (int j = 0; j < d; j++) printf("%d ", a[j]);
    printf("%lld\n", last);
}

打的他不敢还手，对他的打击比 freopen 写成 freeopen 还大。

正常版题解

这是一道 Special Judge 题目。

题意简述

本题要求构造 k 个 m 元组，满足以下条件：

  1. 每个元素均为 [1, n] 中的整数。

  2. 对于任意两个不同的元组 i 和 j，以及任意位置 p，存在一个位置 l \neq p 使得 x_{i,l} \neq x_{j,l}（即删除任意位置 p 后，剩余部分不同）。

思路

通过（kàn）观（tí）察（jiě），我们注意到：

Steps

  1. 当 k \leq n 时：

    • 输出 k 个元组，第 i 个元组所有分量为 i。

  2. 当 k > n 时：

    • 初始化 d = m - 1。
    • 对每个索引 i \in [0, k-1]：
      • 将 i 转换为 d 位 n 进制数（每位数加 1 存储）。
      • 计算前 d 个分量的和 s。
      • 第 m 个分量为 (s - 1) \bmod n + 1。
      • 输出整个元组。

Code

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    long long n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
    // k <= n 时：输出所有分量相同的元组
    if (k <= n) {
        for (int i = 1; i <= k; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j > 0) {
                    printf(" ");
                }
                printf("%d", i);
            }
            printf("\n");
        }
    }
    // k > n 时：使用 n 进制展开构造
    else {
        int d = sc<int>(m - 1);  // 前 m-1 个分量
        static int a[100000];
        for (long long i = 0; i < k; ++i) {
            long long temp = i;
            // 将 i 转换为 n 进制（d 位），存储到 a（高位在前）
            for (int j = d - 1; j >= 0; --j) {
                a[j] = sc<int>(temp % n) + 1;  // 映射到 [1, n]
                temp = temp / n;
            }
            // 计算前 d 个分量的和
            long long s = 0;
            for (int j = 0; j < d; ++j) {
                s += a[j];
            }
            // 计算最后一个分量：(s-1) mod n + 1
            long long last = (s - 1) % n + 1;
            if (last == 0) {  // 确保在 [1, n] 范围内
                last = n;
            }
            // 输出元组
            for (int j = 0; j < d; ++j) {
                printf("%d ", a[j]);
            }
            printf("%lld\n", last);
        }
    }
    return 0;
}

时间复杂度为 O(k \times m)，足以通过本题。（题目限制 k \times m \leq 10^6）