[已解决]洛谷p1036 选数

zzzyf

只a了一个点，找了好久，结果改了之后总是全错。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int k,n,ans;
   
4. int a[20],b[100];
   
5. bool pr[312501];
   
6. void pro(){
   
7.     for(int i=2;i<177;i++){
   
8.         if(i%2==1||i==2){
   
9.             for(int j=i*i;j<=312500;j+=2){
   
10.                 if((j%i==0||pr[j])){
    
11.                     pr[j]=true;
    
12.                 }
    
13.             }
    
14.         }
    
15.         else{
    
16.             for(int j=i*i+1;j<=312500;j+=2){
    
17.                 if(j%i==0||pr[j]){
    
18.                     pr[j]=true;
    
19.                 }
    
20.             }
    
21.         }
    
22.         
    
23.     }
    
24. }
    
25. // int cc(int ns){
    
26. //     for(int i=0;i<ans;i++){
    
27. //         if(ns==b[i]){
    
28. //             return 0;
    
29. //         }
    
30. //     }
    
31. //     b[ans]=ns;
    
32. //     return 1;
    
33. // }
    
34. void z(int i,int an,int step){
    
35.     if(step==k){
    
36.         //cout<<an+a[i]<<endl;
    
37.         if(!pr[an+a[i]]){
    
38.             //ans+=cc(an+a[i]);
    
39.             cout<<an+a[i]<<endl;
    
40.             ans++;
    
41.         }
    
42.     }
    
43.     else{
    
44.         for(int l=i;l<=n;l++){
    
45.             z(l+1,an+a[i],step++);
    
46.         }
    
47.     }
    
48. }
    
49. int main(){
    
50.     pro();
    
51.     cin>>n>>k;
    
52.     for(int i=0;i<n;i++){
    
53.         cin>>a[i];
    
54.     }
    
55.     int o=0;
    
56.     for(int i=0;i<n-k;i++){
    
57.         z(i,0,1);
    
58.     }
    
59.     cout<<ans;
    
60. 
    
61.     return 0;
    
62. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

jhq999

2022-7-11 09:57:32

应该先把奇偶分类
然后奇数选择奇数个，偶数=k-选择奇数的个数
然后再判断和是否为素数（判断时枚举的因子应该都是奇数）

1. typedef struct GETSUSU
   
2. {
   
3.     int *num,*jisu,*ousu,*numk;
   
4.     int ncount,jisucount,ousucount,k;
   
5. 
   
6.     int jisuseek,oususeek,jisuselect,tongjicount;
   
7. 
   
8. 
   
9. }GSS,*pGSS;
   
10. int ousu(pGSS pgss,int n)
    
11. {
    
12.     if(0==n)
    
13.     {
    
14.         for(int i=0;i<pgss->k;i++)
    
15.         {
    
16.             printf("%4d",pgss->numk[i]);
    
17.         }
    
18.         printf("\n");
    
19.         pgss->tongjicount+=1;
    
20.         return 1;
    
21.     }
    
22.     for(int i=pgss->oususeek;i<=pgss->ousucount-n;i++)
    
23.     {
    
24.         pgss->numk[pgss->jisuselect+n-1]=pgss->ousu[i];
    
25.         pgss->oususeek=i+1;
    
26.         ousu(pgss,n-1);
    
27.         pgss->oususeek=i;
    
28.     }
    
29.     return 0;
    
30. }
    
31. int jisu(pGSS pgss,int n)
    
32. {
    
33.     if(0==n)
    
34.     {
    
35.         pgss->oususeek=0;
    
36.         ousu(pgss,pgss->k-pgss->jisuselect);
    
37.         return 1;
    
38.     }
    
39.     for(int i=pgss->jisuseek;i<=pgss->jisucount-n;i++)
    
40.     {
    
41.         pgss->numk[n-1]=pgss->jisu[i];
    
42.         pgss->jisuseek=i+1;
    
43.         jisu(pgss,n-1);
    
44.         pgss->jisuseek=i;
    
45.     }
    
46.     return 0;
    
47. }
    
48. int combination(int a,int b)
    
49. {
    
50.     int sum1=1,sum2=1;
    
51.     for(int i=a;i>a-b;i--)sum1*=i;
    
52.     for(int i=1;i<=b;i++)sum2*=i;
    
53.     return sum1/sum2;
    
54. 
    
55. }
    
56. int main()
    
57. {
    
58.     GSS gss;
    
59.     int n=0,k=0,i=0,j=0,t=0;
    
60.     scanf("%d%d",&n,&k);
    
61.     gss.k=k;
    
62.     gss.ncount=n;
    
63.     gss.num=(int*)calloc(n,sizeof(int));
    
64.     gss.numk=(int*)calloc(k,sizeof(int));
    
65.     gss.jisuseek=gss.oususeek=0;
    
66.     for(i=0,j=n-1;i<j+1;)
    
67.     {
    
68.         scanf("%d",&t);
    
69.         if(t%2)gss.num[i++]=t;
    
70.         else
    
71.             gss.num[j--]=t;
    
72.     }
    
73.     gss.jisucount=i,gss.ousucount=n-i;
    
74.     gss.jisu=gss.num,gss.ousu=gss.num+i;
    
75.     for(i=0;i<n;i++)printf("%4d",gss.num[i]);
    
76.     printf("\n");
    
77.     gss.tongjicount=0;
    
78.     int sum=0;
    
79.     for(i=1;i<=gss.jisucount;i+=2)
    
80.     {
    
81.         sum+=combination(gss.jisucount,i)*combination(gss.ousucount,k-i);
    
82.         gss.jisuseek=gss.oususeek=0;
    
83.         gss.jisuselect=i;
    
84.         jisu(&gss,i);
    
85.     }
    
86. 
    
87.     printf("\n%d",gss.tongjicount);
    
88.     printf("\n%d",sum);
    
89.     free(gss.numk);
    
90.     free(gss.num);
    
91. 
    
92.     return 0;
    
93. }

复制代码

跳转到最佳答案楼层

傻眼貓咪

我不知道对不对，你可以试试这个方法：

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. bool isPrime(int num) {
   
6.         if (num < 2)return false;
   
7.         else if (num == 2)return true;
   
8.         for (int n = 2; n < pow(num, .5) + .5; ++n) {
   
9.                 if (not (num % n)) {
   
10.                         return false;
    
11.                 }
    
12.         }
    
13.         return true;
    
14. }
    
15. 
    
16. // Depth-first search 深度优先搜索
    
17. // arr: 数组, k: 相加的整数个数, num: 已相加多少个数？ i: 当前数组位置, sum: 相加结果, res: 为素数个数
    
18. unsigned DFS(const vector<int>& arr, int k, int num = 0, int i = 1, int sum = 0, int res = 0) {
    
19.     if (num == k){
    
20.         if (isPrime(sum)) return 1;
    
21.         return 0;
    
22.     }
    
23.     for (int j = i; j < arr.size(); ++j) {
    
24.         res += DFS(arr, k, num + 1, j + 1, sum + arr[j]);
    
25.     }
    
26.     return res;
    
27. }
    
28. 
    
29. int main()
    
30. {
    
31.     int n, k;
    
32.     vector<int> arr;
    
33.     arr.push_back(0);
    
34.     cin >> n >> k;
    
35.     for (int i = 1, num; i <= n; i++) {
    
36.         cin >> num;
    
37.         arr.push_back(num);
    
38.     }
    
39.     cout << DFS(arr, k);
    
40.     return 0;
    
41. }

复制代码

柿子饼同学

这题我也有点蒙 , 感觉我的代码是可以过的 , 为什么过不去

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int nums[21], n, k, ans = 0; // 存数字
   
5. bool vis[21]; // 看是否用过
   
6. 
   
7. bool check(int n){ // 看是否是素数
   
8.     int l = sqrt((float)n);
   
9.     for(int i = 2; i <= l; i++){
   
10.         if(n % i == 0) return 0;
    
11.     }
    
12.     return 1;
    
13. }
    
14. 
    
15. void dfs(int dep/*看用了几个数*/, int sum/*加起来的数*/){
    
16.     if(dep == k){ // 用了 k 个数之后
    
17.         if(check(sum)) ans++; // 符合条件就加上一种可能
    
18.         return;
    
19.     }
    
20.     else{
    
21.         for(int i = 0; i < n; i++){ // 遍历整个数组
    
22.             if(!vis[i]){
    
23.                 vis[i] = 1; // vis[i] 代表是否用过 i , 这里如果没用过就用
    
24.                 dfs(dep + 1, sum + nums[i]); // 取的数 +1 , 加起来的数 +nums[i]
    
25.                 vis[i] = 0; // 回溯 , 等他回来就恢复现场让它继续选
    
26.             }     
    
27.         }
    
28.     }
    
29. }
    
30. 
    
31. int main(){
    
32.     ios::sync_with_stdio(0);
    
33. 
    
34.     cin >> n >> k;
    
35.     for(int i = 0; i < n; i++){
    
36.         cin >> nums[i];
    
37.     }
    
38. 
    
39.     dfs(0, 0);
    
40. 
    
41.     cout << ans << endl;
    
42. 
    
43.     return 0;
    
44. }

复制代码

柿子饼同学

傻眼貓咪 发表于 2022-7-9 19:36
我不知道对不对，你可以试试这个方法：

vis 数组为啥不行

傻眼貓咪

柿子饼同学 发表于 2022-7-9 19:57
vis 数组为啥不行

会不会是全局变量有影响？你的代码递归前后都改变 vis 值，可能在其中搜索树根改变了它的值，让答案越变越多。而我的代码完全没有用全局，因为虽然全局变量可行，但递归 + 全局的变数太多，我懒的想，所以不用。

jhq999

应该先把奇偶分类
然后奇数选择奇数个，偶数=k-选择奇数的个数
然后再判断和是否为素数（判断时枚举的因子应该都是奇数）

1. typedef struct GETSUSU
   
2. {
   
3.     int *num,*jisu,*ousu,*numk;
   
4.     int ncount,jisucount,ousucount,k;
   
5. 
   
6.     int jisuseek,oususeek,jisuselect,tongjicount;
   
7. 
   
8. 
   
9. }GSS,*pGSS;
   
10. int ousu(pGSS pgss,int n)
    
11. {
    
12.     if(0==n)
    
13.     {
    
14.         for(int i=0;i<pgss->k;i++)
    
15.         {
    
16.             printf("%4d",pgss->numk[i]);
    
17.         }
    
18.         printf("\n");
    
19.         pgss->tongjicount+=1;
    
20.         return 1;
    
21.     }
    
22.     for(int i=pgss->oususeek;i<=pgss->ousucount-n;i++)
    
23.     {
    
24.         pgss->numk[pgss->jisuselect+n-1]=pgss->ousu[i];
    
25.         pgss->oususeek=i+1;
    
26.         ousu(pgss,n-1);
    
27.         pgss->oususeek=i;
    
28.     }
    
29.     return 0;
    
30. }
    
31. int jisu(pGSS pgss,int n)
    
32. {
    
33.     if(0==n)
    
34.     {
    
35.         pgss->oususeek=0;
    
36.         ousu(pgss,pgss->k-pgss->jisuselect);
    
37.         return 1;
    
38.     }
    
39.     for(int i=pgss->jisuseek;i<=pgss->jisucount-n;i++)
    
40.     {
    
41.         pgss->numk[n-1]=pgss->jisu[i];
    
42.         pgss->jisuseek=i+1;
    
43.         jisu(pgss,n-1);
    
44.         pgss->jisuseek=i;
    
45.     }
    
46.     return 0;
    
47. }
    
48. int combination(int a,int b)
    
49. {
    
50.     int sum1=1,sum2=1;
    
51.     for(int i=a;i>a-b;i--)sum1*=i;
    
52.     for(int i=1;i<=b;i++)sum2*=i;
    
53.     return sum1/sum2;
    
54. 
    
55. }
    
56. int main()
    
57. {
    
58.     GSS gss;
    
59.     int n=0,k=0,i=0,j=0,t=0;
    
60.     scanf("%d%d",&n,&k);
    
61.     gss.k=k;
    
62.     gss.ncount=n;
    
63.     gss.num=(int*)calloc(n,sizeof(int));
    
64.     gss.numk=(int*)calloc(k,sizeof(int));
    
65.     gss.jisuseek=gss.oususeek=0;
    
66.     for(i=0,j=n-1;i<j+1;)
    
67.     {
    
68.         scanf("%d",&t);
    
69.         if(t%2)gss.num[i++]=t;
    
70.         else
    
71.             gss.num[j--]=t;
    
72.     }
    
73.     gss.jisucount=i,gss.ousucount=n-i;
    
74.     gss.jisu=gss.num,gss.ousu=gss.num+i;
    
75.     for(i=0;i<n;i++)printf("%4d",gss.num[i]);
    
76.     printf("\n");
    
77.     gss.tongjicount=0;
    
78.     int sum=0;
    
79.     for(i=1;i<=gss.jisucount;i+=2)
    
80.     {
    
81.         sum+=combination(gss.jisucount,i)*combination(gss.ousucount,k-i);
    
82.         gss.jisuseek=gss.oususeek=0;
    
83.         gss.jisuselect=i;
    
84.         jisu(&gss,i);
    
85.     }
    
86. 
    
87.     printf("\n%d",gss.tongjicount);
    
88.     printf("\n%d",sum);
    
89.     free(gss.numk);
    
90.     free(gss.num);
    
91. 
    
92.     return 0;
    
93. }

复制代码