题解 P1036 【选数】

dbxxx · 2018-11-07 12:33:13 · 题解

最初写于 2018 年 11 月，于 2025 年 2 月重构。

本题的难点在于如何用代码实现不重不漏地枚举每种选数方案，这个问题的答案是不降原则。下面开始解释。

举一个例子：a 是一个长度为 6 的序列 1, 2, 3, 4, 5, 6，想要不重不漏地枚举所有选择 3 个数的方案，如何操作？

一种错误的策略是：

• 第一个数在 1 \sim 6 枚举，设为 x_1。
• 第二个数在 1 \sim 6 枚举，且不选择 x_1（因为同一个数不能选两次）。
• 第三个数在 1 \sim 6 枚举，且不选择 x_1 和 x_2。

这种策略不正确在哪呢？答案是这样的统计重复了。比如 2, 3, 5 与 3, 2, 5，2, 5, 3 实际上是一种选法，但我们统计时却认为他们不同，分别统计了一次，这不是我们期望的。

解决这个问题的策略即不降原则，具体如下：

• 第一个数在 1 \sim 6 枚举，设为 x_1。
• 第二个数在 x_1 + 1 \sim 6 枚举，设为 x_2。
• 第三个数在 x_2 + 1 \sim 6 枚举，设为 x_3。

这样以来，每种选法都会被不重不漏地统计一次。比如 2, 3, 5 与 3, 2, 5，2, 5, 3 中，只有 2, 3, 5 会被统计到：

具体而言，利用每次选数时，不选择比上一次选择小的数的方法，达到每一次枚举到的方案，顺序一定不降，从而达到枚举不重复的目的，这就是不降原则。

这是枚举中基础，但又非常重要的思想，不局限于信息学。文化课的数学科目中，会做排列组合计数题的人，一定会枚举；而要想会枚举，一定要掌握不降原则。希望读者仔细吸收一下这个基本技能。

现在我们回归原题的样例。3, 7, 12, 19，如何不重不漏地枚举出所有选择三个数的情况？相信你已经有答案了：

• 第一个数选 3 时：
  • 第二个数要从 7 开始枚举。
  • 第二个数选 7 时：
    • 第三个数要从 12 开始枚举。
    • 第三个数选 12。此时选择：3, 7, 12，检验和是否为质数：22，否，不统计答案。
    • 第三个数选 19。此时选择：3, 7, 19。检验和是否为质数：29，是，统计答案。
  • 第二个数选 12 时：
    • 第三个数要从 19 开始枚举。
    • 第三个数选 19。此时选择：3, 12, 19。检验和是否为质数：34，否，不统计答案。
  • 第二个数选 19 时，第三个数无法选择，结束。
• 第一个数选 7 时：
  • 第二个数要从 12 开始枚举。
  • 第二个数选 12 时：
    • 第三个数要从 19 开始枚举。
    • 第三个数选 19。此时选择：7, 12, 19。检验和是否为质数：38。否，不统计答案。
  • 第二个数选 19 时，第二个数选 19 时，第三个数无法选择，结束。
• 第一个数选 12 时：
  • 第二个数要从 19 开始枚举。
  • 第二个数选 19 时，第三个数无法选择，结束。
• 第一个数选 19 时：
  • 第二个数无法选择，结束。

上面的选择过程存在明显的递归特征，因此我们考虑使用 dfs 实现程序。但观察上面的过程，我们又出现了两个问题：

• 在人工操作时，我们很容易看出枚举的顺序：3 \to 7 \to 12 \to 19。但在具体的代码实现中，这几个数都存在序列 a 里，选数在代码中如何呈现？
• 第一个数选 12 和 19 两种情况，由于后面根本不存在两个数字可以选择，所以这样的选择一定无效，能否直接优化掉？

对于第一个问题，答案是：不对具体的数字不降原则，而是对下标不降原则。即，我们每次不是选择具体值比上次大的数字，而是选择下标比上次大，即在 a 中出现的更靠后的数字。这样以来，每一步的选择都是在枚举 a 的一段后缀，从而每次选数时，只需明确从 a 的哪个位置开始枚举。这可以在 dfs 中传参做到，具体可见代码。

注意两种不降原则的差别。如 a = 7, 3, 12, 19 时，3, 7, 12 将不再被我们枚举到，被枚举到的是 7, 3, 12。

对于第二个问题，在经过第一个问题的改动后，我们可以通过简单的判断对这种情况进行剪枝。比如对于长度为 4 的 a 想选择 3 个数，那么第一次选择就不要选择太靠后的 a_3 和 a_4。这样以来，每一步选择在枚举 a 的一段后缀的基础上，又把太靠后的后缀优化掉了，现在我们每次选数枚举的是 a 的一段区间。

#include <bits/stdc++.h>

inline bool isprime(int x) { // 判断一个数是否是素数
    if (x == 1) return false; // 注意这步特判是必需的
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

const int N = 25;
int a[N], ans, n, k;

void dfs(int now, int sum, int sid) {
    // 现在已经选了 now 个数，当前总和为 sum
    // sid 是这次选数的起始下标，即我们从 a[sid] 开始选数枚举
    if (now == k) {
        if (isprime(sum))
            ++ans;
        return ;
    }

    // 已经选了 now 个数，这次选完后，还有 k - now - 1 个数要选择
    // 因此 a[n - (k - now - 1)] 即 a[n - k + now + 1] 是枚举的终点
    for (int i = sid; i <= n - k + now + 1; ++i)
        dfs(now + 1, sum + a[i], i + 1);
    return ;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    dfs(0, 0, 1);
    printf("%d\n", ans);
    return 0;
}

如果这篇题解帮助到您，请给这篇题解点个赞，谢谢！