首页 > 代码库 > POJ 2356 Find a multiple 抽屉原理

POJ 2356 Find a multiple 抽屉原理

从POJ 2356来体会抽屉原理的妙用= =!

题意:

给你一个n,然后给你n个数,让你输出一个数或者多个数,让这些数的和能够组成n;

先输出一个数,代表有多少个数的和,然后再输出这些数;

题解:

首先利用前缀和先预处理一下,然后如果sum[i]==0的话,很显然就直接输出i,然后接下来从第一位一直输出到第i位就行了

然后接下来直接用一个mod数组表示上一个答案为这个mod的时候的编号是多少

就是mod[sum[i]%n]=i; 

然后判断一下if(mod[sum[i]%n]!=0)然后就直接从mod[sum[i]%n]+1位一直输出到第i位就行了。

证明如下,如果sum[i]和sum[j],它俩mod n的值都相同的话,则必然可以(sum[i]-sum[j])%n==0;

 

好了,就是这样,喵~

我觉得我写的还是蛮清楚吧= =!

 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 using namespace std; 6 int a[10000]; 7 int mod[10000]; 8 int sum[10001]; 9 int main()10 {11     int n;12     while(cin>>n)13     {14         memset(mod,0,sizeof(mod));15         memset(a,0,sizeof(a));16         memset(sum,0,sizeof(sum));17         for(int i=1;i<=n;i++)18         {19             cin>>a[i];20             sum[i]+=a[i]+sum[i-1];21         }22         for(int i=1;i<=n;i++)23         {24             if(sum[i]%n==0)25             {26                 cout<<i<<endl;27                 for(int j=1;j<i;j++)28                     cout<<a[j]<<endl;29                 cout<<a[i];30                 break;31             }32             if(mod[sum[i]%n]!=0)33             {34                 cout<<i-mod[sum[i]%n]<<endl;35                 for(int j=mod[sum[i]%n]+1;j<i;j++)36                     cout<<a[j]<<endl;37                 cout<<a[i];38                 break;39             }40             mod[sum[i]%n]=i;41         }42     }43     return 0;    44 }

 

POJ 2356 Find a multiple 抽屉原理