从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;
好了,就是这样,喵~
我觉得我写的还是蛮清楚吧= =!
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int a[];
int mod[];
int sum[];
int main()
{
int n;
while(cin>>n)
{
memset(mod,,sizeof(mod));
memset(a,,sizeof(a));
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++)
{
cin>>a[i];
sum[i]+=a[i]+sum[i-];
}
for(int i=;i<=n;i++)
{
if(sum[i]%n==)
{
cout<<i<<endl;
for(int j=;j<i;j++)
cout<<a[j]<<endl;
cout<<a[i];
break;
}
if(mod[sum[i]%n]!=)
{
cout<<i-mod[sum[i]%n]<<endl;
for(int j=mod[sum[i]%n]+;j<i;j++)
cout<<a[j]<<endl;
cout<<a[i];
break;
}
mod[sum[i]%n]=i;
}
}
return ;
}