鸽巢原理

发表于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 4 分钟

鸽巢原理

如果把 >n 个的元素放入n个抽屉中，那么一定有一个抽屉有大于等于2的元素，故又称 “抽屉原理”

poj 2356

题意：

找到m个数字使得这m个数字相加为n的倍数

输出m，然后输出这m个数字

题解：

先使用前缀和 sum[]

如果sum[i]%n==0 那么就已经找到了，输出 i 和这 i 个数字就行了

如果sum[i]%n!=0 那么一定存在 sum[j]%n==sum[i]%n , 那么输出i到j之间的数字就行了

注：

我一开始想的时候感觉这个题解有一点点问题，因为这个题解写的是按照连续的数字，也就是求一个区间内的，而且我也没有写0的情况，但是AC了，然后想为什么没有０，为什么数字都在一个区间内？万一不是一个区间的呢？然后就发现其实是我并没有很好的理解鸽巢原理，虽然这个原理看上去很简单，而且看上去和这道题没什么大的联系，但是上面的问题都可以用鸽巢原理来解释。

鸽巢原理对这题的解释：

因为有ｎ个 sum[i] ，所以在 [1,n-1] 的区间内必定最少有一个数字是由多个 sum[i]%n 的情况的。（ 因为sum[i]%n==0 就是一种情况的解，所以区间内不包含0，因此区间是 [1,n-1] ），因此这题必定有解，最少其中一个解必定是连续的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
const int N = 1e4 + 5;
int a[N],sum[N],mod[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) mod[i]=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		if(sum[i]%n==0){
			cout<<i<<endl;
			for(int j=1;j<=i;j++) cout<<a[j]<<endl;
			return 0;
		}
		else{
			if(mod[sum[i]%n]!=-1){
				cout<<i-mod[sum[i]%n]<<endl;
				for(int j=mod[sum[i]%n]+1;j<=i;j++) cout<<a[j]<<endl;
				return 0;
			}
		}
		mod[sum[i]%n]=i;
	}
	return 0;
}

poj 3370

和上题一样的思路……就不多说了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int a[N],sum[N],mod[N];
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) return 0;
		for(int i=1;i<=m;i++) mod[i]=-1;
		for(int i=1;i<=m;i++) sum[i]=0;
		for(int i=1;i<=m;i++){
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
			sum[i]%=n;
		}
		for(int i=1;i<=m;i++){
			if(sum[i]==0){
				for(int j=1;j<=i;j++) printf("%d ",j);
				break;
			}
			else{
				if(mod[sum[i]]!=-1){
					for(int j=mod[sum[i]]+1;j<=i;j++) printf("%d ",j);
					break;
				}
			}
			mod[sum[i]]=i;
		}
		printf("\n");
	}
	return 0;
}