思維題都刷不動(dòng)？
比賽考驗(yàn)的不僅僅是知識面，思維能力，編碼能力，更有團(tuán)隊(duì)合作的意識以及心態(tài)。平時(shí)接觸的題目會(huì)涵蓋各個(gè)方面的內(nèi)容，我們都需要有一些適當(dāng)?shù)慕忸}技巧，在這里總結(jié)談一些比較重要的技巧或者方法的運(yùn)用：1、預(yù)處理 2、算法優(yōu)化 3、STL的運(yùn)用。
編程的技巧著實(shí)很多，小到一些基本的簡單操作比如說位運(yùn)算的運(yùn)用大到一些好的思想的應(yīng)用。任何一個(gè)技巧的應(yīng)用都可能給你的程序帶來不一般的在速度或其他方面的變化，就比如說這個(gè)位運(yùn)算符的應(yīng)用，充分利用的話時(shí)間開銷大大減小。
我也曾在一本叫做算法心得的書上看到了這個(gè)技巧，老外寫的，非常經(jīng)典，書沒有說一些我們現(xiàn)在的算法，而是說怎么利用一些簡單卻非常高效的技巧，只是那本書我實(shí)在沒有看完…感覺寫的不錯(cuò)，但我還沒有用過。
下面也有一些小技巧（在此引用，感謝這位博主）：
http://blog.sina.com.cn/s/blog_a46ca35201013c4n.html
下面進(jìn)入正題：
1、預(yù)處理
所謂預(yù)處理，顧名思義，就是事先計(jì)算好需要的值或事先處理某些東西，有時(shí)候你會(huì)發(fā)現(xiàn)你做一個(gè)題目出現(xiàn)了TLE，原因就是重復(fù)的計(jì)算會(huì)導(dǎo)致效率不高（或者說你的預(yù)處理不夠“優(yōu)雅”）。
一、直接把結(jié)果預(yù)處理：
舉幾個(gè)比較簡單的例子：
1、Xtuoj1052
Description
某一個(gè)數(shù)字集合定義如下：
1. 0屬于這個(gè)集合；
2.如果x屬于這個(gè)集合，那么2x+1,3x+1也屬于這個(gè)集合；
3.集合只包含按增序排列的前100000個(gè)元素。
集合按增序排列，根據(jù)輸入的元素序號，輸出對應(yīng)的元素值。
輸入
每行一個(gè)整數(shù)n（n<100000），表示元素的序號（從0開始記數(shù)），如果是-1，則輸入結(jié)束。
輸出
每行輸出對應(yīng)元素的值。
Sample Input
0
1
2
3
4
5
-1
Sample Output
0
1
3
4
7
9
分析：很明顯，不能也不好直接判斷是否存在于這個(gè)集合中，只需要把所有存在于這個(gè)集合中標(biāo)記，并且預(yù)處理這些元素的序號，之后輸出就行了，那么一次預(yù)處理便可以知道所有序號對應(yīng)的元素了。
#include <iostream>
#define MAX 2000001
using namespace std;
int a[100010], b[3*MAX];
int main() {
int n, i, j;
b[0] = 1;
for (i = 0; i < MAX; i++)
if (b[i] == 1) b[2*i+1] = b[3*i+1] = 1;
for (i = 0, j = 0; i < 100000; j++)
if (b[j] == 1) a[i++] = j;
while (cin >> n, n != 1) cout << a[n] << endl;
return 0;
}
2、POJ1426
點(diǎn)擊打開鏈接
題意：有k個(gè)壞人k個(gè)好人坐成一圈，前k個(gè)為好人（編號1~k），后k個(gè)為壞人(編號k+1~2k)，給定m，從編號為1的人開始報(bào)數(shù)，報(bào)到m的人就要自動(dòng)死去，之后從下一個(gè)人繼續(xù) 開始新一輪的報(bào)數(shù)。問當(dāng)m為什么值時(shí)，k個(gè)壞人會(huì)在好人死亡之前全部死掉？
分析：遇到存在環(huán)的題目的時(shí)候，可以直接直線化處理。當(dāng)然也可以直接利用循環(huán)鏈表或者數(shù)組進(jìn)行環(huán)的模擬，不過這樣的程序?qū)懫饋碛悬c(diǎn)復(fù)雜。
這個(gè)題目直接暴力模擬求解必定TLE，需要一點(diǎn)數(shù)學(xué)的知識，這在里就不詳細(xì)說了，即使這樣，還是會(huì)超時(shí)，正確的方法便是預(yù)處理出僅有的14個(gè)答案，但既然已經(jīng)知道了所有答案，而且又只有14個(gè)，那么直接把答案交上去就行了。
#include <cstdio>
int ans[15] = {0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881, 13482720};
int main() {
int n;
while (scanf("%d", &n), n) printf("%d\n", ans[n]);
return 0;
}
3、uva12716
點(diǎn)擊打開鏈接
題意：給定一個(gè)整數(shù)n，求出有多少對整數(shù)a,b滿足1<=b<=a<=n且gcd(a,b)=a XOR b.
分析：最容易想到的方法是枚舉a，b，雙重循環(huán)加上求gcd，總復(fù)雜度為O(n*n*logn),絕對無法承受。如何減少枚舉呢？注意到亦或運(yùn)算的性質(zhì)，如果a^b=c,那么a^c=b,既然c為a，b的最大公約數(shù)的話，那么我們可以從枚舉a和c出發(fā)，那么就是枚舉所有因子c及其可能的倍數(shù)a，和素?cái)?shù)篩法一樣，這樣復(fù)雜度為O(nlogn*logn),n最大為30000000，復(fù)雜度還是有點(diǎn)高，怎么減少復(fù)雜度呢？這就要通過一點(diǎn)數(shù)學(xué)知識或者找規(guī)律發(fā)現(xiàn)了，通過打印出所有滿足條件的a,b,c可以發(fā)現(xiàn)a+b=c，所以可以將復(fù)雜度降為O(n*logn)，但是題目是多樣例輸入，如果每次都需要O(n*logn)計(jì)算答案的話，還是會(huì)超時(shí)，觀察便可得知其實(shí)在計(jì)算n以內(nèi)滿足條件的a，b對數(shù)時(shí)比n小的數(shù)以內(nèi)的對數(shù)都已經(jīng)計(jì)算出來了，也就是說不需要重復(fù)計(jì)算了，那么我們可以通過一次預(yù)處理，在計(jì)算的過程中統(tǒng)計(jì)每個(gè)a組合時(shí)的對數(shù)，之后循環(huán)遍歷一次全部加起來就可以知道每個(gè)n以內(nèi)的答案了。
代碼：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 30000000;
int a[N+5];
void pretreat() {
for (int i = 1; i <= 15000000; i++) {
for (int j = i<<1; j <= N; j += i) {
if ((j ^ (j-i)) == i) a[j]++;
}
}
for (int i = 2; i <= N; i++) a[i] += a[i-1];
}
int main() {
pretreat();
int t, ca = 0;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("Case %d: %d\n", ++ca, a[n]);
}
return 0;
}
二、把需要用的預(yù)處理
比較常見的基本就是三個(gè)：預(yù)處理素?cái)?shù)、預(yù)處理組合數(shù)、預(yù)處理前綴和。
首先舉個(gè)比較經(jīng)典的例子：素?cái)?shù)打表
判斷是否素?cái)?shù)有3種方式：O(sqrt(n)的簡單素性測試、埃氏篩法，以及Miller_Rabin 算法進(jìn)行素?cái)?shù)測試。
如果需要進(jìn)行大量的用到素?cái)?shù)或者判斷素?cái)?shù)，則可以埃氏篩法打表出所有的素?cái)?shù)。
1、xtuoj1237
Description
題目描述
如果n和n+2都是素?cái)?shù)，我們稱其為孿生素?cái)?shù)，比如3和5，5和7都是孿生素?cái)?shù)。給你一個(gè)區(qū)間[a,b],請問期間有多少對孿生素?cái)?shù)？
輸入
第一行是一個(gè)整數(shù)K(K≤ 10000)，表示樣例的個(gè)數(shù)。以后每行一個(gè)樣例，為兩個(gè)整數(shù)，a和b，1≤a≤b≤5000000。
輸出
每行輸出一個(gè)樣例的結(jié)果。
樣例輸入
5
1 3
1 10
1 100
1 1000
1 5000000
樣例輸出
0
2
8
35
32463
分析：計(jì)算區(qū)間內(nèi)個(gè)數(shù)的題目一般滿足區(qū)間減法性質(zhì)，但是不能一概而論，具體題目具體分析，就像這題一對孿生素?cái)?shù)是跨越了3個(gè)數(shù)，要分情況考慮。
首先直接標(biāo)記出所有的素?cái)?shù)，令g[x]為1到x+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對數(shù)，要統(tǒng)計(jì)出數(shù)量，遍歷一次即可，只需要一次預(yù)處理就可以計(jì)算出所有的g[x],之后便可以O(shè)(1)計(jì)算出所有1到x+2這個(gè)區(qū)間內(nèi)孿生素?cái)?shù)的對數(shù)了。
如果輸入的區(qū)間長度小于2，那么必定沒有，如果長度大于2，稍加思考便可以得知答案即為g[b-2]-g[a-1]。
#include <cstdio>
#include <cmath>
const int N = 5000001;
int f[N], g[N];
int main() {
int up = sqrt(N);
for (int i = 2; i <= up; i++)
if(!f[i]) for (int j = i*i; j <= N; j += i) f[j] = 1;
for (int i = 3; i < N-1; i += 2)
g[i+1] = g[i] = g[i-1] + !(f[i]|| f[i+2]);
int t;
scanf("%d", &t);
while (t--) {
int a, b;
scanf("%d %d", &a, &b);
b-a < 2 ? puts("0") : printf("%d\n", g[b-2] -g[a-1]);
}
return 0;
}
2、CF231CTo Add or Not to Add
點(diǎn)擊打開鏈接
題意：給定一個(gè)數(shù)組，每次可以給任意元素加1，這樣的操作不能超過k次，求操作不超過k次后數(shù)組中一個(gè)數(shù)能夠出現(xiàn)的最多次數(shù)，以及能夠以這個(gè)次數(shù)出現(xiàn)的最小的數(shù)。
分析：這個(gè)題目明顯具有單調(diào)性，這樣的話就可以進(jìn)行二分搜索求取最大次數(shù)了。怎么判斷假定的解是否可行呢？既然只能是加1，而且又不超過k次，那么首先將數(shù)組排序，假設(shè)搜索的次數(shù)為m，那么i從第m個(gè)數(shù)循環(huán)到最后一個(gè)數(shù)，只要滿足了次數(shù)不小于k就立即退出循環(huán)，這樣找到的便一定是出現(xiàn)m次的最小的數(shù)，但是這個(gè)判斷的過程就是第m個(gè)數(shù)與其之前的m-1個(gè)數(shù)的差之和要不大于k，如果每次都直接加上差進(jìn)行判斷必定超時(shí)，因?yàn)槎炙阉骷友h(huán)判斷的時(shí)間復(fù)雜度太高，那么最好的優(yōu)化就是直接之前預(yù)處理，求出第1個(gè)數(shù)到第m個(gè)數(shù)區(qū)間的和，后面判斷的時(shí)候直接就是o（1）計(jì)算區(qū)間的和了。
代碼如下：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 100010;
LL a[N], sum[N];
int main() {
int n; LL k;
while (~scanf("%d %I64d", &n, &k)) {
for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
sort(a + 1, a + 1+n);
int r = INF, l = 0;
sum[1] = a[1];
for (int i = 2; i <= n; i++) sum[i] = a[i] + sum[i-1];
LL ans;
while (r - l > 1) {
int m = (r+l) / 2;
if (m > n) { r = m; continue; }
int flag = 0;
for (int i = m; i <= n; i++) {
if ((m-1)*a[i] - sum[i-1] +sum[i-m] <= k){
flag = 1; ans = a[i];
break;
}
}
flag ? l = m : r = m;
}
printf("%d %I64d\n", l, ans);
}
return 0;
}
三、關(guān)于預(yù)處理的總結(jié)：
預(yù)處理的目的是為了減少重復(fù)的計(jì)算從而減少時(shí)間復(fù)雜度，有時(shí)一個(gè)簡單的預(yù)處理能使得算法性能顯著提高。首先我們可以按思路直接寫一個(gè)程序，如果復(fù)雜度太大，那么算法的優(yōu)化可以從這個(gè)過程出發(fā)，思考可以對哪個(gè)算法的部分進(jìn)行改進(jìn)，而預(yù)處理便是一種對應(yīng)的非常重要的技巧。像預(yù)處理區(qū)間和便是非常常見的，而且正如上面所示的幾個(gè)題一樣，一次預(yù)處理出全部的答案也是很常見的，要注意思考每個(gè)部分的聯(lián)系。
2、算法優(yōu)化：
其實(shí)不知道該怎么給這個(gè)技巧取名字，算法優(yōu)化涵蓋的范圍很廣，優(yōu)化的地方可以有很多，所以總結(jié)也不可能全面，就針對自己遇到的一些題來總結(jié)下吧，像上面的預(yù)處理技巧其實(shí)也算是算法優(yōu)化的一部分，只不過覺得很重要，所以特別分開了。
分為3個(gè)部分：
1、減少冗余計(jì)算。2、減少計(jì)算量。3、優(yōu)化計(jì)算過程。
(1)、減少冗余計(jì)算
1、Codeforces659F-Polycarp and Hay
點(diǎn)擊打開鏈接
題意：給定一個(gè)矩陣，每個(gè)格子有一個(gè)數(shù)字，操作是改變格子中的數(shù)字，使其變小，操作后的矩陣必須滿足以下要求：所有格子中的數(shù)字和為k，非零格子中的數(shù)字要相同，至少一個(gè)格子要保留為原來的數(shù)字不變化，所有格子必須聯(lián)通，聯(lián)通是指所有非零格子都可以通過非零格子到達(dá)。
分析：很容易想到搜索來解決。剛開始的思路是，對于k的某一個(gè)約數(shù)d，如果格子中存在數(shù)字d且大于等于d的數(shù)字的個(gè)數(shù)如果大于等于k/di個(gè)的話，那么開始進(jìn)行搜索并判斷是否滿足條件，滿足條件就把上一次走過的的格子全部變?yōu)閐，其他全部變?yōu)?即可。具體是從正反開始枚舉k的每一個(gè)因子然后重復(fù)上述過程，但各種優(yōu)化之后最終還是超時(shí)了，跑到了第57個(gè)樣例，發(fā)現(xiàn)方法選取有問題，首先需要枚舉每一個(gè)可行的因子，每次枚舉都需要遍歷所有格子，這樣時(shí)間復(fù)雜度過高。
其實(shí)可以換種方式：直接一次遍歷原圖即可，對于格子中的某一數(shù)字d，如果它是k的因子的話，那么直接從此開始搜索，判斷是否滿足條件，這樣優(yōu)化之后復(fù)雜度明顯改善，但最后還是超時(shí)了，到了第95個(gè)test，但是這只是一個(gè)最直接的處理，算法的優(yōu)化是無盡的，很重要的一點(diǎn)就是減少冗余，這樣便除去了大量的重復(fù)過程，如果每個(gè)處理的過程不是常數(shù)時(shí)間的話，那么這個(gè)優(yōu)化對于時(shí)間復(fù)雜度的改善是明顯的！！！回到此題，明顯對于某一個(gè)數(shù)字d，如果搜索完所有可以到達(dá)的格子仍然后不符合條件的話，那么這個(gè)過程所有與d相等的格子無需在進(jìn)行搜索處理，標(biāo)記即可，因?yàn)檫@些格子也必定不符合條件。
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1010;
LL k, di, tab[N][N];
int n, m, flag = 1, tot, cnt, sum;
int vis[N][N], v[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void DFS(int x, int y) {
if (tab[x][y] == di) v[x][y] = 1;//標(biāo)記數(shù)字相等的格子
vis[x][y] = sum;
if (++cnt == tot) { flag = 0; return ; }
if (flag) {
for (int i = 0; i < 4 && flag; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] == sum) continue;
if (tab[nx][ny] >= di) DFS(nx, ny);
}
}
}
int main() {
scanf("%d %d %I64d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%I64d", &tab[i][j]);
LL t = k/n/m;
for (int i = 1; i <= n && flag; i++) {
for (int j = 1; j <= m && flag; j++) {
di = tab[i][j];
if (k % di == 0 && di >= t && !v[i][j]) {
cnt = 0; sum++;
tot = k/tab[i][j];
DFS(i, j);
}
}
}
if (flag) puts("NO");
else {
puts("YES");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) printf("%I64d ", vis[i][j] == sum ? di : 0);
puts("");
}
}
return 0;
}
2、HDU5510-Bazinga
點(diǎn)擊打開鏈接
題意：給定n個(gè)字符串，分別s1、s2…..sn，找出最大的i，使得存在一個(gè)j(1<=j<i)使得sj不是si的子串。
分析：題目數(shù)據(jù)量很大，最多500個(gè)字符串，而且長度可以達(dá)到2000，然后最后50個(gè)樣例，估算下可知就算是使用kmp算法，直接暴力也必定超時(shí)，但是這種題沒有什么其他的高效解法，只能暴力，那么我們需要從優(yōu)化算法的角度入手。其實(shí)只要稍加優(yōu)化就能過了。
如果逆著枚舉所有i的話，那么無法優(yōu)化，最壞情況下還是會(huì)枚舉完所有的i，肯定也會(huì)超時(shí)，順著枚舉i然后減少重復(fù)的判斷就可以了。可以知道，如果一個(gè)串i是另一個(gè)串j的子串的話，那么在枚舉時(shí)對于串i便無需在進(jìn)行匹配了，只需要與j匹配即可，這題出題人肯定也是考察這一點(diǎn)，想想看，對于串的匹配，通常的算法是o(n^2),對于串i，如果前面的串中很多都是i的子串的如果不用判斷的話會(huì)減少大量的時(shí)間消耗大的重復(fù)判斷過程。
不過值得一提的是使用strstr，或者search居然會(huì)比kmp快了近一倍，雖說一般這兩個(gè)函數(shù)是平方的，但在實(shí)際應(yīng)用中一般比kmp快，但是這種大量的匹配過程為何還會(huì)快且快這么多呢？
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[510][2010];
int main() {
int t, k = 0;
int vis[510];
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%s", s[i]);
int ans = -1;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (!vis[j]) {
int leni = strlen(s[i]);
if (search(s[i], s[i]+leni, s[j], s[j]+strlen(s[j])) == s[i]+leni) { ans = i; break; }
else vis[j] = 1;
}
}
}
printf("Case #%d: %d\n", ++k, ans);
}
return 0;
}
(2)、減少計(jì)算量
1、uva10976- Fractions Again?!
點(diǎn)擊打開鏈接
題意：給定正整數(shù)k，找到所有的正整數(shù)x>=y使得1/k=1/x+1/y，并且輸出所有的式子。
分析：暴力枚舉即可，但是枚舉量多大呢？如果枚舉x，推導(dǎo)可知最優(yōu)也要從k*(k+1）枚舉到2*k，太大了，明顯不可取，但是如果從枚舉y出發(fā)，可以知道y<=2*k，枚舉量大大減小，效率足夠高了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int, int> p;
p ans[10000];
int main()
{
int n;
while (~scanf("%d", &n)){
int k = 0;
for (int i = 2*n; i >= n+1; i--){
int j = n*i/(i-n);
if (j*(i-n) == n*i && j >= 2*n && j <= n*(n+1)) ans[k++] = p(j, i);
}
printf("%d\n", k);
for (int i = k-1; i >= 0; i--) printf("1/%d = 1/%d + 1/%d\n", n, ans[i].first, ans[i].second);
}
return 0;
}
2、Hdu5128 - The E-pangPalace
點(diǎn)擊打開鏈接
題意：給定n個(gè)點(diǎn)，要求從這n個(gè)點(diǎn)當(dāng)中選擇8個(gè)點(diǎn)作為頂點(diǎn)來構(gòu)成2個(gè)不相交(不能有任何一個(gè)點(diǎn)公共)的矩形，如果無法選出兩個(gè)這樣的矩形的話輸出imp，否則輸出這兩個(gè)矩形的最大的面積和。
分析：最容易想到的就是預(yù)處理出所有的矩形，假設(shè)有n個(gè)矩形，之后n*n跑一遍，但這樣可能達(dá)到C(30,4)*C(30,4)的復(fù)雜度，會(huì)超時(shí)。其實(shí)沒必要，類似于折半枚舉(雙向搜索)的思想，只要枚舉矩形的兩個(gè)對角點(diǎn)即兩個(gè)點(diǎn)就行了，然后判斷另外兩個(gè)點(diǎn)是否存在即可。所以枚舉量最多只有C(30,4)了。而且判斷兩個(gè)矩形是否相交的話我們不需要分類出所有的情況，從反面考慮，如果一個(gè)矩形在另一個(gè)矩形的上方或者左方或者下方或者右方的話就說明不相交了。而且另外一點(diǎn)是，對于一個(gè)矩形，我們只需要枚舉一次對角頂點(diǎn)的組合，另外一個(gè)組合沒必要枚舉，這樣減少了很多不必要的枚舉。而且對于選出的4個(gè)點(diǎn)，按照x從左從左至右排列假設(shè)為a,b,c,d四個(gè)點(diǎn)的話，只有3種組合方式(a,b)與(c,d),(a,c)與(b,d),(a,d)與(b,c)，全部枚舉一下就好了。為方便判斷，可以事先給坐標(biāo)排序，之后枚舉所有大小為4的子集，并且每次對3種組合方式判斷一下取最大值。
這題的一個(gè)坑點(diǎn)：一個(gè)矩形可能完全包含在另一個(gè)矩形中，這種情況下面積取較大者，否則取和。
暴力枚舉不失為一種好辦法，但是過多的枚舉必然會(huì)導(dǎo)致效率低下了。所以下手之前可以分析下，看是否可以減少重復(fù)的沒必要的枚舉，而且有時(shí)候減少這些枚舉還可以保證正確率，就像這題如果枚舉矩形的兩個(gè)對角的組合的話可能會(huì)導(dǎo)致判斷不全面導(dǎo)致計(jì)算錯(cuò)誤，之前做的時(shí)候就是這樣，發(fā)現(xiàn)答案變大了，原因是因?yàn)榭紤]不全面，但是其實(shí)是沒必要的。而且折半枚舉也是一種重要的思想，因?yàn)楹芏嗲闆r下只需要枚舉一部分量，然后另一部分量直接判斷或者進(jìn)行查找就好了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
struct po{
int x, y;
bool operator < (const po& a) const{
return x == a.x ? y < a.y : x < a.x;
}
}p[50];
int vis[210][210];
int check(int i, int j, int k, int l)
{
int ix = p[i].x, iy = p[i].y, jx = p[j].x, jy = p[j].y;
int kx = p[k].x, ky = p[k].y, lx = p[l].x, ly = p[l].y;
if (ix == jx || iy >= jy || kx == lx || ky >= ly) return 0;
if (!vis[ix][jy] || !vis[jx][iy] || !vis[kx][ly] || !vis[lx][ky]) return 0;
if (jx < kx || ix > lx || jy < ky || iy > ly) return (jx - ix) * (jy - iy) + (lx - kx) * (ly - ky);
if (ix < kx && kx < jx && ix < lx && lx < jx && iy < ky && ky < jy && iy < ly && ly < jy) return (jx - ix) * (jy - iy);
return 0;
}
int solve(int i, int j, int k, int l)
{
return max(check(i, j, k, l), max(check(i, k, j, l), check(i, l, j, k)));
}
int main()
{
int n;
while (scanf("%d", &n), n){
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y), vis[p[i].x][p[i].y] = 1;
if (n < 8) { puts("imp"); continue; }
sort(p, p + n);
int k = (1 << 4) - 1;
int ans = 0;
while (k < 1 << n){
int t[4];
for (int i = 0, j = 0; i < n; i++)
if (k & (1 << i)) t[j++] = i;
ans = max(ans, solve(t[0], t[1], t[2], t[3]));
int x = k & -k, y = k + x;
k = ((k & ~y) / x >> 1) | y;
}
ans ? printf("%d\n", ans) : puts("imp");
}
return 0;
}
(3)、優(yōu)化計(jì)算過程
在此舉一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法的優(yōu)化的例子：
1、codeforces675E Trains and Statistic
點(diǎn)擊打開鏈接
題意：一個(gè)城市有n個(gè)車站，編號從1到n，在第i號車站只能買到第i+1號到ai號車站的票(ai>=i+1),令P(i,j)為從第i號車站去第j號車站所需要買的最少的票的數(shù)量，給定ai，求所有的P(i,j)之和(1<=i<j<=n).
分析：看起來像圖論題，但是無法存儲(chǔ)，考慮其他方法。無后效性，明顯的動(dòng)態(tài)規(guī)劃，令dp[i]為從i號車站去之后i+1到n這些車站的總票數(shù)最小數(shù)量，可以知道需要逆推，狀態(tài)轉(zhuǎn)移即為dp[i] = dp[pos]+n-i-(a[i]-pos),pos為i+1到a[i]這些車站中a[pos]最大的一個(gè)編號，知道了狀態(tài)轉(zhuǎn)移還不行，因?yàn)樾枰写罅坑?jì)算區(qū)間最大值的過程，使用線段樹優(yōu)化即可。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010;
int id[N<<2], a[N];
LL dp[N], ans;
void update(int root) {
if (a[id[root<<1]] > a[id[root<<1|1]]) id[root] = id[root<<1];
else id[root] = id[root<<1|1];
}
void build(int root, int l, int r) {
if (l == r) { id[root] = l; return ; }
int t = (r-l) / 2;
build(root<<1, l, l + t);
build(root<<1|1, l + t+1, r);
update(root);
}
int query(int l, int r, int L, int R, int root) {
if (l > R || r < L) return -1;
if (l <= L && R <= r) return id[root];
int idls, idrs, t = (R-L) / 2;
idls = query(l, r, L, L + t, root<<1);
idrs = query(l, r, L + t+1, R, root<<1|1);
if (idls == -1) return idrs;
if (idrs == -1) return idls;
if (a[idls] > a[idrs]) return idls;
return idrs;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) scanf("%d", a+i);
a[n] = n; ans = dp[n-1] = 1;
build(1, 1, n);
for (int i = n-2; i >= 1; i--) {
int pos = query(i+1, a[i], 1, n, 1);
dp[i] = dp[pos] + n-i - a[i]-pos;
ans += dp[i];
}
printf("%I64d\n", ans);
return 0;
}
算法優(yōu)化的總結(jié)：
程序時(shí)間復(fù)雜度過高，除了換更優(yōu)的算法之外，優(yōu)化當(dāng)前的算法也是很重要的。就像上面說明的那樣：減少當(dāng)前計(jì)算過程中的冗余計(jì)算，比如說標(biāo)記，刪除、從減少計(jì)算量出發(fā)優(yōu)化，比如說部分枚舉，折半枚舉、或者優(yōu)化某個(gè) 計(jì)算的過程，比如說數(shù)據(jù)結(jié)構(gòu)優(yōu)化。算法優(yōu)化思想或者技巧需要知識的積累和對算法過程進(jìn)行的仔細(xì)分析，難以總結(jié)全面。要想熟練運(yùn)用，還得不斷地鍛煉和總結(jié)。
3、 STL的高效運(yùn)用：
不管你是一個(gè)ACM競賽者還是一個(gè)開發(fā)程序員，STL都會(huì)是一個(gè)非常好的工具。如果能夠充分地利用STL，可以在代碼空間、執(zhí)行時(shí)間和編碼效率上獲得極大的好處，代碼不僅高效簡潔而且看起來特別舒服。
首先粗略介紹下STL：
STL 大致可以分為三大類：算法(algorithm)、容器(Container)、迭代器(iterator)。
STL 容器是一些模板類，提供了多種組織數(shù)據(jù)的常用方法，例如vector(向量，類似于數(shù)組)、list(列表，類似于鏈表)、deque(雙向隊(duì)列)、set(集合)、map(映射)、stack(棧)queue(隊(duì)列)、priority_queue(優(yōu)先隊(duì)列)等，
通過模板的參數(shù)我們可以指定容器中的元素類型。
STL 算法是一些模板函數(shù)，提供了相當(dāng)多的有用算法和操作，從簡單如for_each（遍歷）到復(fù)雜如stable_sort（穩(wěn)定排序）。STL 迭代器是對C 中的指針的一般化，用來將算法和容器聯(lián)系起來。幾乎所有的STL 算法都是通過迭代器來存取元素序列進(jìn)行工作的，而STL 中的每一個(gè)容器也都定義了其本身所專有的迭代器，用以存取容器中的元素。有趣的是，普通的指針也可以像迭代器一樣工作。熟悉了STL 后，你會(huì)發(fā)現(xiàn)，很多功能只需要用短短的幾行就可以實(shí)現(xiàn)了。通過STL，我們可以構(gòu)造出優(yōu)雅而且高效的代碼，甚至比你自己手工實(shí)現(xiàn)的代碼效果還要好。
STL 的另外一個(gè)特點(diǎn)是，它是以源碼方式免費(fèi)提供的，程序員不僅可以自由地使用這些代碼，也可以學(xué)習(xí)其源碼，甚至按照自己的需要去修改它。
在這里首先例舉ACM經(jīng)常需要用到的STL容器或算法：
STl容器或適配器等：pair、list、vector、priority_queue、set、map、stack
常用STL 算法庫：sort快速排序算法、二分查找算法、枚舉排列算法 .
在這里只介紹下應(yīng)用，如果想知道這個(gè)容器的具體操作可以去看書或者找度娘，這里不詳細(xì)介紹操作了.
①、容器或適配器部分：
1、 pair
相當(dāng)于一個(gè)Struct，訪問方式舉個(gè)例子：pair<int,int> p; 那么第一個(gè)成員便是p.first、第二個(gè)p.second,pair使用起來很方便，簡單快速高效，可以當(dāng)做一個(gè)二元struct使用，而且它定義了比較的方法，先根據(jù)第一個(gè)成員比較，在根據(jù)第二個(gè)，所以如果你的比較運(yùn)算符是這樣，那么你就不需要定義比較函數(shù)了，而struct是不能直接進(jìn)行比較的,構(gòu)造pair的方法：make_pair。
下面是一個(gè)簡單的例子：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <functional>
using namespace std;
const int N = 1010;
typedef pair<int, int> p;
p a[N];
int main() {
int k = 0;
a[k++] = p(3, 4);
a[k++] = p(3, 100);
a[k++] = p(1, 2);
a[k++] = p(4, 10);
//首先按第一個(gè)成員從大到小排列，當(dāng)?shù)谝粋€(gè)成員相等時(shí)，按第二個(gè)成員second從大到小排列
sort(a, a+k, greater<p>());
for (int i = 0; i < k; i++) printf("%d %d\n", a[i].first, a[i].second);
return 0;
}
2、List
list是一個(gè)循環(huán)鏈表，其實(shí)我并不經(jīng)常使用。關(guān)鍵在于這個(gè)容器的特點(diǎn)：快速插入和刪除。作用和vector差不多，但內(nèi)部是用鏈表實(shí)現(xiàn)。
這個(gè)容器不支持隨機(jī)訪問，你不能[]或者利用通用算法操作，比如說要排序的話你只能利用成員函數(shù)比如list.sort()，而且很重要的一點(diǎn)，list的size()函數(shù)是線性的，因?yàn)槭且员闅v函數(shù)distance實(shí)現(xiàn)的。
下面的這個(gè)題便可以用list的O(1)插入和刪除特性暴力解決，簡直是神技般的存在!
Hdu5127-Dogs' Candies
點(diǎn)擊打開鏈接
題意：一個(gè)以兩個(gè)數(shù)字p，q作為單個(gè)元素的序列，支持三種操作：
1、 從序列中去掉包含p，q的這兩個(gè)數(shù)字的元素。
2、向序列中添加包含p，q的這兩個(gè)數(shù)字的元素。
3、對于給定的x和y，找到一對p，q，使得px+qy最大，輸出這個(gè)最大值。
分析：這題雖然數(shù)據(jù)量比較大，但是卻可以暴力解決，據(jù)說現(xiàn)場賽時(shí)只有10個(gè)隊(duì)伍過了此題，正解很麻煩，cdq分治+凸包，然而我全都不會(huì)…..首先抓住這題的一個(gè)特性，題目可能存在大量的插入和刪除操作，而且對于尋找最大值的操作，只能循環(huán)遍歷一次，不存在貪心的選取策略能使得枚舉量減少。如果采取不刪除，而直接進(jìn)行標(biāo)記的策略便會(huì)超時(shí)，因?yàn)檫@樣會(huì)使得遍歷的時(shí)間增加。
根據(jù)以上的分析，抓住題目的特征，選取合適的方法，選用list作為容器來存儲(chǔ)。運(yùn)行時(shí)間不到時(shí)限的一半，簡直神奇，如果選取其他的容器也都會(huì)超時(shí)。也許這就是傳說中的暴力姿勢比較好吧….
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <list>
#include <utility>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> p;
list<p> l;
int main() {
int n;
while (scanf("%d", &n), n) {
l.clear();
for (int i = 0; i < n; i++) {
LL a, b;
int t;
scanf("%d %I64d %I64d", &t, &a, &b);
if (t == 1) l.push_back(p(a, b));
else if (t == -1) l.erase(find(l.begin(), l.end(), p(a, b)));
else {
list<p>::iterator i = l.begin();
LL ans = i->first * a + i->second * b;
for (++i; i != l.end(); i++) ans = max(ans, i->first * a + i->second * b);
printf("%I64d\n", ans);
}
}
}
return 0;
}
3、vector
可以說這是一個(gè)STL的神器，相當(dāng)于一個(gè)不定長數(shù)組，利用這個(gè)你可以添加任意多的元素，容器以連續(xù)數(shù)組的方式存儲(chǔ)元素序列，可以將vector 看作是以順序結(jié)構(gòu)實(shí)現(xiàn)的線性表。當(dāng)我們在程序中需要使用動(dòng)態(tài)數(shù)組時(shí)，vector將是一個(gè)理想的選擇。這個(gè)完全相當(dāng)于把一個(gè)數(shù)組當(dāng)成一個(gè)元素來進(jìn)行使用了，可以直接相等，賦值操作等。
在這里介紹幾個(gè)比較經(jīng)典的使用：
1、利用vector防止遞歸爆棧。2、利用vector來實(shí)現(xiàn)鄰接表（通常是vector<int>G[N]，但這種方式可能會(huì)因?yàn)榇鎯?chǔ)量巨大然后vector的容量擴(kuò)展導(dǎo)致TLE）3、利用vector存儲(chǔ)空間占用比較大的矩陣。
vector高效的原因在于配置了比其所容納的元素更多的內(nèi)存，但其內(nèi)存重新配置會(huì)花很多時(shí)間，（在這里順便說下，像new和malloc等函數(shù)要慎用，這屬于用時(shí)間開銷代價(jià)換取空間的舉措，非常容易TLE），vector確實(shí)非常好用，合理使用實(shí)則幫助很大。
Vector算是應(yīng)用得最多的一個(gè)stl容器了，例子太多了，在此就不舉了.....
4、priority_queue:
這個(gè)也可以說是一個(gè)神器，優(yōu)先隊(duì)列其實(shí)就是堆，在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時(shí)，具有最高優(yōu)先級的元素最先被刪除。優(yōu)先隊(duì)列具有最高級先出（first in, largest out）的行為特征。在這里說下這個(gè)怎么進(jìn)行重載的問題。
兩種方式：
一、直接在struct或者class內(nèi)部定義，那么你定義時(shí)直接指明元素類型就好了，因?yàn)槟闶嵌x了比較函數(shù)的。二、定義比較結(jié)構(gòu)。
//內(nèi)部定義：
struct node{
int x, y;
node(int x = 0, int y = 0) : x(x), y(y) {}
bool operator < (const node &a) const { return x > a.x; }
};
priority_queue<node> q;
//定義比較結(jié)構(gòu)
struct node{
int x, y;
node(int x = 0, int y = 0) : x(x), y(y) {}
};
struct cmp {
bool operator () (const node &a, const node &b) { return a.x< b.x; }
};
priority_queue<node, vector<node>,cmp> q;
具體點(diǎn)就是可以用來貪心或者加速搜索，下面是對應(yīng)的兩個(gè)題：
(1)、貪心
優(yōu)先隊(duì)列最常用的就是貪心，舉個(gè)例子。
poj2010-Moo University - Financial Aid
點(diǎn)擊打開鏈接
題意：有c只奶牛，現(xiàn)在要招募n只進(jìn)動(dòng)物學(xué)校，第i只奶牛的分?jǐn)?shù)為si,需要的資金幫助為ai,現(xiàn)在有總共為f的資金，問招募到的n只奶牛中中位數(shù)最大是多少？
分析：采取貪心策略，盡量選擇大的，首先按分?jǐn)?shù)從小到大排個(gè)序，之后從大到小枚舉中位數(shù)，所以我們要知道當(dāng)前分?jǐn)?shù)作為中位數(shù)下，需要的資金總和最小是多少。令l[i]表示選取第i+1號奶牛作為中位數(shù)時(shí)分?jǐn)?shù)比它小的n/2頭奶牛需要的資金幫助的最小值，令r[i]表示選取第i-1號奶牛作為中位數(shù)時(shí)分?jǐn)?shù)比它大的n/2頭奶牛需要的資金幫助的最小值。遍歷時(shí)用優(yōu)先隊(duì)列存儲(chǔ)當(dāng)前的分?jǐn)?shù)，貪心地?fù)Q掉需要的資金多的奶牛，一次預(yù)處理r[i]和l[i]即可，總的時(shí)間復(fù)雜度為O(nlogn)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int l[N], r[N];
struct calf {
int s, a;
}ca[N];
bool cmp(calf x, calf y) { return x.s < y.s; }
int main() {
int n, c, f;
scanf("%d %d %d", &n, &c, &f);
for (int i = 1; i <= c; i++) scanf("%d %d", &ca[i].s, &ca[i].a);
sort(ca+1, ca+1+c, cmp);
n >>= 1;
priority_queue <int> q;
int sum = 0;
for (int i = 1; i <= n; i++) q.push(ca[i].a), sum += ca[i].a;
l[n] = sum;
for (int i = n+1; i <= c-n-1; i++) {
if (ca[i].a >= q.top()) l[i] = sum;
else {
sum -= q.top() - ca[i].a;
q.pop(); q.push(ca[i].a);
l[i] = sum;
}
}
sum = 0;
while (!q.empty()) q.pop();
for (int i = c; i >= c-n+1; i--) q.push(ca[i].a), sum += ca[i].a;
r[c-n+1] = sum;
for (int i = c-n; i >= n+2; i--) {
if (ca[i].a >= q.top()) r[i] = sum;
else {
sum -= q.top() - ca[i].a;
q.pop(); q.push(ca[i].a);
r[i] = sum;
}
}
int ans = -1;
for (int i = c-n; i >= n+1; i--) {
if (r[i+1] + l[i-1] + ca[i].a <= f) {
ans = ca[i].s;
break;
}
}
printf("%d\n", ans);
return 0;
}
(2)、加速搜索
csu1780 - 簡單的圖論問題
點(diǎn)擊打開鏈接
這題很明顯屬于搜索題，bfs廣搜即可，但是需要找到權(quán)值最小的路徑的話，那么我們需要使用優(yōu)先隊(duì)列來加速搜索和求解答案。每一步優(yōu)先選擇權(quán)值小的結(jié)點(diǎn)來拓展?fàn)顟B(tài)，且結(jié)點(diǎn)中記錄上一次擴(kuò)展?fàn)顟B(tài)時(shí)的方向，而且給一個(gè)點(diǎn)標(biāo)記去重的需要考慮四個(gè)方向的狀態(tài)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
struct po{
int x, y, w, di;
bool operator > (const po &a)const {return w > a.w;}
};
int n, m, vis[505][505], v[505][505][4];
int maze[510][510], r1, c1, r2, c2, t;
char st[5];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int bfs()
{
priority_queue <po, vector<po>, greater<po> > q;
q.push((po){r1, c1, maze[r1][c1], 0});
memset(vis, 0, sizeof(vis));
vis[r1][c1] = 1;
while (!q.empty()){
po t = q.top(); q.pop();
if (t.x==r2 && t.y==c2) return t.w;
for (int i = 0; i < 4; i++){
int nx = t.x+dx[i], ny = t.y+dy[i];
if (nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || maze[nx][ny]==-1) continue;
q.push((po){nx, ny, t.w+maze[nx][ny], 0}); vis[nx][ny] = 1;
}
}
return -1;
}
int bfs1()
{
memset(v, 0, sizeof(v));
priority_queue <po, vector<po>, greater<po> > q;
q.push((po){r1, c1, maze[r1][c1], -1});
v[r1][c1][0] = v[r1][c1][1] = v[r1][c1][2] = v[r1][c1][3] = 1;
while(!q.empty()){
po t = q.top(); q.pop();
if (t.x==r2 && t.y==c2) return t.w;
for(int i = 0;i < 4;i ++){
if(i == t.di) continue;
int nx = t.x+dx[i], ny = t.y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>m || v[nx][ny][i] || maze[nx][ny]==-1) continue;
q.push((po){nx, ny, t.w+maze[nx][ny], i}); v[nx][ny][i] = 1;
}
}
return -1;
}
int main()
{
while (~scanf("%d %d %d %d %d %d", &n, &m, &r1, &c1, &r2, &c2)){
memset(maze, -1, sizeof(maze));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j){
scanf("%s", st);
if (st[0] != '*') sscanf(st, "%d", &maze[i][j]);
}
printf("Case %d: %d %d\n", ++t, bfs(), bfs1());
}
return 0;
}
5、set：
set，顧名思義，集合，無重復(fù)元素，插入的元素自動(dòng)按增序排列。
內(nèi)部實(shí)現(xiàn): 紅黑樹，一種平衡的二叉排序樹，其Compare 函數(shù)，類似于qsort 函數(shù)里的那個(gè)Compare 函數(shù)，作為紅黑樹在內(nèi)部實(shí)現(xiàn)的比較方式。
在這里說下一些成員函數(shù)的時(shí)間復(fù)雜度：
insert() O(logn)、erase()O(logn)、find()O(logn)
lower_bound()O(logn) 查找第一個(gè)不小于k 的元素
upper_bound()O(logn) 查找第一個(gè)大于k 的元素
equal_range()O(logn) 以pair形式返回lower_bound和upper_bound，在需要確定一個(gè)增序序列中某一段都是某一值的情況下是非常有效的，這比通用算法更有效。
容器最主要的功能就是判重,也可以進(jìn)行二分查找。
要允許重復(fù)元素，選用multiset即可。
容器性能：set與map的查找、刪除、插入性能都是對數(shù)復(fù)雜度。
沒有定義比較方式的元素需要進(jìn)行重載，重載方式和優(yōu)先隊(duì)列一樣。
判重是set的一個(gè)最常見的使用。
Uva11572- Unique Snowflakes
點(diǎn)擊打開鏈接
題意：給定一個(gè)長度為n序列A，找到一個(gè)最長的連續(xù)子序列，使得這個(gè)序列中沒有相同的元素。
分析：經(jīng)典的O(n)尺取法，實(shí)現(xiàn)過程中需要判斷當(dāng)前的右端點(diǎn)元素是否存在，利用set判斷即可。s.find(x) != s.end()和s.count(x)都可以。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
int a[1000001];
set<int> s;
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", a+i);
s.clear();
int st = 0, en = 0, ma = 0;
while (en < n) {
while (en < n && !s.count(a[en])) s.insert(a[en++]);
ma = max(ma, en-st);
s.erase(a[st++]);
}
printf("%d\n", ma);
}
return 0;
}
6、map
這個(gè)容器也非常好，和set差不多，pair 組成的紅黑樹（所以比較方式和pair一樣），成員函數(shù)復(fù)雜度和前者一樣，在這里就不贅述了，容器適用于那些需要進(jìn)行映射（可以根據(jù)Key找到對應(yīng)的Value，作為hash還是不錯(cuò)的），因此map是關(guān)聯(lián)數(shù)組。
要允許重復(fù)元素，使用multimap。
在這里指出：在C++11里,有unoder和hash的map和set,里面的元素沒有順序.速度比普通的set和map快了很多，但是需要自己重載hash
map最常見的應(yīng)用就是進(jìn)行映射。
hdu4460 - Friend Chains
點(diǎn)擊打開鏈接
題意：給定n個(gè)人的名字和這n個(gè)人之間的朋友關(guān)系，間接相連也算是朋友，如果兩個(gè)人之間通過n個(gè)人相連，那么這條朋友鏈的長度即為n-1.求一個(gè)最小的k，使得對任意兩個(gè)人，他們之間的朋友鏈的長度不會(huì)超過k。
分析：明顯是求任意兩點(diǎn)之間的最短路，把那個(gè)最大的距離找到即可，但是給定的是名字，需要進(jìn)行映射，用map映射為標(biāo)號即可。而且這題的邊的權(quán)值為1，不需要用優(yōu)先隊(duì)列，用普通隊(duì)列即可。值得注意的是，不需要進(jìn)行n次bfs求取最短路，只需要進(jìn)行兩次。首先選取一個(gè)點(diǎn)x進(jìn)行最短路的求解，之后找到離x距離最大的那個(gè)點(diǎn)y在進(jìn)行一次最短路的求解即可。因?yàn)榈谝淮巫疃搪房隙〞?huì)求得整個(gè)圖中離圖的重心點(diǎn)最遠(yuǎn)的那個(gè)點(diǎn)，也就是說處于整個(gè)圖的最端點(diǎn)。那么之后從這個(gè)點(diǎn)出發(fā)求得的最短路距離必定是整個(gè)圖中任意兩點(diǎn)之間距離的最大值。
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
const int N = 1010;
int vis[N], d[N];
map <string, int> mp;
vector<int> G[N];
int solve(int x, int n) {
int ma = 0, res, cnt = 1;
queue<int> q; q.push(x);
memset(vis+1, 0, sizeof(int) * (n+1));
memset(d+1, 0, sizeof(int) * (n+1));
vis[x] = 1;
while (!q.empty()) {
int t = q.front(); q.pop();
for (int i = 0; i < G[t].size(); i++) {
int y = G[t][i];
if (vis[y]) continue;
vis[y] = 1;
d[y] = d[t] + 1;
if (ma < d[y]) res = y, ma = d[y];
q.push(y); cnt++;
}
}
return cnt != n ? -1 : x == 1 ? res: ma;
}
int main() {
int n;
while (scanf("%d", &n), n) {
mp.clear();
for (int i = 1; i <= n; i++) G[i].clear();
char s[15], str[15];
for (int i = 1; i <= n; i++) scanf("%s", s), mp[s] = i;
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%s %s", s, str);
G[mp[s]].push_back(mp[str]);
G[mp[str]].push_back(mp[s]);
}
int ans = solve(1, n);
ans == -1 ? puts("-1") : printf("%d\n", solve(ans, n));
}
return 0;
}
7、stack：
stack，棧在STL里面它屬于容器適配器，對容器的重新包裝，后進(jìn)先出結(jié)構(gòu)。
經(jīng)典使用：單調(diào)棧的實(shí)現(xiàn)。
poj2559 - Largest Rectangle in a Histogram
點(diǎn)擊打開鏈接
題意：給定一個(gè)柱狀圖，由n個(gè)寬為1，長為hi的矩形從左至右依次排列組成，求里面包含的長方形的最大面積是多少？
分析：如果預(yù)處理一次區(qū)間最小值，暴力也要O（n^2),無法承受，換一種方式，我們可以枚舉每個(gè)h[i]，求以當(dāng)前高度作為長度的矩形的最大面積，所以需要做的就是對于固定的h[i]，求出左端點(diǎn)L和右端點(diǎn)R，必定有h[L-1]<h[i]和h[R]<h[i],否則總可以更新左右端點(diǎn)，令l[i]為(j<=i且h[j-1]<h[i]的最大的j),r[i]為(j>i且h[j]<h[i]的最小的j). 怎么計(jì)算l[i]和r[i]. 思考下就可以知道可以利用棧解決。
考慮計(jì)算l[i]的情況，棧中維護(hù)的是高度依次減小的標(biāo)號，也就是如果棧中從上到下的值依次為i，那么i>i+1且h[i]>h[i+1]。對于當(dāng)前的高度h[i]，如果有棧頂?shù)脑豩[k]>=h[i]，證明左端點(diǎn)可以一直往左移動(dòng)，不斷地取出棧頂元素，如果棧為空了證明可以移動(dòng)到最左邊，也就是l[i]=0,否則h[i]=j+1。之所以利用棧求解，是因?yàn)槊看味家〉米筮叺谝粋€(gè)高度小的端點(diǎn)和右邊第一個(gè)高度小的端點(diǎn)。這樣符合后進(jìn)先出的性質(zhì)，模擬下棧的工作情況便可以明白了。正反兩次預(yù)處理就可以計(jì)算出l和r了，之后遍歷一次高度求取最大值。
這樣的棧稱為單調(diào)棧，和單調(diào)隊(duì)列是類似的。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 100010;
stack<int> s;
template <class T>
inline void read(T &res) {
char c; res = 0;
while (!isdigit(c = getchar()));
while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
}
int l[N], r[N];
LL h[N];
int main() {
int n;
while (read(n), n) {
for (int i = 0; i < n; i++) read(h[i]);
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.empty() && h[s.top()] >= h[i]) s.pop();
l[i] = s.empty() ? 0 : s.top()+1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n-1; i >= 0; i--) {
while (!s.empty() && h[s.top()] >= h[i]) s.pop();
r[i] = s.empty() ? n : s.top();
s.push(i);
}
LL ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, (LL)h[i] * (r[i] - l[i]));
printf("%I64d\n", ans);
}
return 0;
}
② 、算法庫
主要的頭文件就是#include <algorithm>
1、 sort排序系列：
sort：對給定區(qū)間所有元素進(jìn)行排序（全排）
stable_sort ：對給定區(qū)間所有元素進(jìn)行穩(wěn)定排序，就是相等的元素位置不變，原來在前面的還在前面。
partial_sort ：對給定區(qū)間所有元素部分排序，就是找出你指定的數(shù)目最小或最大的值放在最前面或最后面，比如說我只要找到1000000個(gè)數(shù)中最大的五個(gè)數(shù)，那你用這個(gè)函數(shù)是最好的，排序后最大的五個(gè)數(shù)就在最前面的五個(gè)位置，其他的元素位置分布不確定。
partial_sort_copy：對給定區(qū)間復(fù)制并排序，和上面的一樣，只是這是指定區(qū)間進(jìn)行復(fù)制然后排序的。
nth_element ：找出給定區(qū)間的某個(gè)位置對應(yīng)的元素，根據(jù)比較函數(shù)找到第n個(gè)最大（小）元素，適用于尋找“第n個(gè)元素”。
is_sorted ：判斷一個(gè)區(qū)間是否已經(jīng)排好序（返回bool值判斷是否已排序）
partition ：使得符合某個(gè)條件的元素放在前面，劃分區(qū)間函數(shù)，將 [first, last)中所有滿足的元素置于不滿足的元素前面，這個(gè)函數(shù)會(huì)返回迭代器，設(shè)返回的迭代器為 i，則對 [first, i)中的任意迭代器 j，*j滿足給定的判斷，對 [i, last) 中的任意迭代器 k，*k不滿足。
stable_partition ：相對穩(wěn)定的使得符合某個(gè)條件的元素放在前面（和上面的一樣，只是位置不變）
這個(gè)函數(shù)真是絕對的神助，相比qsort沒這么麻煩了。使用時(shí)根據(jù)需要選擇合理的排序函數(shù)即可，所有的排序函數(shù)默認(rèn)從小到大排序，可以定義自己的比較方式。
sort排序十分常見，在此舉個(gè)其他排序的例子：
xtu1050-第K個(gè)數(shù)
Description
給你一個(gè)整數(shù)序列和若干個(gè)問題，問題是這個(gè)序列的第i個(gè)元素到第j個(gè)元素的片斷中的第k大數(shù)是什么？比如說給你的序列為（1, 5, 2, 6, 3, 7, 4），問題是（2，5，3），則從第2個(gè)元素到第5個(gè)元素為（5，2，6，3），排序以后是（2，3，5，6），則第三個(gè)數(shù)是5。
輸入：
第一行為兩個(gè)整數(shù)n，m（1 <= n <= 100 000, 1 <= m <= 5 000），表示序列的元素個(gè)數(shù)和問題的個(gè)數(shù)，第二行為n個(gè)正整數(shù)的序列，每個(gè)整數(shù)為一個(gè)32位整數(shù)，兩個(gè)數(shù)之間有一個(gè)空格隔開。以后m行為問題，每個(gè)問題由三個(gè)整數(shù)表示i，j，k，第i個(gè)元素到第j個(gè)元素的片斷中的第k大數(shù)是什么？（元素序號從1開始計(jì)數(shù),i<=j,1<=k<=j-i+1）
輸出：
每行輸出對應(yīng)問題的結(jié)果。
Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3
分析：只需要選擇第k個(gè)數(shù)，直接nth_element，線性復(fù)雜度暴力水過………而且這題解法很多，比如用線段樹等數(shù)據(jù)結(jié)構(gòu)進(jìn)行求解會(huì)是更優(yōu)的。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100010];
int b[100010];
int main()
{
int n, t, i, j, k;
scanf("%d %d", &n, &t);
for (i = 1; i <= n; i++) scanf("%d", &a[i]);
while (t--)
{
copy(a+1, a+n+1, b+1);
scanf("%d %d %d", &i, &j, &k);
nth_element(b+i, b+i+k-1, b+j+1);
printf("%d\n", b[i+k-1]);
}
return 0;
}
2、 二分系列：
二分檢索，復(fù)雜度O(log(last-first))
itr =upper_bound(first, last, value, cmp);
//itr 指向大于value 的第一個(gè)值(或容器末尾)
itr = lower_bound(first, last, value, cmp);
//itr 指向不小于valude 的第一個(gè)值(或容器末尾)
pairequal_range(first, last, value, cmp);
//找出等于value 的值的范圍O(2*log(last– first))
Binary_search(first,last, value)返回bool值，找到則true，否則false。
二分經(jīng)常會(huì)與其他算法結(jié)合，二分的應(yīng)用是也是十分常見的，在這舉個(gè)例子說明下找一個(gè)數(shù)或等于一個(gè)數(shù)的一個(gè)范圍的二分應(yīng)用：
hdu1496-Equations
點(diǎn)擊打開鏈接
題意：給定a，b，c，d四個(gè)數(shù)，求有多少對x1，x2，x3，x4滿a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
分析：暴力會(huì)超時(shí)，把a(bǔ)x1*x1+bx2*x2打表，利用二分查找，排序之后equal_range尋找等于這個(gè)值的范圍就行了。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int val[40010];
int main() {
pair <int*, int*> p;
int a, b, c, d;
while (cin >> a >> b >> c >> d) {
if( (a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0)){
cout << 0 << endl;
continue;
}
memset(val, 0, sizeof(val));
int k = 0;
for (int i = -100; i <= 100; i++){
if (i == 0) continue;
for (int j = -100; j <= 100; j++) {
if (j == 0) continue;
val[k++] = a*i*i + b*j*j;
}
}
sort(val, val+k);
int cnt = 0;
for (int j = -100; j <= 100; j++) {
if (j == 0) continue;
for (int i = -100; i <= 100; i++) {
if (i == 0) continue;
int sum = c*j*j + d*i*i;
p = equal_range(val, val+k, -sum);
cnt += p.second - p.first;
}
}
cout << cnt << endl;
}
return 0;
}
利用二分查找時(shí)間復(fù)雜度降到了o（n*nlog（n））。當(dāng)然這個(gè)題目可以hash，這是最好的辦法，O(1)查找，復(fù)雜度更小了。
3、 排列系列：
這兩個(gè)函數(shù)都可以用來枚舉字典序排列，那種水題直接用這個(gè)就解決了。
在這里貼個(gè)網(wǎng)址，看了下，說的挺好的；
http://blog.sina.com.cn/s/blog_9f7ea4390101101u.html
4、 常用函數(shù)：
最后補(bǔ)充下常用函數(shù)，//其實(shí)是我常用的函數(shù)...
copy函數(shù)，直接拷貝，比for循環(huán)高效，最壞為線性復(fù)雜度，而且這個(gè)可以說是一個(gè)copy族函數(shù)，還有類似的滿足一定條件的copy函數(shù)如copy_if等。
find、find_i：查找第一個(gè)匹配的值或第一個(gè)滿足函數(shù)使其為true的值位置，沒有返回指定區(qū)間的末尾，線性復(fù)雜度，還有一些不怎么常用的find族函數(shù)就不多介紹了。
count、count_if： 返回匹配或使函數(shù)為true的值的個(gè)數(shù)，線性復(fù)雜度。
search，這是尋找序列是否存在于另一個(gè)序列中的函數(shù)，挺好用的，某些簡單的尋找公共子串的題就可以這樣寫，時(shí)間復(fù)雜度二次。
reverse，翻轉(zhuǎn)一個(gè)區(qū)間的值，我經(jīng)常遇到需要這種題，直接reverse了，不需要for循環(huán)了，主要是方便。
for_each:直接對一個(gè)區(qū)間內(nèi)的每個(gè)元素執(zhí)行后面的函數(shù)操作，寫起來簡單。
max、min、max_element、min_element:尋找兩個(gè)數(shù)或者一個(gè)區(qū)間的最大最小值，都可以添加比較函數(shù)參數(shù)。
集合操作函數(shù)：includes、set_union、set_difference、set_intersection、set_symmetric_difference、前面這些函數(shù)的最差復(fù)雜度為線性，另外附加一個(gè)序列的操作函數(shù)merge，相當(dāng)于歸并排序中的合并函數(shù)，時(shí)間復(fù)雜度為線性，注意這些函數(shù)的操作對象都必須是升序的。
這里舉個(gè)例子：
#include<cstdio>
#include<algorithm>
using namespace std;
void out(int a) { if (a != -1) printf("%d ",a); }
int main() {
int a[5] = {1, 8, 10, 52, 100};
int b[5] = {6, 8, 9, 10, 1000};
int c[20];
printf("a集合為：");
for_each(a, a+5, out);
puts("");
printf("b集合為：");
for_each(b, b+5, out);
puts("");
//判斷b是否是a的子集。
if(includes(a, a+5, b, b+5)) printf("bis a sub set of a\n");
//合并兩個(gè)有序序列，必須為合并后的序列分配空間，否則程序會(huì)崩潰。
printf("兩個(gè)集合的合并序列為：");
merge(a, a+5, b, b+5, c);
for_each(c, c+10, out);
puts("");
//求兩個(gè)集合的并集。
fill(c, c+20, -1);
set_union(a, a+5, b, b+5, c);
printf("兩個(gè)集合的并集為：");
for_each(c, c+10, out);
puts("");
//求兩個(gè)集合的交集。
fill(c, c+20, -1);
set_intersection(a, a+5, b, b+5, c);
printf("兩個(gè)集合的交集為：");
for_each(c, c+10, out);
puts("");
//求兩個(gè)集合的差集，這里為a-b。
fill(c, c+20, -1);
set_difference(a, a+5, b, b+5, c);
printf("a-b的差集為：");
for_each(c, c+10, out);
puts("");
//求兩個(gè)集合的差集，這里為b-a。
fill(c, c+20, -1);
set_difference(b, b+5, a, a+5, c);
printf("b-a的差集為：");
for_each(c, c+10, out);
puts("");
//求兩個(gè)集合的對稱差
set_symmetric_difference(a, a+5, b, b+5,c);
printf("兩個(gè)集合的對稱差為：");
for_each(c, c+10, out);
puts("");
return 0;
}
下面的這個(gè)題便說明了STL的方便與實(shí)用：
codeforces730A - Toda2
點(diǎn)擊打開鏈接
題意：有n個(gè)人，每個(gè)人有一個(gè)rating，目的是使得每個(gè)人的rating相同而且盡可能的大，每次可以選取2到5個(gè)人，使得每個(gè)人的rating減1，如果rating已經(jīng)為0了，那么不減少，輸出你的操作過程的每一步，每一步為一個(gè)01序列，如果選擇了第i個(gè)人，那么序列中第i位為1。
分析：模擬題，不過比較麻煩，為方便起見，利用STL實(shí)現(xiàn)，思路是每次選取兩到三個(gè)人進(jìn)行rating的減小，然后每次選取rating較大的幾個(gè)人減少就行了，如果r全部相等就可以了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
struct p{
int r, id;
p(int r = 0, int id = 0) : r(r), id(id) {}
bool operator <(const p &x)const { return r > x.r; }
};
vector<string> ans;
multiset<p> s;
int main() {
ios::sync_with_stdio(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int r;
cin >> r;
s.insert(p(r, i));
}
while (s.begin()->r != s.rbegin()->r){
string t(n, '0');
int num = 2;
if(s.count(*s.begin()) == 3) num++;
vector<p> tmp;
for (int i = 1; i <= num; i++) {
p a = *s.begin();
s.erase(s.begin());
t[a.id] = '1';
if (a.r) a.r--;
tmp.push_back(a);
}
s.insert(tmp.begin(), tmp.end());
ans.push_back(t);
}
cout << s.begin()->r << "\n" << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) cout << ans[i] << "\n";
return 0;
}
③ 、STL使用的總結(jié)：
STl不失為一種絕佳工具，合理的使用是一種很好的技巧，但是需要指出不要過分依賴于STL，STL里面函數(shù)確實(shí)多的你幾乎每個(gè)操作都有函數(shù)代替，寫起來又簡單。但凡是都有利弊，STl不好的一個(gè)地方就是如果碰到某些卡時(shí)間、卡空間、各種卡的題目，那些函數(shù)的效率問題就大打折扣了，一般手寫的效率會(huì)高。
1、STL的容器如queue還有很多函數(shù)都比較慢，在碰到那些數(shù)據(jù)量大的題目時(shí)效率確實(shí)不高，很容易超時(shí)，poj1426 BFS水題吧，用STl容器queue各種超時(shí)，一直想不明白，后面自己寫個(gè)queue，直接就32ms AC了，通過這個(gè)也更加體會(huì)到這一點(diǎn)（最致命的一點(diǎn)）
2、STL封裝了大量的數(shù)據(jù)結(jié)構(gòu)和算法，使用起來一定需要注意，STl容器的操作都是建立在迭代器之上的，迭代器的使用也需要注意，不然各種問題，程序崩潰…
3、STL算法極其多，大致分為搜索、修改、排序、集合與工具等，每一種類中的算法都比較多，有助于我們快速地完成程序設(shè)計(jì)。
4、使用STL容器時(shí)注意使用自帶的成員函數(shù)要比通用算法高效很多。
5、STL的算法思想是非常值得借鑒的，你可以去查看以學(xué)習(xí)。
6、STL也是存在缺點(diǎn)的，沒有提供任何泛型的圖或樹結(jié)構(gòu)，只能自己實(shí)現(xiàn)。
