[已解决]洛谷p1036 选数

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. }

复制代码