P1036 [NOIP2002 普及组] 选数
2022/2/4 6:12:27
本文主要是介绍P1036 [NOIP2002 普及组] 选数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
只能说是用递归dfs,感觉这个题目在暴力枚举中算是一个偏难的题了,我没怎么做过这类题,见识了不降原则之后只能说自己受教了
对于本题,所谓不降原则就是
:
在6里面随便选5个数,那么选法都是什么呢? 12345 12346 前两个还不会弄混 然后很可能就乱了 少点数可能不会乱 但是多了就不好整了 比如说在100里随便选50个数。 1 2 3 4 5 6 7 8 9 10 11 12...... Die. 所以我们可以运用不降原则: 保证枚举的这些数是升序排列 其实真正的不降原则还可以平 比如 1 2 2 3 3 4...... 但是请注意这道题也不能平 否则就有重复数字了 拿6个里面选3个举例子 1 2 3 1 2 4 1 2 5 1 2 6 第一轮枚举完毕。 第二个数加一 1 3 ? 这个“?”应该是4,因为是升序排列 1 3 4 1 3 5 1 3 6 接着,就是这样 1 4 5 1 4 6 1 5 6 第一位是1枚举完毕 第一位是2呢? 2 3 4 2 3 5 2 3 6 2 4 5 2 4 6 2 5 6 以此类推..... 3 4 5 3 4 6 3 5 6 4 5 6 然后就枚举不了了,结束。
并且附上讲解视频:https://www.bilibili.com/video/BV1ry4y1372t?from=search&seid=15955411940625510269&spm_id_from=333.337.0.0
附上代码了:
#include<bits/stdc++.h> using namespace std; int n,k; int a[25]; int ans; bool isprime(int a)//判断是不是素数 { for(int i=2;i<=sqrt(a);i++) { if(a%i==0) return false;//不是素数 } return true;//是素数 } void dfs(int step,int sum,int start)//start用来表示这个数字遵循这不降原则,step表示层数 { if(step==k) { if(isprime(sum))//如果和是素数 ans++; return ; } for(int i=start;i<n;i++) { dfs(step+1,sum+a[i],i+1);//进入下一层;开始累加; 升序起始值要变成i+1,以免算重 } } int main() { cin>>n>>k; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } dfs(0,0,0); cout<<ans<<endl; return 0; }
这篇关于P1036 [NOIP2002 普及组] 选数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现