566
技術社區[雲棲]
POJ 2356 鴿巢原理
題意：給定n個數，從中選出連續的若幹個，使得和為n的倍數。多解時輸出任意解。
這題運用鴿巢原理，首先用s[1],s[2],s[3]...s[n]表示第一個數到第n個數的和也就是s[n]=a[1]+...+a[n]，然後將s[i]分別對n取餘，顯然，如果s[i]=0那麼此時1-i個數即為n的倍數也就是答案，如果s[i]均不為0，那麼通過鴿巢原理可知s[i]個數為n，1<=s[i]<=n-1，那麼至少有兩個s[i] 即s[i]=s[j] (i!=j) 所以此時i+1至j 即為答案
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[10005],a[10005];
int main()
{
int n,f,ans1,ans2;
while(~scanf("%d",&n))
{
s[0]=f=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(f)
continue;
s[i]=(s[i-1]+a[i])%n;
if(s[i]==0)
f=1,ans1=i;
for(int j=1; j<i; j++)
if(s[j]==s[i])
{
f=2,ans1=j,ans2=i;
break;
}
}
if(f==1)
{
printf("%d\n",ans1);
for(int i=1; i<=ans1; i++)
printf("%d\n",a[i]);
}
if(f==2)
{
printf("%d\n",ans2-ans1);
for(int i=ans1+1; i<=ans2; i++)
printf("%d\n",a[i]);
}
}
return 0;
}
最後更新：2017-04-04 07:03:45