首页 > 代码库 > POJ2356 Find a multiple
POJ2356 Find a multiple
题解:
所谓鸽巢原理，通俗理解就是把n+1个物品放进n个盒子中，那么一定有一个盒子有2个物品
这题可以得到结论。
n个数中，必定有连续的m个数和sum，使得sum%n==0.
证明:
对于:sum[k]=a[1]+a[2]+.........a[k],1<=k<=n，若sum[k]%n==0。则直接得到，否则1<=sum[k]%n<=n-1。sum数组的大小为n，
那么，一定存在i,j使得sum(j)%n==sum(i)%n。故(sum(i)-sum(j))%n==0。即证
参考博客http://blog.csdn.net/acm_cxlove/article/details/7432166
代码:
vector保存
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>#include<vector>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define MS(x,y) memset(x,y,sizeof(x))#define MC(x,y) memcpy(x,y,sizeof(x))#define ls o<<1#define rs o<<1|1#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=20100;const int N=1e9;const int mod=1e9+7;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------ll a[maxn],sum[maxn];vector<int> s[maxn];int main(){ int n; n=read(); for(int i=1;i<=n;i++){ a[i]=read(); sum[i]=sum[i-1]+a[i]; s[sum[i]%n].pb(i); } if(s[0].size()>0){ printf("%d\n",s[0][0]); for(int i=1;i<=s[0][0];i++) printf("%d\n",a[i]); } else{ for(int i=1;i<=n-1;i++){ if(s[i].size()>1){ int c=s[i][0],b=s[i][1]; printf("%d\n",b-c); for(int j=c+1;j<=b;j++) printf("%d\n",a[j]); break; } } } return 0;}
直接模拟coding by cxlove
/*ID:cxlovePROB:POJ 2356DATA:2012.4.6HINT:鸽巢原理*/#include<iostream>#include<cstdio>#include<cstring>using namespace std;int main(){ int n,k; int a[10005]={0},b[10005]; while(scanf("%d",&n)!=EOF){ bool flag=false; memset(b,0,sizeof(b)); for(int i=1;i<=n;i++){ scanf("%d",&k); if(flag) continue; a[i]=a[i-1]+k; if(a[i]%n==0){ printf("%d\n",i); for(int j=1;j<=i;j++) printf("%d\n",a[j]-a[j-1]); flag=true; } else if(b[a[i]%n]){ printf("%d\n",i-b[a[i]%n]); for(int j=b[a[i]%n]+1;j<=i;j++) printf("%d\n",a[j]-a[j-1]); flag=true; } else b[a[i]%n]=i; } } return 0;}
POJ2356 Find a multiple
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。