poj 3370 鸽笼原理知识小结

中学就听说过抽屉原理,可惜一直没机会见识,现在这题有鸽笼原理的结论,但其实知不知道鸽笼原理都可以做

先总结一下鸽笼原理:

有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。

如果你知道这个结论:
a1,a2,a3...am是正整数序列,至少存在整数k和r,1<=k<r<=m,使得ak+a(k+1)+...+a(r)是m的倍数。

证明比较简单:

Sk表示前k个数之和,

(1)若Sk%m==0,前k个数就是m的倍数

(2)如果Sn与St模m同余,那么从t+1到n这些数之和模m等于0.

即使你不知道这个结论,DP厉害的话,应该能想到用 前n项的和 去思考的思想

有这个结论知必有解。

贴代码之前,在总结一下鸽笼原理的结论:
推论1:m只鸽子,n个笼,则至少有一个鸽笼里有不少于[(m-1)/n]+1只鸽子。

推论2:若取n*(m-1)+1个球放进n个盒子,则至少有1个盒子有m个球。

推论3:若m1,m2,...mn是n个正整数,而且(m1+m2+...+mn)/n>r-1

则m1,m2,...mn中至少有一个数不小于r

直接贴代码吧:没啥解释的,700多MS,当时judge的时候我还害怕TLE

#include<cstdio>
#include<cstring>
using namespace std;
#define N 100002 int sum[N],pos[N]; int main()
{ int c,n,i,r,t,j; while(scanf("%d%d",&c,&n),c+n)
{
memset(pos,-1,sizeof(pos));
bool flag=false; scanf("%d",&sum[0]);
sum[0]%=c;
pos[sum[0]]=0;
if(sum[0]==0){printf("1\n");flag=1;} for(i=1;i<n;i++)
{
scanf("%d",&sum[i]);
if(flag)continue;
sum[i]%=c;
sum[i]+=sum[i-1];
sum[i]%=c;
if(sum[i]==0)
{
for(j=0;j<i;j++)
printf("%d ",j+1);
printf("%d\n",i+1);
flag=1;
continue;
}
if(pos[sum[i]]==-1)pos[sum[i]]=i;
else
{
for(j=pos[sum[i]]+1;j<=i;j++)
if(j!=i)printf("%d ",j+1);
else printf("%d\n",i+1);
flag=1;
}
} } return 0;
}
上一篇:CentOS Crontab(定时任务)


下一篇:Asp.Net 无法获取IIS拾取目录的解决办法[译]