鳩の巣の原理

転載は出典を明記してください.ありがとうございます.http://blog.csdn.net/ACM_cxlove?view mode=contensts           by---cxlove
基本的な原理はn＋1の物体はn個の箱に入れて、少なくとも一つの箱に二つの物体が置いてあります.
poj 2356
http://poj.org/problem?id=2356
n個の数がありますが、その中からいくつかの数の和がnの倍数です.
数学は不思議なものだと言わざるを得ない.結論は任意のn個の数で、必ず連続のm個の数の和はnの倍数である.
次に簡単に証明します.組み合わせの数学書の中で、黒い本が紹介されています.Skはa 1＋a 2＋…akを表しています.Skがnの倍数であれば、直接Skを取ります.そうでなければ、S 1-n除nの残数は1--(n-1)というn-1個の数に分布しています.鳩の巣原理を使うと、必ず二つの剰余が同じです.すなわち(Si% n)=(Sjn)=(Sj-n)です.

/*
ID:cxlove
PROB:POJ 2356
DATA:2012.4.6
HINT:    
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	int n,k;
	int a[10005]={0},b[10005];
	while(scanf("%d",&n)!=EOF){
		bool flag=false;
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++){
			scanf("%d",&k);
			if(flag) continue;
			a[i]=a[i-1]+k;
			if(a[i]%n==0){
				printf("%d
",i);
				for(int j=1;j<=i;j++)
					printf("%d
",a[j]-a[j-1]);
				flag=true;
			}
			else if(b[a[i]%n]){
				printf("%d
",i-b[a[i]%n]);
				for(int j=b[a[i]%n]+1;j<=i;j++)
					printf("%d
",a[j]-a[j-1]);
				flag=true;
			}
			else
				b[a[i]%n]=i;
		}
	}
	return 0;
}

POJ 3370http://poj.org/problem?id=3370
上の問題と同じように、n個の数の中からm個の数とcの倍数を探し出します.c<=n、上の証明を使うと、必ず連続するk個の数がcの倍数となりますので、オーバーフローする可能性があります.

/*
ID:cxlove
PROB:POJ 3370
DATA:2012.4.6
HINT:    
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
LL a[100005]={0},b[100005];
int main(){
	int n,k,c;
	while(scanf("%d%d",&c,&n)!=EOF&&n+c){
		bool flag=false;
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++){
			scanf("%d",&k);
			if(flag) continue;
			a[i]=a[i-1]+k;
			if(a[i]%c==0){
				for(int j=1;j<i;j++)
					printf("%d ",j);
				printf("%d
",i);
				flag=true;
			}
			else if(b[a[i]%c]){
				for(int j=b[a[i]%c]+1;j<i;j++)
					printf("%d ",j);
				printf("%d
",i);
				flag=true;
			}
			else
				b[a[i]%c]=i;
		}
	}
	return 0;
}

POJ 3145http://poj.org/problem?id=3145
昔作った問題ですが、鳩の巣の原理が巧みに使われています.
二つの操作があります
B Xは、数学x(1-500,000)をセットに入れて、
A Yは、集合中のモードYの最小数を出力します.複数あれば、最後にセットに入れる要素を出力します.
以下の問題を考慮して、0-(Y-1)の中でモードYが一番小さい数は必ず0-(Y-1)の中で数字が一番小さい数であることを考慮して、この類推(Y~2*Y-1)(2*Y~3*Y-1)に従って、線分樹は数字の挿入作業を処理して、区間の最小数を検索します.

/*
ID:cxlove
PROB:Harmony Forever 
DATA:2012.2.24
HINT:   ，    
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1<<30
#define MAX 500000
using namespace std;
struct line{
	int left,right,mid;
	int val;
}L[MAX*4];
int pos[MAX+5],cnt,val[MAX+5];
void bulid(int step,int l,int r){
	L[step].left=l;
	L[step].right=r;
	L[step].mid=(l+r)/2;
	L[step].val=inf;
	if(l==r)
		return;
	bulid(step<<1,l,(l+r)/2);
	bulid(step<<1|1,(l+r)/2+1,r);
}
void update(int step,int pos){
	if(L[step].left>pos||L[step].right<pos)
		return;
	if(L[step].left>=pos&&L[step].right<=pos){
		L[step].val=pos;
		return ;
	}
	if(pos<=L[step].mid)
		update(step<<1,pos);
	else
		update(step<<1|1,pos);
	L[step].val=min(L[step<<1].val,L[step<<1|1].val);
}
int query(int step,int l,int r){
	if(L[step].left>r||L[step].right<l)
		return inf;
	if(L[step].left>=l&&r>=L[step].right)
		return L[step].val;
	if(L[step].left<L[step].right)
		return min(query(step<<1,l,r),query(step<<1|1,l,r));
	return inf;
}
void slove(int mod){
	int l=0,r=mod-1,ans=-1,temp,k;
	while(l<=MAX){
		if(r>MAX)
			r=MAX;
		temp=query(1,l,r);		
		if(temp!=inf){
			if(ans==-1||(temp%mod)<(ans%mod))
				ans=temp;
			else if((temp%mod)==(ans%mod)&&pos[temp]>pos[ans])
				ans=temp;
		}
		l+=mod;
		r+=mod;
	}
	printf("%d
",pos[ans]);
}
void fun(int mod){
	int ans=inf,k;
	for(int i=cnt-1;i>=1;i--){
		if(val[i]%mod==0){
			k=i;
			break;
		}
		if(val[i]%mod<ans){
			ans=val[i]%mod;
			k=i;
		}
	}
	printf("%d
",k);
}
int main(){
	int q,m,tt=0;
	char str[5];
	while(scanf("%d",&q)&&q){
		if(tt>0)
			printf("
");
		printf("Case %d:
",++tt);
		bulid(1,0,MAX);
		cnt=1;
		for(int i=0;i<q;i++){
			scanf("%s",str);
			if(str[0]=='B'){
				scanf("%d",&m);
				val[cnt]=m;
				pos[m]=cnt++;
				update(1,m);
			}
			else{
				scanf("%d",&m);
				if(cnt==1)
					printf("-1
");
				else if(m<=5000)
					fun(m);
				else
			    	slove(m);
			}
		}
	}
	return 0;
}