鴿巢原理又名抽屜原理

一種簡(jiǎn)單的表述法為：

• 若有n個(gè)籠子和n+1只鴿子，所有的鴿子都被關(guān)在鴿籠里，那么至少有一個(gè)籠子有至少2只鴿子。

另一種為：

• 若有n個(gè)籠子和kn+1只鴿子，所有的鴿子都被關(guān)在鴿籠里，那么至少有一個(gè)籠子有至少k+1只鴿子。

例子：

• 盒子里有10只黑襪子、12只藍(lán)襪子，你需要拿一對(duì)同色的出來(lái)。假設(shè)你總共只能拿一次，只要3只就可以拿到相同顏色的襪子，因?yàn)轭伾挥袃煞N（鴿巢只有兩個(gè)），而三只襪子（三只鴿子），從而得到“拿3只襪子出來(lái)，就能保證有一雙同色”的結(jié)論。
• 有n個(gè)人（至少2人）互相握手（隨意找人握），必有兩人握手次數(shù)相同。

一種表達(dá)是這樣的：如果要把n個(gè)物件分配到m個(gè)容器中，必有至少一個(gè)容器容納至少?n / m?個(gè)物件。（?x?大于等于x的最小的整數(shù)）

?

容斥原理又稱排容原理

（1）兩個(gè)集合容斥關(guān)系

（2）三個(gè)集合容斥關(guān)系

（3）n個(gè)集合的容斥關(guān)系

即1個(gè)集合的并-2個(gè)集合的并+3個(gè)集合的并-4個(gè)集合的并+5個(gè)集合的并......

?

鴿巢：

pku2365 Find a multiple

?題目意思是給n個(gè)數(shù)，選擇其中一些數(shù)，使他們的和是n的k倍，k是自然數(shù)。只要輸出其中正確的解就行

分析：

這n個(gè)數(shù)有n個(gè)前綴和,s[0],s[1],s[2]...s[n]，并且對(duì)n取余

如果有s[i]==0，則輸出0-i之間的數(shù)

如果不存在s[i]==0, 則s[i]一定在[1,n-1]之間 ，

根據(jù)鴿巢原理，n個(gè)物體放入n-1個(gè)盒子，至少有一個(gè)盒子有兩個(gè)及以上的物體，所以題目一定有解

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 10010 int n; int arr[maxn],s[maxn],h[maxn]; int main() {while(~scanf("%d",&n)){memset(h,-1,sizeof(h));int x;for(int i=0;i<n;i++){scanf("%d",&arr[i]);s[i]=(s[i-1]+arr[i])%n;}int a,b;for(int i=0;i<n;i++){if(s[i]==0){a=0;b=i;break;}else{if(h[s[i]]!=-1){a=h[s[i]]+1;b=i;break;}else h[s[i]]=i;}}printf("%d\n",b-a+1);for(int i=a;i<=b;i++)printf("%d\n",arr[i]);}return 0; } View Code

pku3370 Halloween treats

?和pku2365相同，c個(gè)孩子在n個(gè)neighbor中要選擇糖果，使得糖果總和是c的倍數(shù)

注意鴿巢原理的使用范圍，有n-1個(gè)盒子，至少n個(gè)物體，如果neighbor給的糖數(shù)為0，則盒子數(shù)量要減少，當(dāng)然沒(méi)有這種數(shù)據(jù)了

tip:數(shù)組下標(biāo)盡量不要用-1，或者每次讓s[-1]=0，進(jìn)行初始化。這個(gè)地址由于沒(méi)有跟著數(shù)組空間一起初始化，
所以其中的數(shù)據(jù)是不一定的， #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 100010 #define ll long long int c,n; int h[maxn],a[maxn],x; int main() {while(~scanf("%d%d",&c,&n)){if(c==0&&n==0)break;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}memset(h,-1,sizeof(h));int s=0;h[0]=0;for(int i=1;i<=n;i++){s=(s+a[i])%c;// printf("* %d %d\n",i,s);if(h[s]!=-1){for(int j=h[s]+1;j<i;j++){printf("%d ",j);}printf("%d\n",i);break;}else h[s]=i;}}return 0; } View Code

容斥：

hdu1695?GCD?

x=[a,b] , y=[c,d] ?求gcd(x,y)=k 的組合數(shù) ,a=1,c=1 ，(x,y),(y,x)是同一種組合

用容斥原理+二進(jìn)制枚舉。

先把b/=k ,d/=k

問(wèn)題變成x=[1,b] ?y=[1,d] ,其中(x,y)互質(zhì)的對(duì)數(shù)

枚舉x，預(yù)處理x的質(zhì)因子，假設(shè)w是x的質(zhì)因子，1-d中w的倍數(shù)有d/w個(gè)

假設(shè)f(n)表示1-d中n個(gè)x的質(zhì)因子乘積的倍數(shù)

容斥原理：不與x互質(zhì)的個(gè)數(shù)=f(1)-f(2)+f(3)-f(4)...

注意：答案很大，用long long存

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define maxn 100010 #define ll long long vector<int>v[maxn]; bool is[maxn]; void prime() {for(int i=0;i<maxn;i++)v[i].clear();memset(is,false,sizeof(is));is[0]=is[1]=true;for(int i=2;i<maxn;i++){for(int j=i;j<maxn;j+=i){if(!is[i]){v[j].push_back(i);if(j>i)is[j]=true;}}} } int work(int u,int s,int d)// d是范圍1-d s是狀態(tài)壓縮 u是素因子表 {int cnt=0;int mul=1;for(int i=0;i<v[u].size();i++){if((1<<i)&s){mul*=v[u][i];cnt++;}}int all=d/mul-(u-1)/mul;//u-d 內(nèi)s選擇狀態(tài)因子的倍數(shù)的個(gè)數(shù)(d>u)if(cnt%2==0)all=-all;return all; } int main() {prime();int T;scanf("%d",&T);for(int ca=1;ca<=T;ca++){int a,b,c,d,k;ll ans;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);if(k==0)ans=0;else{ans=0;b/=k;d/=k;if(b>d)b^=d^=b^=d;for(int i=1;i<=b;i++){ans+=d-i+1;//(x,y) 和(y,x)算一種 選擇范圍i-dint p=(1<<v[i].size());//p是素因子是否選取的所有狀態(tài)for(int j=1;j<p;j++){ans-=work(i,j,d);}}}printf("Case %d: %lld\n",ca,ans);}return 0; } /* 2 1 1 1 5 1 1 5 1 1 1 */ View Code

hdu2461?Rectangles

給你n（n很小）個(gè)長(zhǎng)方形，求這中間任意長(zhǎng)方形的面積并。容斥

tip:結(jié)構(gòu)體數(shù)組會(huì)初始化為0，結(jié)構(gòu)體變量不會(huì)初始化為0

因?yàn)檫@個(gè)tle，還以為是算法錯(cuò)了

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n,m; struct rec {int x1,y1,x2,y2; }a[30]; vector<int>v; int s[(1<<20)+10]; rec intersec(rec a, rec b) {rec c;if(a.x2<=b.x1||a.y2<=b.y1||a.x1>=b.x2||a.y1>=b.y2){c.x1=c.x2=c.y1=c.y2=0;//注意沒(méi)有交集要賦值0，否則tle，In_exclusion中停不下來(lái)！return c;}c.x1=max(a.x1,b.x1);c.y1=max(a.y1,b.y1);c.x2=min(a.x2,b.x2);c.y2=min(a.y2,b.y2);return c; } int Area(rec r) {if(r.x1>=r.x2||r.y1>=r.y2)return 0;return (r.y2-r.y1)*(r.x2-r.x1); } int In_exclusion(int k,rec r) {if(k>=v.size()||Area(r)==0){return 0;}int ret=0;for(int i=k;i<v.size();i++){rec tmp=intersec(a[v[i]],r);ret+=Area(tmp)-In_exclusion(i+1,tmp);}return ret; } int main() {rec tot;tot.x1=tot.y1=0;tot.x2=tot.y2=1000;int ca=1;while(~scanf("%d%d",&n,&m)){if(n==0&&m==0)break;printf("Case %d:\n",ca++);for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);memset(s,0,sizeof(s));//do not forget else get tlefor(int i=1;i<=m;i++){v.clear();int R;int id;scanf("%d",&R);int add=0;while(R--){scanf("%d",&id);v.push_back(id);add=add|(1<<(id-1));}if(s[add]==0)s[add]=In_exclusion(0,tot);printf("Query %d: %d\n",i,s[add]);}puts("");}return 0; } /* 3 2 0 0 2 3 1 1 4 5 0 2 3 4 2 1 2 3 1 2 3 */ View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/kylehz/p/4414333.html

總結(jié)

以上是生活随笔為你收集整理的鸽巢原理和容斥原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。