算法竞赛入门与进阶 （一）枚举
??枚舉
1.關鍵點：不重復不遺漏2.優化：把多余的操作去掉
例一：
在一個N*N(N<=100)矩陣中求一個最大的正方形使得該正方形的四個頂點都是有字符“#”構成。?
#*#***
******
#*#*#*
******
#*****
***#**
hint：
1.兩個點確定一個正方形，然后判斷其余兩個點是否為“#”
2.三個點確定一個矩形，若矩形邊平行于坐標軸，則只需要兩個點
例二：
給定長度為n的整數數列{Ai}，找出兩個整數ai和aj（i<j），使得ai-aj盡量大
例三：
給定長度為n的整數數列以及整數S，求出總和不小于S的連續子串的長度的最小值，如果解不存在，輸出0.
poj3061 尺取法（追逐法）
#include<iostream> using namespace std; int a[100005]; int main() {ios::sync_with_stdio(false);int t;cin>>t; while(t--){int n,s;cin>>n>>s;for(int i=0;i<n;i++){cin>>a[i]; }int sum=0,l=0,re=0x7f7f7f7f;for(int i=0;i<n;i++){sum+=a[i];if(sum>=s){while(sum>=s){sum-=a[l];l++;}re=min(re,i-l+2);} }if(l==0)cout<<0<<endl;elsecout<<re<<endl;}return 0; }變型1：
圓圈舞蹈
【問題描述】
?? ? 熊大媽的奶牛在時針的帶領下，圍成了一個圓圈跳舞。由于沒有嚴格的教育，奶牛們之間的間隔不一致。
????? 奶牛想知道兩只最遠的奶牛到底隔了多遠。奶牛A到B的距離為A順時針走和逆時針走，到達B的較短路程。告訴你相鄰兩個奶牛間的距離，請你告訴奶牛兩只最遠的奶牛
到底隔了多遠。
【輸入】
???? 第一行一個整數N，表示有N只奶牛。(2≤N≤100000)
???? 接下來2～N+1行，第I行有一個數，表示第I-1頭奶牛順時針到第I頭奶牛的距離。(1≤距離≤maxlongint，距離和≤maxlongint)
????? 第N+l行的數表示第N頭奶牛順時針到第1頭奶牛的距離。
【輸出】
???? 一行，表示最大距離。
【樣例】
Circle.in
5
1
2
3
4
5
Circle.out
7
【樣例解析】
????? Circle.out所有奶牛I到J之間的距離和到達方式（順為順時針，逆為逆時針）如下：
| ?I\J | 1 | 2 | 3 | 4 | 5 |
| 1 | O | 1?(順) | 3(順) | 6（順） | 5（逆） |
| 2 | 1（逆） | O | 2（順） | 5（順） | 6（逆） |
| 3 | 3（逆） | 2（逆） | 0 | 3（順） | 7（順） |
| 4 | 6（逆） | 5（逆） | 3（逆） | 0 | 4(順) |
| 5 | 5（順） | 6（順） | 7（逆） | 4（逆） | 0 |
所以，最遠的兩頭奶牛為3到5，距離是7。
解法：1.枚舉每一個點，直到找到一個大于園的一半周長的點
2.總長度減去剛找到的長度，進行比較，然后選小的
3.求出每頭奶牛與他相離最遠奶牛的距離：
求兩頭：1頭順時針最大的
1頭逆時針最大的
#include<bits/stdc++.h> using namespace std; int n; int a[100005]; int c=0;//記錄園的周長 int ans=0;//記錄答案 void work() {int sum=0,k=0;//sum記錄長度 for(int i=1;i<=n;i++){sum+=a[i-1];if(sum>c/2){k=i;break;}} int q=min(sum,abs(c-sum));//該點選擇的最短路int q1=min(sum-a[k-1],abs(c-(sum-a[k-1])));ans=max(q,q1);//以上為二分 for(int i=1;i<=n;i++){sum-=a[i-1];while(sum<=c/2){sum+=a[k+1];k++;} ans=max(ans,abs(c-sum));ans=max(ans,min(sum-a[k-1],abs(c-(sum-a[k-1]))));}cout<<ans<<endl; } int main() {ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];c+=a[i];}work();return 0; }變型2：
小明喜歡收集卡片，他要去商店購買新到的卡片。
商店出售的卡片有N張，是連續的，小明只能購買連續的一段，
這一串卡片共有M種，每種卡片都有一個價格，小明拿的錢數為 V，
他想知道如何用花最少的錢來集齊所有種類的卡片。
N<=1000000 ，M<=2000 ，Ti<=2000 ,? V<=10^9
輸入第1行 三個正整數 N，M，V，
第2行共M個正整數，第i個數Ti表示第i種卡片的價格，
第3行 N個正整數，表示第i個卡片是哪一類。
輸出小明還剩多少錢
樣例輸入
5 2 20
10 5
1 1 2 2 1
樣例輸出
5?
#include<bits/stdc++.h> using namespace std; int M[2005],N[1000005];int n,m;long long v; int kind[2005];int main() {ios::sync_with_stdio(false);while(cin>>n>>m>>v){for(int i=1;i<=m;i++)cin>>M[i];for(int j=0;j<n;j++)cin>>N[j];fill(kind,kind+2005,0);long long sum= 0;int r,l=0;for(r=0;r<n;r++){sum+=M[N[r]];kind[N[r]]++;if(kind[N[l]]>1){//cout<<"yes"<<endl;while(kind[N[l]]>1){sum-=M[N[l]];kind[N[l]]--;l++;}} }//cout<<l<<" "<<r<<endl;if(l==0)cout<<v<<endl;else{cout<<v-sum<<endl;}}return 0;}變型3：
/* 有N個數的數列，M次操作，每次對一個區間[Li,Ri]加上一個值Xi 問M次操作之后，每個數的值。 */ #include<bits/stdc++.h> using namespace std; int n,m; int a[100005]; int main() {ios::sync_with_stdio(false);while(cin>>n&&n){fill(a,a+100005,0);for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=0;i<m;i++){int l,r,x;cin>>l>>r>>x;a[l]+=x;a[r+1]-=x;}for(int i=1;i<n;i++)cout<<a[i-1]+a[i]<<" ";cout<<a[n-1]+a[n]<<endl;}return 0; }變型4：UVA 11020
有n個人，每個人有兩個屬性x，y，如果對于一個人P（x，y），不存在另外一個人(a，b)，使得a<x, b <= y 或者 a < = x, b < y,?則這個人是有優勢的。動態插入每個人，?要求統計當前已經插入的人中，有優勢的人的個數。 #include<bits/stdc++.h> using namespace std; struct ty{int x,y;bool operator < (const ty & a) const {return x<a.x||(x==a.x&&y<a.y);} }; multiset <ty> st; int n; int main() {ios::sync_with_stdio(false);int t;cin>>t; for(int ka=1;ka<=t;ka++){cin>>n;st.clear();for(int i=1;i<=n;i++){int x,y;cin>>x>>y;ty p;p.x=x;p.y=y;multiset <ty>::iterator it=st.lower_bound(p);if(it==st.begin()||(--it)->y>y)st.insert(p);it=st.upper_bound(p);while(it!=st.end()&&it->y>=y)st.erase(it++);}cout<<st.size()<<endl;}return 0; }
總結
以上是生活随笔為你收集整理的算法竞赛入门与进阶 （一）枚举的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： bzoj 1225 暴搜动态规划
- 下一篇： poj2002 STL set