桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。
这一现象就是我们所说的“抽屉原理”。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。
第一抽屉原理 原理1:把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。 原理2:把多于mn(m乘n)+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。 原理3:把无数多件物体放入n个抽屉,则至少有一个抽屉里有无数个物体。 第二抽屉原理 把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体(例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。
构造抽屉的方法
运用抽屉原理的核心是分析清楚问题中,哪个是物件,哪个是抽屉。例如,属相是有12个,那么任意37个人中,至少有一个属相是不少于4个人。这时将属相看成12个抽屉,则一个抽屉中有 37/12,即3余1,余数不考虑,而向上考虑取整数,所以这里是3+1=4个人,但这里需要注意的是,前面的余数1和这里加上的1是不一样的。
因此,在问题中,较多的一方就是物件,较少的一方就是抽屉,比如上述问题中的属相12个,就是对应抽屉,37个人就是对应物件,因为37相对12多。
抽屉问题试题链接:(我W了好几发,就是因为没有设long long,设的是int)
https://vjudge.net/contest/375775#problem/B
代码:
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> using namespace std; long long a[200005]; long long u[200005]; int main() { int c,n; while(scanf("%d%d",&c,&n)) { if(c==0&&n==0) break; for (int i=1;i<=n;i++) { scanf("%lld",&a[i]); u[i]=-1; //1-n的点都设为-1(不包括0) } long long sum=0; for (int i=1;i<=n;i++) { sum+=a[i]; if(u[sum%c]!=-1) { for (long long j=u[sum%c]+1;j<=i;j++) { printf("%lld",j); if(j!=i) cout << " "; } cout << endl; break; } u[sum%c]=i; } } return 0; }