【组合数学】鸽巢原理

鸽巢原理，或称抽屉原理：把n+1个物体放进n个盒子，至少有一个盒子包含连个或更多的物体。

典型例题：

1.hdu 1205 吃糖果

小G有k种糖果，每种数量已知，小G不喜欢连续两次吃同样的糖果，问有没有可行的方案。

分析：找出最多数量的糖果，把它的数量N看成N块隔板，剩余所有糖果的数量为S。若两块隔板不能连续，则两块隔板之间必有一颗糖果。所以，只需判断S是否大于等于（N-1）即可。

#include <iostream>
 using namespace std;
 typedef long long ll;
 int main(){
     int t;
     cin>>t;
     while(t--){
         int n;
         cin>>n;
         ll num,minx=-1,s=0;
         while(n--){
             cin>>num;s+=num;
             if(num>minx)
             minx=num;
         }
         if(minx-1>(s-minx))
         cout<<"No"<<endl;
         else cout<<"Yes"<<endl;
     }
 }

View Code

2.hdu 1808

大致题意：n个邻居有n堆数中，问是否存在一些数，能否被C这个数整除。（C<n）

分析：此题根据抽屉原理，t表示前k的前缀和对C的取余的结果，s[t]=k记录此时的位置。当后面第m项出现相同的余数时，k+1项到m的和定是C的倍数，输出答案即可。

#include <iostream>
 #include <string.h>
 using namespace std;
 typedef long long ll;
 int f[100005],a[100005];
 int main(){
     int c,n;
     while(scanf("%d %d",&c,&n)){
         if(c==0&&n==0)break;
         memset(f,-1,sizeof f);
         ll s=0;
         for(int i=0;i<n;i++){
             scanf("%d",&a[i]);
         }
         for(int i=0;i<n;i++){
             s+=a[i];
             int t=s%c;
             if(t==0){
                 for(int j=0;j<=i;j++){
                     j==0?printf("%d",j+1):printf(" %d",j+1);
                 }
                 printf("\n");
                 break;
             }
             else if(f[t]!=-1){
                 for(int j=f[t]+1;j<=i;j++)
                 j==f[t]+1?printf("%d",j+1):printf(" %d",j+1);
                 printf("\n");break;
             }
             f[t]=i;
         }
     }
     return 0;
 }

View Code