自动搬运

查看原文

来自洛谷，原作者为

	dbxxx 多刷题，少整那些没用的

搬运于2025-08-24 21:20:11，当前版本为作者最后更新于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, 2, 5$ 无法枚举到，是因为第一个数是 $3$ 时，第二个数从 $4$ 开始枚举，取不到 $2$。
• $2, 5, 3$ 无法枚举到，是因为第二个数是 $5$ 时，第三个数从 $6$ 开始枚举，取不到 $3$。

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

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

现在我们回归原题的样例。$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;
}

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