NOIP2002普及組 選數
[问题描述]:
已知 n 个整数 x1,x2,…,xn，以及一个整数 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）
x1,x2，…,xn （1<=xi<=5000000）
[输出]：
格式为：一个整数（满足条件的种数）。
[输入输出样例]:
输入：choose.in
4 3
3 7 12 19
输出：choose.out
1
【分析】
排列組合問題，直接深度優先搜索（遞歸）即可。
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 39 40 41 42 43 44 45 46 47 48 49 | #include <iostream>#include <cstdio>#include <cmath>using namespace std;int sum=0;//當前總和int num[21];int n,k;int tot=0;bool prime(int num){ if (num==1)return false; for (int i=2;i<=(int)sqrt(double(num));i++) if (num%i==0) return false; return true; }void dg(int dep,int loc){ if(k-dep>n-loc) return; if (dep==k+1) { if (prime(sum)) tot++; } if (dep<k+1) { for (int i=loc;i<=n;i++) { sum+=num[i]; dg(dep+1,i+1); sum-=num[i]; } }}int main(){ freopen("choose.in","r",stdin); freopen("choose.out","w",stdout); cin>>n>>k; for (int i=1;i<=n;i++) cin>>num[i]; dg(1,1); cout<<tot<<endl; return 0;} |
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
正在编译...
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 20 | 0.026 s | 275 KB | 0 |
| 2 | 正确 | 20 | 0.001 s | 275 KB | 0 |
| 3 | 正确 | 20 | 0.001 s | 275 KB | 0 |
| 4 | 正确 | 20 | 0.001 s | 275 KB | 0 |
| 5 | 正确 | 20 | 0.001 s | 275 KB | 0 |
运行完成
运行时间 0.028 s
平均内存使用 275 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!
1 |
评论 (0)
