题目：http://poj.org/problem?id=2356 大意：给出n个数字，在其中找出连续的数字使其和是n的倍数，不能找到输出0。 设sum[i]=a1+a2+……+ai,n个sum[i]模n的结果范围是[0,n-1]。由鸽巢原理可知：必有一个sum[i]的模结果是0（均匀分布）或有两个sum[i]模结果相等（非均匀分布）（也就是sum[j]-sum[i]=0）。所以一定存在着这样连续数字的和是n的倍数。N<=1e4，如果用纯暴力可能有超时的风险，以空间换时间，根据“必有一个sum[i]的模结果是0或有两个sum[i]模结果相等”使用标记法。
#include #include #include using namespace std; const int maxn=1e4+5; int sum[maxn],tag[maxn],a[maxn],l,r,N; int main() { //freopen("cin.txt","r",stdin); while(cin>>N){ memset(sum,0,sizeof(sum)); memset(tag,-1,sizeof(tag)); tag[0]=0; for(int i=1;i<=N;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; int m=sum[i]%N; if(tag[m]==-1) tag[m]=i; else { l=tag[m]; r=i; } } printf("%d ",r-l); for(int i=l+1;i<=r;i++){ printf("%d ",a[i]); } } return 0; }