更好的观看体验put_togetherXX の 家
题目描述
已知 n 个整数 x1,x2,⋯,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。
第二行 n 个整数，分别为 x1,x2,⋯,xn（1≤xi≤5×106）。
输出格式
输出一个整数，表示种类数。
输入输出样例
输入 #1复制
4 3
3 7 12 19
输出 #1复制
1
说明/提示
【题目来源】
NOIP 2002 普及组第二题
代码与解析
本题主要考察的是dfs暴力枚举 这样一说其实还算简单
我们可以构建一个dfs函数和一个判断质数的函数 但这道题却给了我一次教训
先讲dfs函数
我们可以让这个函数包含 现在选用了多少数，现在的和，上一个数的编号
Q:为什么要有上一个数的编号
A:降低复杂度
如1+2+4和1+4+2的和是同一个 这便是组合问题 （时间复杂度）
其次 通过知道上一个数的编号可少去开一个数组记录这个数是否被使用 （空间复杂度）
87分代码
#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],t;
bool zs(int x)
{
if(x==0||x==1)return false;
for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
return true;
}
void dfs(int id,int ans,int la)
{
if(id==k+1)if(zs(ans)){t++;return ;}
for(int i=la+1;i<=n;i++)dfs(id+1,ans+a[i],i);
return ;
}
int main()
{
cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0,0);cout<<t;
return 0;
}
提交之后 额外数据点超时（同时1.53s 要求1.5s）
优化
让dfs提前结束 比如说你现在取了2个数（id=2） 你后面还有3个数（n-la=3）
可是你要拿6个数（k=6） 你怎么取都去不了6个 因此做出如下优化
优化后代码 复杂度1.51s
#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],t;
bool zs(int x)
{
if(x==0||x==1)return false;
for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
return true;
}
void dfs(int id,int ans,int la)
{
if(id+(n-la)<k)return ;//加了这一行
if(id==k+1)if(zs(ans)){t++;return ;}
for(int i=la+1;i<=n;i++)dfs(id+1,ans+a[i],i);
return ;
}
int main()
{
cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0,0);cout<<t;
return 0;
}
1.51s还是超时 继续优化 为何不提前打表
打表优化代码
#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],t;bool nzs[100000005];
/*bool zs(int x)
{
if(x==0||x==1)return false;
for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
return true;
}*/
void dfs(int id,int ans,int la)
{
if(id+(n-la)<k)return ;
if(id==k+1)if(!nzs[ans]){t++;return ;}
for(int i=la+1;i<=n;i++)dfs(id+1,ans+a[i],i);
return ;
}
int main()
{
nzs[1]=true;nzs[0]=true;
for(int i=2;i<=100000000;i++)
{
if(nzs[i])continue;
for(int j=i+i;j<=100000000;j+=i)nzs[j]=true;
}
cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0,0);cout<<t;
return 0;
}
为什么是100000000 因为n做多为20 a[i]最大为5*10^6
没错用时1.7s 全部超时
正解
回到复杂度1.51s的
bool zs(int x)
{
if(x==0||x==1)return false;
for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
return true;
}
zs函数中 i<=sqrt(x) 这个引起了超时 原因很简单 浮点运算满 因此更为i*i<=x 即可满分通过
满分代码
#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],t;
bool zs(int x)
{
if(x==0||x==1)return false;
for(int i=2;i*i<=x;i++)if(x%i==0)return false;
return true;
}
void dfs(int id,int ans,int la)
{
if(id+(n-la)<k)return ;
if(id==k+1)if(zs(ans)){t++;return ;}
for(int i=la+1;i<=n;i++)dfs(id+1,ans+a[i],i);
return ;
}
int main()
{
cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0,0);cout<<t;
return 0;
}
结言：不要再使用sqrt了呀 太慢了
