HDU 鸽巢原理

鸽巢原理

把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。把多于m*n+1（n!=0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。把无数还多件物体放入n个抽屉，则至少有一个抽屉里有无数个物体。

一、HDU 1205 吃糖果

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1205 思路是，把数量最大的这一种类放在一堆，数量记为maxa，其他种类的糖果放在一堆，数量为sum-maxa。如果maxa > sum-maxa + 2，则意味着消耗完其他种类的糖果之后，数量最大的这一种类的糖果最后必定会剩下至少2个，也就是他不能把所有糖果都吃完。 代码如下：

#include <iostream> using namespace std; typedef long long ll; //HDU Accepted 1205 1669MS 1404K 373 B G++ int main() { int t, n; ll a; cin>>t; while(t--) { cin>>n; ll sum = 0; ll maxa = 0; for(int i=0; i<n; i++) { cin>>a; if(a > maxa) maxa = a; //记录数量最大的一种糖果 sum += a; //记录总和 } //maxa - (sum - maxa) >= 2，鸽巢原理 if(maxa - sum + maxa >= 2) printf("No\n"); else printf("Yes\n"); } return 0; }

二、HDU 5776 SUM

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5776 题目大意：给定一个序列，系统询问是否存在一个连续的子序列，其和可以被m整除。 若存在输出是，否则输出否。 思路是，我们边输入，边记录前缀和。我们将前缀和mod m，并对记录余数的数组（nest数组）相应位置加1，代表有几个前缀和模运算后是这个余数。此时有两种情况，第一种是，前缀和mod m为0，代表从1到当前位置的数相加正好可以被m整除；第二种是，前缀和不为0，但是出现这个余数的情况=2，那么通过将这两个前缀个相减，中间这几个数字的和就可以被m整除。

举例： 如：m=3, sequence：1 2 3，（1+2）%3 = 0，因此1、2的和可被m整除，输出Yes。 如：m=3, sequence：1 4 5，余数数组变化如下：nest[1] = 1 -> nest[2] = 1 -> nest[1] = 2，可以看到到5的时候，得到余数为1的情况为2个了，也就是4和5组成的和可以被m整除。

还有一处，就是当$n>m$时，由鸽巢原理可知，此种情况必然是可以被整除，可优化。 AC代码：

#include <iostream> #include <string.h> using namespace std; //HDU Accepted 5776 109MS 1800K 582B G++ const int MAXM = 5005; const int MAXN = 100005; int nest[MAXM]; int a[MAXN]; int main() { int t, n, m; cin>>t; while(t--) { cin>>n>>m; int sum = 0; memset(nest, 0, sizeof(nest)); for(int i=0; i<n; i++) { cin>>a[i]; sum += a[i]; //前缀和 nest[sum % m]++; } if(n > m) { cout<<"YES"<<endl; continue; } bool flag = false; for(int i=0; i<m; i++) { if(nest[i] >= 2 || nest[0]) { flag = 1; break; } } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } /* 1 5 7 1 4 5 4 9 --------- YES */

三、HDU 1808 Halloween treats

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1808 和第二题类似。 需要注意的是cin太慢了会导致TLE，因此加上这句std::ios::sync_with_stdio(false)，禁用cin的同步，就好啦~ 代码如下：

#include <iostream> using namespace std; typedef long long ll; const int MAXN = 100005; //HDU Accepted 1808 343MS 2996K 634 B G++ ll a[MAXN]; ll nest[MAXN]; int main() { std::ios::sync_with_stdio(false); //cin输入太慢了，导致超时 int c, n; while(cin>>c>>n && c+n) { //init for(ll i=0; i<=n; i++) nest[i] = 0; for(ll i=1; i<=n; i++) cin>>a[i]; ll sum = 0; //前缀和 for(ll i=1; i<=n; i++) { sum += a[i]; ll t = sum % c; if(t == 0) { for(ll j=1; j<i; j++) cout<<j<<" "; cout<<i<<endl; break; } else if(nest[t]) { //这个余数出现过 for(ll j=nest[t]+1; j<i; j++) cout<<j<<" "; cout<<i<<endl; break; } nest[t] = i; } } return 0; }