【P1036 选数】题解

这是洛谷的P1036 选数的题解.这篇文章先发布于洛谷题解,因此存在和此博客风格略有出入的情况,请忽略.

点击这里直达题目.

本人大概是最弱的红名了吧(还是改了,现在是红名了)…一条咸鱼看着周围的大佬们瑟瑟发抖….

进入正题.这道题暴搜居然没有TLE,心情大好,来发篇题解,希望能帮上有需要的人的忙.

既然放在了过程函数和递归中,首先想到的就是用递归解决.首先考虑得到了一个和,如何判断它是不是质数?朴素方法,设这个数为n,从2至n-1,依此判断是否能整除n,如果发现存在某个整数能够整除n,那么n不是质数,否则是.显然循环次数规模与n相同.

简单优化,显然一个整数n若可以用两个整数的乘积表示,那么其中小一点的约数不会超过$\sqrt{n}$.我们以$60$为例 (试图隐藏我不打算证明的事实) :

60=1*60=2*30=3*20=4*15=5*12=6*10=10*6=..

显然,当超过$\sqrt{60}=7$时开始前面的数就是较大的约数了.因此,可以将枚举范围缩小到$[2,\sqrt{n}]$,时间复杂度降低到$O(\sqrt{n})$.简要代码如下:

1
2
3
4
5
6
bool isp(int a)//返回a是否为质数
{
int sq=sqrt(a);//调用函数求a的算术平方根.注意sqrt()函数在cmath中.提前算出可以避免每次循环都计算一次a的算术平方根,可以减小常数
for(int i=2;i<=sq;i++) if(a%i==0) return false;
return true;
}

考虑可能需要进行多次判断,即使如此优化仍可能超时,考虑一个更优的方法:注意到相加得到的和最大不超过$1\times10^7$,可以构造一个质数表,每次检查n是否为质数只需要查表即可.如何构造一个这样的质数表呢?显然由质数的定义可以得到,一个质数的任意整倍数(除其自身外)都不是质数,任意一个整数都可以被表示为某(几)个质数的乘积,也就是说任意的整数都是某(几)个质数的整倍数.因此只需将任意一个质数的二倍及以上的整倍数标记为”非质数”,就可以获得这样的一张质数表了.简要代码如下:

1
2
3
4
5
6
7
8
const int MAX=10000010;
bool notp[MAX];//质数表,当notp[i]==0时i为质数.注意开够空间

void calp(void)//开始构造质数表
{
for(int i=2;i<MAX;i++) if(!notp[i]) for(int j=i+i;j<MAX;j+=i) notp[j]=1;//当前的i是质数,因此将其所有二倍及以上的整倍数都设为非质数.注意不要越界
return;
}

这样一来就更优了.简单 (胡乱) 分析一波:外层循环将重复约$1\times10^7$次,若$i$不是质数则内层将仅进行$1$次判断,否则在判断后还将进行约$(1\times10^7-i)/i$次赋值操作.实验证明 (再次尝试隐藏自己不打算推式子的事实) ,该函数的循环仅会运行$3.95\times10^7$次,反复改变MAX的值可以发现运行次数与MAX的一次方成正比,即该方法可以在线性时间内构造质数表.为了确认自己已经理解了这一部分,建议先前去完成P3383 【模板】线性筛素数.

事实上,还可以再做两个小小的改变,进一步提高这个算法的效率.外层的for(int i=2;i<MAX;i++)可以修改为for(int i=2;i<sqrt(MAX);i++),而内层的for(int j=i+i;j<MAX;j+=i)可以修改为for(int j=i*i;j<MAX;j+=i).当然,建议将修改后的外层的条件修改为i<LIM,并在循环外加上int LIM=sqrt(MAX);,来避免重复计算带来的时间开销.这两处改动的正确性很显然,可以自己证咯.

到目前为止,我们获得了初始化时间复杂度为$O(n)$,查询时间复杂度为$O(1)$的质数表.下面,我们尝试回到原来的问题,看看我们还缺些什么.

我们需要从n个数中选出k个并计算它们的和.为了暴搜,我们需要寻找一种方法唯一地定义当前状态.很容易想到需要一个集合E表示已选择的数.可以用一个数组visited,标记所有已选的数的visited为1.像是这样:

1
2
3
4
//假设选了i
visited[i]=1;
cal();//递归调用
visited[i]=0;//还原确保之后不会漏选某种情况

可以很容易的利用visited统计已选的数的个数和和.看起来不错.但是不要容易确保不会选重的同时不选漏.比如

a[1]+a[2]+a[5],a[5]+a[2]+a[1]

而且每次查找visited也不够优美,应该还有更简单的解决办法.

很容易注意到,每次只向后看是不会漏选的.举例,如当前选到的数中下标最大的是low,那么选下一个数的时候只从下标为$[low+1,n]$的数中选不会导致缺失情况也不会导致重复 (依然不证明) ,因此可以重新定义当前状态:还须选i个数,当前的和为sum,当前已经看完了下标为k及以前的数.这样就确保了每次不需要检查重复的情况,也不需要管具体选择了哪些书,只要一一枚举k以后的数并递归调用就可以了,极大的简化了问题.

递归边界也不难得出:当还须选0个数的时候,已经选够了,判断当前的和是否为质数,如果是返回1,否则返回0.而非边界的时候则进行枚举,计算所有情况得到的返回值的和并返回,我们的函数返回值即使在当前限定条件下(从下标大于k的数中选i个数,在sum的基础上加上选的数的和结果是质数)的情况数.显然在主函数中调用cal(k,0,0)得到的返回值即为结果(注意,这里的k与函数中的k含义不同,此处于题目描述一致,请仔细确认不同k的含义).

最后还有一个小小的可行性剪枝:若cal函数中发现$n-k<i$则返回0.为了确认理解了k的含义,请自行思考理由.

附上AC代码(上面解释过的部分此处不再加注释):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>//虽然使用的是c++,但由于c的输入输出更快,倾向于使用c的输入输出
using namespace std;
const int MAX=10000010;
bool notp[MAX];
int a[25];//保存数据
int n;//函数中需要使用,为了方便设为全局变量

void calp(void)
{
for(int i=2;i<MAX;i++) if(!notp[i]) for(int j=i+i;j<MAX;j+=i) notp[j]=1;
return;
}

int cal(int i,int sum,int k) //再选i个,当前和为sum,看完了a[k]
{
if(i==0)
{
if(notp[sum]) return 0;
else return 1;
}

if(n-k<i) return 0;

int ans=0;
for(int j=k+1;j<=n;j++) ans+=cal(i-1,sum+a[j],j);
return ans;
}

int main()
{
calp();
int k;
//关于输入输出的问题请自行查找资料/请教他人解决
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",a+i);
printf("%d",cal(k,0,0));
return 0;
}

至此,虽然并没有使用更高效率的方法,我们依然以尚可以接受的时间通过了这道题.强烈建议再去完成P1706 全排列问题,使用类似的方法完成一道题可以加深理解.

补充一下,还有一道更进阶的题目P1691 有重复元素的排列问题

最后,本人蒟蒻一棵 (棵?),有不准确的地方请…用力喷!我会回来改正的.

Ps.现在看来当初自己写了些什么东西啊…恥ずかしい…

以上.

本文标题:【P1036 选数】题解

文章作者:Snake

发布时间:2018年04月06日 - 21:04

最后更新:2018年04月28日 - 20:04

原始链接:https://snake.moe/2018/04/06/【P1036 选数】题解/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。