首页 > 代码库 > 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 抽屉原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。