关于 P1036 【选数】
嗯，新手试炼场的，错了两次，对，我是蒟蒻。
因为这道题对我有帮助，所以，它是好题。
错啦两次，好尬的。
49——17——100；
不费话了，过程函数与递推。
当然要递推：
49分的不说了，从未先编译一下试试。
跟着题目走，判断质数。
来一段辣鸡代码
#includeusing namespace std;int n,k;int x[25];int ans;bool judge_prime(int x){ for(register int i;i*i<=x;i++) { if(x%i==0) { return false; } } return true;}int rule(int choose_left_num,int already_sum,int start,int end){ if(choose_left_num==0) { return judge_prime(already_sum); } int sum=0; for(register int i=start;i<=end;i++) { sum+=rule(choose_left_num-1,already_sum+x[i],i+1,end); } return sum;}int main(){ scanf("%d%d",&n,&k); for(register int i=1;i<=n;i++) { scanf("%d",&x[i]); } ans=rule(k,0,0,n-1); printf("%d",ans); return 0;}
递推函数：
choose_left_num为剩余的k；
already_sum为前面累加的和；
start和end为全组合（常见）剩下数字的选取范围；
生成全组合，在过程中逐渐把k个数相加，当选取的数个数为0时，直接返回前面的累加和是否为质数即可；
想了好久才懂得
谢谢题解
nonetheless,
however,
whereas,
but,
就你这种辣鸡水平还想递推，一边呆着！
所谓“骗分过样例，暴力出奇迹” 这段话搜狗拼音第一个(＾－＾)
暴搜啊，想什么哪？
所以：
#includeusing namespace std;int n,k;bool notp[10000010];int a[25];void caesar(void){ for(int i=2;i<10000010;i++) { if(!notp[i]) { for(int j=i+i;j<10000010;j+=i) { notp[j]=1; } } } return;}int cae(int x,int sum,int y){ if(x==0) { if(notp[sum]) return 0; else return 1; } if(n-y
老老实实地暴搜。
考虑可能需要进行多次判断,即使如此优化仍可能超时；
考虑一个更优的方法:
注意到相加得到的和最大不超过107,可以构造一个质数表；
每次检查n是否为质数只需要查表即可.如何构造一个这样的质数表呢?
由于一个质数的任意整倍数(除其自身外)都不是质数,任意一个整数都可以被表示为某(几)个质数的乘积,也就是说任意的整数都是某(几)个质数的整倍数；
因此只需将任意一个质数的二倍及以上的整倍数标记为"非质数",就可以获得这样的一张质数表了；
是这段：
int n,k;bool notp[10000010];//我叫质数婊，呸，质数表int a[25];void caesar(void)//我要创造质数，额(⊙o⊙)…质数表{ //当前的i是质数,因此将其所有二倍及以上的整倍数都设为非质数，千万不要越界 for(int i=2;i<10000010;i++) { if(!notp[i]) { for(int j=i+i;j<10000010;j+=i) { notp[j]=1; } } } return;} 这样一来就更优了.简单胡乱分析一波:
外层循环将重复约107次,若i不是质数则内层将仅进行1次判断,否则在判断后还将进行约(107-i)/i次赋值操作；
实验证明隐藏自己不打算推式子的事实,该函数的循环仅会运行3.95x107次,反复改变MAX的值可以发现运行次数与MAX的一次方成正比,即该方法可以在线性时间内构造质数表.
到目前为止,我们获得了初始化时间复杂度为O(n),查询时间复杂度为O(1)的质数表.下面,我们尝试回到原来的问题,看看我们还缺些什么？
我们需要从n个数中选出k个并计算它们的和.为了暴搜,我们需要寻找一种方法唯一地定义当前状态？
很容易注意到,每次只向后看是不会漏选的；
举例,如当前选到的数中下标最大的是low,那么选下一个数的时候只从下标为[low+1,n]的数中选不会导致缺失情况也不会导致重复依然不证明；
因此可以重新定义当前状态:
还须选i个数,当前的和为sum,当前已经看完了下标为k及以前的数.这样就确保了每次不需要检查重复的情况,也不需要管具体选择了哪些数；
只要一一枚举k以后的数并递归调用就可以了,极大的简化了问题.
递归边界也不难得出:
当还须选0个数的时候,已经选够了,判断当前的和是否为质数,如果是返回1,否则返回0；
而非边界的时候则进行枚举,计算所有情况得到的返回值的和并返回,我们的函数返回值即使在当前限定条件下(从下标大于k的数中选i个数,在sum的基础上加上选的数的和结果是质数)的情况数；
显然在主函数中调用cae(k,0,0)得到的返回值即为结果
最后还有一个小小的可行性剪枝:若cal函数中发现n-k<i则返回0
它：
#includeusing namespace std;int n,k;bool notp[10000010];int a[25];void caesar(void){ for(int i=2;i<10000010;i++) { if(!notp[i]) { for(int j=i+i;j<10000010;j+=i) { notp[j]=1; } } } return;}int cae(int x,int sum,int y){ if(x==0) { if(notp[sum]) return 0; else return 1; } if(n-y
差不多就这样。
谢谢！
人生总有那么一段大片大片空白的时光。你在等待，你在坚忍，你在静默。你在等一场春华秋实，你在等新一轮的春暖花开，你在等从未有过的雷霆万钧。这静默的日子有些长，有些闷，但是我也会等下去。我相信人的青春不止有一次，有时候，时光会给你额外的惊喜。
There is always a big blank space in life. You are waiting, you are persevering, you are silent. You are waiting for a spring and autumn harvest. You are waiting for a new round of spring blossoms. You are waiting for a thunderbolt that has never happened before. The silent days are long and stuffy, but I will wait. I believe that people have more than one youth. Sometimes, time gives you extra surprises.
人生にはいつも大きな空白の時間がある。あなたは待っていて、あなたは我慢して、あなたは静かにしています。あなたは春の美しさを待っていて、あなたは新しい1ラウンドの春の暖かい花が咲いて、あなたはかつてない雷の危機を待っています。この静かな日は少し長くて、少し退屈ですが、私も待っています。私は人の青春が一度だけではないと信じています。時には、時間はあなたに余分なサプライズを与えます。