比賽考驗的不僅僅是知識面，思維能力，編碼能力，更有團隊合作的意識以及心態。平時接觸的題目會涵蓋各個方面的內容，我們都需要有一些適當的解題技巧，在這裡總結談一些比較重要的技巧或者方法的運用：1、預處理 2、演算法最佳化 3、STL的運用。

 

程式設計的技巧著實很多，小到一些基本的簡單操作比如說位運算的運用大到一些好的思想的應用。任何一個技巧的應用都可能給你的程式帶來不一般的在速度或其他方面的變化，就比如說這個位運算子的應用，充分利用的話時間開銷大大減小。

我也曾在一本叫做演算法心得的書上看到了這個技巧，老外寫的，非常經典，書沒有說一些我們現在的演算法，而是說怎麼利用一些簡單卻非常高效的技巧，只是那本書我實在沒有看完…感覺寫的不錯，但我還沒有用過。

 

下面也有一些小技巧（在此引用，感謝這位博主）：

http://blog.sina.com.cn/s/blog_a46ca35201013c4n.html

 

下面進入正題：

1、預處理

所謂預處理，顧名思義，就是事先計算好需要的值或事先處理某些東西，有時候你會發現你做一個題目出現了TLE，原因就是重複的計算會導致效率不高（或者說你的預處理不夠“優雅”）。

一、直接把結果預處理：

舉幾個比較簡單的例子：

1、Xtuoj1052

Description

某一個數字集合定義如下：

1. 0屬於這個集合；

2.如果x屬於這個集合，那麼2x+1,3x+1也屬於這個集合；

3.集合只包含按增序排列的前100000個元素。

集合按增序排列，根據輸入的元素序號，輸出對應的元素值。

輸入

每行一個整數n（n<100000），表示元素的序號（從0開始記數），如果是-1，則輸入結束。

輸出

每行輸出對應元素的值。

Sample Input

0

1

2

3

4

5

-1

Sample Output

0

1

3

4

7

9

分析：很明顯，不能也不好直接判斷是否存在於這個集合中，只需要把所有存在於這個集合中標記，並且預處理這些元素的序號，之後輸出就行了，那麼一次預處理便可以知道所有序號對應的元素了。

#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

題意：有k個壞人k個好人坐成一圈，前k個為好人（編號1~k），後k個為壞人(編號k+1~2k)，給定m，從編號為1的人開始報數，報到m的人就要自動死去，之後從下一個人繼續 開始新一輪的報數。問當m為什麼值時，k個壞人會在好人死亡之前全部死掉？

分析：遇到存在環的題目的時候，可以直接直線化處理。當然也可以直接利用迴圈連結串列或者陣列進行環的模擬，不過這樣的程式寫起來有點複雜。

這個題目直接暴力模擬求解必定TLE，需要一點數學的知識，這在裡就不詳細說了，即使這樣，還是會超時，正確的方法便是預處理出僅有的14個答案，但既然已經知道了所有答案，而且又只有14個，那麼直接把答案交上去就行了。

#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

題意：給定一個整數n，求出有多少對整數a,b滿足1<=b<=a<=n且gcd(a,b)=a XOR b.

分析：最容易想到的方法是列舉a，b，雙重迴圈加上求gcd，總複雜度為O(n*n*logn),絕對無法承受。如何減少列舉呢？注意到亦或運算的性質，如果a^b=c,那麼a^c=b,既然c為a，b的最大公約數的話，那麼我們可以從列舉a和c出發，那麼就是列舉所有因子c及其可能的倍數a，和素數篩法一樣，這樣複雜度為O(nlogn*logn),n最大為30000000，複雜度還是有點高，怎麼減少複雜度呢？這就要透過一點數學知識或者找規律發現了，透過打印出所有滿足條件的a,b,c可以發現a+b=c，所以可以將複雜度降為O(n*logn)，但是題目是多樣例輸入，如果每次都需要O(n*logn)計算答案的話，還是會超時，觀察便可得知其實在計算n以內滿足條件的a，b對數時比n小的數以內的對數都已經計算出來了，也就是說不需要重複計算了，那麼我們可以透過一次預處理，在計算的過程中統計每個a組合時的對數，之後迴圈遍歷一次全部加起來就可以知道每個n以內的答案了。

程式碼：

#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;

}

二、把需要用的預處理

比較常見的基本就是三個：預處理素數、預處理組合數、預處理字首和。

首先舉個比較經典的例子：素數打表

判斷是否素數有3種方式：O(sqrt(n)的簡單素性測試、埃氏篩法，以及Miller_Rabin 演算法進行素數測試。

如果需要進行大量的用到素數或者判斷素數，則可以埃氏篩法打表出所有的素數。

1、xtuoj1237

Description

題目描述

如果n和n+2都是素數，我們稱其為孿生素數，比如3和5，5和7都是孿生素數。給你一個區間[a,b],請問期間有多少對孿生素數？

輸入

第一行是一個整數K(K≤ 10000)，表示樣例的個數。以後每行一個樣例，為兩個整數，a和b，1≤a≤b≤5000000。

輸出

每行輸出一個樣例的結果。

樣例輸入

5

1 3

1 10

1 100

1 1000

1 5000000

樣例輸出

0

2

8

35

32463

分析：計算區間內個數的題目一般滿足區間減法性質，但是不能一概而論，具體題目具體分析，就像這題一對孿生素數是跨越了3個數，要分情況考慮。

首先直接標記出所有的素數，令g[x]為1到x+2這個區間內孿生素數的對數，要統計出數量，遍歷一次即可，只需要一次預處理就可以計算出所有的g[x],之後便可以O(1)計算出所有1到x+2這個區間內孿生素數的對數了。

如果輸入的區間長度小於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

題意：給定一個數組，每次可以給任意元素加1，這樣的操作不能超過k次，求操作不超過k次後陣列中一個數能夠出現的最多次數，以及能夠以這個次數出現的最小的數。

分析：這個題目明顯具有單調性，這樣的話就可以進行二分搜尋求取最大次數了。怎麼判斷假定的解是否可行呢？既然只能是加1，而且又不超過k次，那麼首先將陣列排序，假設搜尋的次數為m，那麼i從第m個數迴圈到最後一個數，只要滿足了次數不小於k就立即退出迴圈，這樣找到的便一定是出現m次的最小的數，但是這個判斷的過程就是第m個數與其之前的m-1個數的差之和要不大於k，如果每次都直接加上差進行判斷必定超時，因為二分搜尋加迴圈判斷的時間複雜度太高，那麼最好的最佳化就是直接之前預處理，求出第1個數到第m個數區間的和，後面判斷的時候直接就是o（1）計算區間的和了。

 

程式碼如下：

#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;

}

三、關於預處理的總結：

預處理的目的是為了減少重複的計算從而減少時間複雜度，有時一個簡單的預處理能使得演算法效能顯著提高。首先我們可以按思路直接寫一個程式，如果複雜度太大，那麼演算法的最佳化可以從這個過程出發，思考可以對哪個演算法的部分進行改進，而預處理便是一種對應的非常重要的技巧。像預處理區間和便是非常常見的，而且正如上面所示的幾個題一樣，一次預處理出全部的答案也是很常見的，要注意思考每個部分的聯絡。

2、演算法最佳化：

其實不知道該怎麼給這個技巧取名字，演算法最佳化涵蓋的範圍很廣，最佳化的地方可以有很多，所以總結也不可能全面，就針對自己遇到的一些題來總結下吧，像上面的預處理技巧其實也算是演算法最佳化的一部分，只不過覺得很重要，所以特別分開了。

分為3個部分：

1、減少冗餘計算。2、減少計算量。3、最佳化計算過程。

(1)、減少冗餘計算

1、Codeforces659F-Polycarp and Hay

題意：給定一個矩陣，每個格子有一個數字，操作是改變格子中的數字，使其變小，操作後的矩陣必須滿足以下要求：所有格子中的數字和為k，非零格子中的數字要相同，至少一個格子要保留為原來的數字不變化，所有格子必須聯通，聯通是指所有非零格子都可以透過非零格子到達。

分析：很容易想到搜尋來解決。剛開始的思路是，對於k的某一個約數d，如果格子中存在數字d且大於等於d的數字的個數如果大於等於k/di個的話，那麼開始進行搜尋並判斷是否滿足條件，滿足條件就把上一次走過的的格子全部變為d，其他全部變為0即可。具體是從正反開始列舉k的每一個因子然後重複上述過程，但各種最佳化之後最終還是超時了，跑到了第57個樣例，發現方法選取有問題，首先需要列舉每一個可行的因子，每次列舉都需要遍歷所有格子，這樣時間複雜度過高。

其實可以換種方式：直接一次遍歷原圖即可，對於格子中的某一數字d，如果它是k的因子的話，那麼直接從此開始搜尋，判斷是否滿足條件，這樣最佳化之後複雜度明顯改善，但最後還是超時了，到了第95個test，但是這只是一個最直接的處理，演算法的最佳化是無盡的，很重要的一點就是減少冗餘，這樣便除去了大量的重複過程，如果每個處理的過程不是常數時間的話，那麼這個最佳化對於時間複雜度的改善是明顯的！！！回到此題，明顯對於某一個數字d，如果搜尋完所有可以到達的格子仍然後不符合條件的話，那麼這個過程所有與d相等的格子無需在進行搜尋處理，標記即可，因為這些格子也必定不符合條件。

 

#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;//標記數字相等的格子

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

題意：給定n個字串，分別s1、s2…..sn，找出最大的i，使得存在一個j(1<=j<i)使得sj不是si的子串。

分析：題目資料量很大，最多500個字串，而且長度可以達到2000，然後最後50個樣例，估算下可知就算是使用kmp演算法，直接暴力也必定超時，但是這種題沒有什麼其他的高效解法，只能暴力，那麼我們需要從最佳化演算法的角度入手。其實只要稍加最佳化就能過了。

如果逆著列舉所有i的話，那麼無法最佳化，最壞情況下還是會列舉完所有的i，肯定也會超時，順著列舉i然後減少重複的判斷就可以了。可以知道，如果一個串i是另一個串j的子串的話，那麼在列舉時對於串i便無需在進行匹配了，只需要與j匹配即可，這題出題人肯定也是考察這一點，想想看，對於串的匹配，通常的演算法是o(n^2),對於串i，如果前面的串中很多都是i的子串的如果不用判斷的話會減少大量的時間消耗大的重複判斷過程。

 不過值得一提的是使用strstr，或者search居然會比kmp快了近一倍，雖說一般這兩個函式是平方的，但在實際應用中一般比kmp快，但是這種大量的匹配過程為何還會快且快這麼多呢？

#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)、減少計算量

1、uva10976- Fractions Again?!

題意：給定正整數k，找到所有的正整數x>=y使得1/k=1/x+1/y，並且輸出所有的式子。

分析：暴力列舉即可，但是列舉量多大呢？如果列舉x，推導可知最優也要從k*(k+1）列舉到2*k，太大了，明顯不可取，但是如果從列舉y出發，可以知道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

題意：給定n個點，要求從這n個點當中選擇8個點作為頂點來構成2個不相交(不能有任何一個點公共)的矩形，如果無法選出兩個這樣的矩形的話輸出imp，否則輸出這兩個矩形的最大的面積和。

分析：最容易想到的就是預處理出所有的矩形，假設有n個矩形，之後n*n跑一遍，但這樣可能達到C(30,4)*C(30,4)的複雜度，會超時。其實沒必要，類似於折半列舉(雙向搜尋)的思想，只要列舉矩形的兩個對角點即兩個點就行了，然後判斷另外兩個點是否存在即可。所以列舉量最多隻有C(30,4)了。而且判斷兩個矩形是否相交的話我們不需要分類出所有的情況，從反面考慮，如果一個矩形在另一個矩形的上方或者左方或者下方或者右方的話就說明不相交了。而且另外一點是，對於一個矩形，我們只需要列舉一次對角頂點的組合，另外一個組合沒必要列舉，這樣減少了很多不必要的列舉。而且對於選出的4個點，按照x從左從左至右排列假設為a,b,c,d四個點的話，只有3種組合方式(a,b)與(c,d),(a,c)與(b,d),(a,d)與(b,c)，全部列舉一下就好了。為方便判斷，可以事先給座標排序，之後列舉所有大小為4的子集，並且每次對3種組合方式判斷一下取最大值。

這題的一個坑點：一個矩形可能完全包含在另一個矩形中，這種情況下面積取較大者，否則取和。

暴力列舉不失為一種好辦法，但是過多的列舉必然會導致效率低下了。所以下手之前可以分析下，看是否可以減少重複的沒必要的列舉，而且有時候減少這些列舉還可以保證正確率，就像這題如果列舉矩形的兩個對角的組合的話可能會導致判斷不全面導致計算錯誤，之前做的時候就是這樣，發現答案變大了，原因是因為考慮不全面，但是其實是沒必要的。而且折半列舉也是一種重要的思想，因為很多情況下只需要列舉一部分量，然後另一部分量直接判斷或者進行查詢就好了。 

 

#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)、最佳化計算過程

在此舉一個數據結構進行演算法的最佳化的例子：

1、codeforces675E  Trains and Statistic

 題意：一個城市有n個車站，編號從1到n，在第i號車站只能買到第i+1號到ai號車站的票(ai>=i+1),令P(i,j)為從第i號車站去第j號車站所需要買的最少的票的數量，給定ai，求所有的P(i,j)之和(1<=i<j<=n).

分析：看起來像圖論題，但是無法儲存，考慮其他方法。無後效性，明顯的動態規劃，令dp[i]為從i號車站去之後i+1到n這些車站的總票數最小數量，可以知道需要逆推，狀態轉移即為dp[i] = dp[pos]+n-i-(a[i]-pos),pos為i+1到a[i]這些車站中a[pos]最大的一個編號，知道了狀態轉移還不行，因為需要有大量計算區間最大值的過程，使用線段樹最佳化即可。

#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;

}

演算法最佳化的總結：

程式時間複雜度過高，除了換更優的演算法之外，最佳化當前的演算法也是很重要的。就像上面說明的那樣：減少當前計算過程中的冗餘計算，比如說標記，刪除、從減少計算量出發最佳化，比如說部分列舉，折半列舉、或者最佳化某個 計算的過程，比如說資料結構最佳化。演算法最佳化思想或者技巧需要知識的積累和對演算法過程進行的仔細分析，難以總結全面。要想熟練運用，還得不斷地鍛鍊和總結。

3、 STL的高效運用：

不管你是一個ACM競賽者還是一個開發程式設計師，STL都會是一個非常好的工具。如果能夠充分地利用STL，可以在程式碼空間、執行時間和編碼效率上獲得極大的好處，程式碼不僅高效簡潔而且看起來特別舒服。

首先粗略介紹下STL：

STL 大致可以分為三大類：演算法(algorithm)、容器(Container)、迭代器(iterator)。

STL 容器是一些模板類，提供了多種組織資料的常用方法，例如vector(向量，類似於陣列)、list(列表，類似於連結串列)、deque(雙向佇列)、set(集合)、map(對映)、stack(棧)queue(佇列)、priority_queue(優先佇列)等，

透過模板的引數我們可以指定容器中的元素型別。

STL 演算法是一些模板函式，提供了相當多的有用演算法和操作，從簡單如for_each（遍歷）到複雜如stable_sort（穩定排序）。STL 迭代器是對C 中的指標的一般化，用來將演算法和容器聯絡起來。幾乎所有的STL 演算法都是透過迭代器來存取元素序列進行工作的，而STL 中的每一個容器也都定義了其本身所專有的迭代器，用以存取容器中的元素。有趣的是，普通的指標也可以像迭代器一樣工作。熟悉了STL 後，你會發現，很多功能只需要用短短的幾行就可以實現了。透過STL，我們可以構造出優雅而且高效的程式碼，甚至比你自己手工實現的程式碼效果還要好。

STL 的另外一個特點是，它是以原始碼方式免費提供的，程式設計師不僅可以自由地使用這些程式碼，也可以學習其原始碼，甚至按照自己的需要去修改它。

在這裡首先例舉ACM經常需要用到的STL容器或演算法：

STl容器或介面卡等：pair、list、vector、priority_queue、set、map、stack

常用STL 演算法庫：sort快速排序演算法、二分查詢演算法、列舉排列演算法 .

在這裡只介紹下應用，如果想知道這個容器的具體操作可以去看書或者找度娘，這裡不詳細介紹操作了.

①、容器或介面卡部分：

1、  pair

相當於一個Struct，訪問方式舉個例子：pair<int,int> p; 那麼第一個成員便是p.first、第二個p.second,pair使用起來很方便，簡單快速高效，可以當做一個二元struct使用，而且它定義了比較的方法，先根據第一個成員比較，在根據第二個，所以如果你的比較運算子是這樣，那麼你就不需要定義比較函數了，而struct是不能直接進行比較的,構造pair的方法：make_pair。

下面是一個簡單的例子：

#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);

//首先按第一個成員從大到小排列，當第一個成員相等時，按第二個成員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.sort()，而且很重要的一點，list的size()函式是線性的，因為是以遍歷函式distance實現的。

Hdu5127-Dogs" Candies

題意：一個以兩個數字p，q作為單個元素的序列，支援三種操作：

1、 從序列中去掉包含p，q的這兩個數字的元素。

2、向序列中新增包含p，q的這兩個數字的元素。

3、對於給定的x和y，找到一對p，q，使得px+qy最大，輸出這個最大值。

 

分析：這題雖然資料量比較大，但是卻可以暴力解決，據說現場賽時只有10個隊伍過了此題，正解很麻煩，cdq分治+凸包，然而我全都不會…..首先抓住這題的一個特性，題目可能存在大量的插入和刪除操作，而且對於尋找最大值的操作，只能迴圈遍歷一次，不存在貪心的選取策略能使得列舉量減少。如果採取不刪除，而直接進行標記的策略便會超時，因為這樣會使得遍歷的時間增加。

根據以上的分析，抓住題目的特徵，選取合適的方法，選用list作為容器來儲存。執行時間不到時限的一半，簡直神奇，如果選取其他的容器也都會超時。也許這就是傳說中的暴力姿勢比較好吧….

#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

可以說這是一個STL的神器，相當於一個不定長陣列，利用這個你可以新增任意多的元素，容器以連續陣列的方式儲存元素序列，可以將vector 看作是以順序結構實現的線性表。當我們在程式中需要使用動態陣列時，vector將是一個理想的選擇。這個完全相當於把一個數組當成一個元素來進行使用了，可以直接相等，賦值操作等。

在這裡介紹幾個比較經典的使用：

1、利用vector防止遞迴爆棧。2、利用vector來實現鄰接表（通常是vector<int>G[N]，但這種方式可能會因為儲存量巨大然後vector的容量擴充套件導致TLE）3、利用vector儲存空間佔用比較大的矩陣。

vector高效的原因在於配置了比其所容納的元素更多的記憶體，但其記憶體重新配置會花很多時間，（在這裡順便說下，像new和malloc等函式要慎用，這屬於用時間開銷代價換取空間的舉措，非常容易TLE），vector確實非常好用，合理使用實則幫助很大。

Vector算是應用得最多的一個stl容器了，例子太多了，在此就不舉了.....

 

4、priority_queue:

這個也可以說是一個神器，優先佇列其實就是堆，在優先佇列中，元素被賦予優先順序。當訪問元素時，具有最高優先順序的元素最先被刪除。優先佇列具有最高階先出（first in, largest out）的行為特徵。在這裡說下這個怎麼進行過載的問題。

兩種方式：

一、直接在struct或者class內部定義，那麼你定義時直接指明元素型別就好了，因為你是定義了比較函式的。二、定義比較結構。

//內部定義：

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;

//定義比較結構

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;

具體點就是可以用來貪心或者加速搜尋，下面是對應的兩個題：

(1)、貪心

優先佇列最常用的就是貪心，舉個例子。

poj2010-Moo University - Financial Aid     

題意：有c只奶牛，現在要招募n只進動物學校，第i只奶牛的分數為si,需要的資金幫助為ai,現在有總共為f的資金，問招募到的n只奶牛中中位數最大是多少？

分析：採取貪心策略，儘量選擇大的，首先按分數從小到大排個序，之後從大到小列舉中位數，所以我們要知道當前分數作為中位數下，需要的資金總和最小是多少。令l[i]表示選取第i+1號奶牛作為中位數時分數比它小的n/2頭奶牛需要的資金幫助的最小值，令r[i]表示選取第i-1號奶牛作為中位數時分數比它大的n/2頭奶牛需要的資金幫助的最小值。遍歷時用優先佇列儲存當前的分數，貪心地換掉需要的資金多的奶牛，一次預處理r[i]和l[i]即可，總的時間複雜度為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 - 簡單的圖論問題

這題很明顯屬於搜尋題，bfs廣搜即可，但是需要找到權值最小的路徑的話，那麼我們需要使用優先佇列來加速搜尋和求解答案。每一步優先選擇權值小的結點來拓展狀態，且結點中記錄上一次擴充套件狀態時的方向，而且給一個點標記去重的需要考慮四個方向的狀態。

#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，顧名思義，集合，無重複元素，插入的元素自動按增序排列。

內部實現: 紅黑樹，一種平衡的二叉排序樹，其Compare 函式，類似於qsort 函數里的那個Compare 函式，作為紅黑樹在內部實現的比較方式。

在這裡說下一些成員函式的時間複雜度：

insert() O(logn)、erase()O(logn)、find()O(logn)

lower_bound()O(logn) 查詢第一個不小於k 的元素

upper_bound()O(logn) 查詢第一個大於k 的元素

equal_range()O(logn) 以pair形式返回lower_bound和upper_bound，在需要確定一個增序序列中某一段都是某一值的情況下是非常有效的，這比通用演算法更有效。

容器最主要的功能就是判重,也可以進行二分查詢。

要允許重複元素，選用multiset即可。

沒有定義比較方式的元素需要進行過載，過載方式和優先佇列一樣。

判重是set的一個最常見的使用。

Uva11572- Unique Snowflakes

題意：給定一個長度為n序列A，找到一個最長的連續子序列，使得這個序列中沒有相同的元素。

分析：經典的O(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

這個容器也非常好，和set差不多，pair 組成的紅黑樹（所以比較方式和pair一樣），成員函式複雜度和前者一樣，在這裡就不贅述了，容器適用於那些需要進行對映（可以根據Key找到對應的Value，作為hash還是不錯的），因此map是關聯陣列。

要允許重複元素，使用multimap。

在這裡指出：在C++11裡,有unoder和hash的map和set,裡面的元素沒有順序.速度比普通的set和map快了很多，但是需要自己過載hash

map最常見的應用就是進行對映。

hdu4460 - Friend Chains

題意：給定n個人的名字和這n個人之間的朋友關係，間接相連也算是朋友，如果兩個人之間透過n個人相連，那麼這條朋友鏈的長度即為n-1.求一個最小的k，使得對任意兩個人，他們之間的朋友鏈的長度不會超過k。

分析：明顯是求任意兩點之間的最短路，把那個最大的距離找到即可，但是給定的是名字，需要進行對映，用map對映為標號即可。而且這題的邊的權值為1，不需要用優先佇列，用普通佇列即可。值得注意的是，不需要進行n次bfs求取最短路，只需要進行兩次。首先選取一個點x進行最短路的求解，之後找到離x距離最大的那個點y在進行一次最短路的求解即可。因為第一次最短路肯定會求得整個圖中離圖的重心點最遠的那個點，也就是說處於整個圖的最端點。那麼之後從這個點出發求得的最短路距離必定是整個圖中任意兩點之間距離的最大值。

#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裡面它屬於容器介面卡，對容器的重新包裝，後進先出結構。

經典使用：單調棧的實現。

poj2559 - Largest Rectangle in a Histogram

題意：給定一個柱狀圖，由n個寬為1，長為hi的矩形從左至右依次排列組成，求裡面包含的長方形的最大面積是多少？

分析：如果預處理一次區間最小值，暴力也要O（n^2),無法承受，換一種方式，我們可以列舉每個h[i]，求以當前高度作為長度的矩形的最大面積，所以需要做的就是對於固定的h[i]，求出左端點L和右端點R，必定有h[L-1]<h[i]和h[R]<h[i],否則總可以更新左右端點，令l[i]為(j<=i且h[j-1]<h[i]的最大的j),r[i]為(j>i且h[j]<h[i]的最小的j). 怎麼計算l[i]和r[i]. 思考下就可以知道可以利用棧解決。

考慮計算l[i]的情況，棧中維護的是高度依次減小的標號，也就是如果棧中從上到下的值依次為i，那麼i>i+1且h[i]>h[i+1]。對於當前的高度h[i]，如果有棧頂的元素h[k]>=h[i]，證明左端點可以一直往左移動，不斷地取出棧頂元素，如果棧為空了證明可以移動到最左邊，也就是l[i]=0,否則h[i]=j+1。之所以利用棧求解，是因為每次都要取得左邊第一個高度小的端點和右邊第一個高度小的端點。這樣符合後進先出的性質，模擬下棧的工作情況便可以明白了。正反兩次預處理就可以計算出l和r了，之後遍歷一次高度求取最大值。

這樣的棧稱為單調棧，和單調佇列是類似的。

#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：對給定區間所有元素進行排序（全排）

stable_sort ：對給定區間所有元素進行穩定排序，就是相等的元素位置不變，原來在前面的還在前面。

partial_sort ：對給定區間所有元素部分排序，就是找出你指定的數目最小或最大的值放在最前面或最後面，比如說我只要找到1000000個數中最大的五個數，那你用這個函式是最好的，排序後最大的五個數就在最前面的五個位置，其他的元素位置分佈不確定。

partial_sort_copy：對給定區間複製並排序，和上面的一樣，只是這是指定區間進行復制然後排序的。

nth_element ：找出給定區間的某個位置對應的元素，根據比較函式找到第n個最大（小）元素，適用於尋找“第n個元素”。

is_sorted ：判斷一個區間是否已經排好序（返回bool值判斷是否已排序）

partition ：使得符合某個條件的元素放在前面，劃分區間函式，將 [first, last)中所有滿足的元素置於不滿足的元素前面，這個函式會返回迭代器，設返回的迭代器為 i，則對 [first, i)中的任意迭代器 j，*j滿足給定的判斷，對 [i, last) 中的任意迭代器 k，*k不滿足。

stable_partition ：相對穩定的使得符合某個條件的元素放在前面（和上面的一樣，只是位置不變）

這個函式真是絕對的神助，相比qsort沒這麼麻煩了。使用時根據需要選擇合理的排序函式即可，所有的排序函式預設從小到大排序，可以定義自己的比較方式。

sort排序十分常見，在此舉個其他排序的例子：

xtu1050-第K個數

Description

給你一個整數序列和若干個問題，問題是這個序列的第i個元素到第j個元素的片斷中的第k大數是什麼？比如說給你的序列為（1, 5, 2, 6, 3, 7, 4），問題是（2，5，3），則從第2個元素到第5個元素為（5，2，6，3），排序以後是（2，3，5，6），則第三個數是5。

輸入：

第一行為兩個整數n，m（1 <= n <= 100 000, 1 <= m <= 5 000），表示序列的元素個數和問題的個數，第二行為n個正整數的序列，每個整數為一個32位整數，兩個數之間有一個空格隔開。以後m行為問題，每個問題由三個整數表示i，j，k，第i個元素到第j個元素的片斷中的第k大數是什麼？（元素序號從1開始計數,i<=j,1<=k<=j-i+1）

輸出：

每行輸出對應問題的結果。

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個數，直接nth_element，線性複雜度暴力水過………而且這題解法很多，比如用線段樹等資料結構進行求解會是更優的。

#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、 二分系列：

二分檢索，複雜度O(log(last-first))

itr =upper_bound(first, last, value, cmp);

//itr 指向大於value 的第一個值(或容器末尾)

itr = lower_bound(first, last, value, cmp);

//itr 指向不小於valude 的第一個值(或容器末尾)

pairequal_range(first, last, value, cmp);

//找出等於value 的值的範圍O(2*log(last– first))

Binary_search(first,last, value)返回bool值，找到則true，否則false。

二分經常會與其他演算法結合，二分的應用是也是十分常見的，在這舉個例子說明下找一個數或等於一個數的一個範圍的二分應用：

hdu1496-Equations

題意：給定a，b，c，d四個數，求有多少對x1，x2，x3，x4滿a*x1^2+b*x2^2+c*x3^2+d*x4^2=0

分析：暴力會超時，把ax1*x1+bx2*x2打表，利用二分查詢，排序之後equal_range尋找等於這個值的範圍就行了。

#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;

}

利用二分查詢時間複雜度降到了o（n*nlog（n））。當然這個題目可以hash，這是最好的辦法，O(1)查詢，複雜度更小了。

3、 排列系列：

這兩個函式都可以用來列舉字典序排列，那種水題直接用這個就解決了。

在這裡貼個網址，看了下，說的挺好的；        

http://blog.sina.com.cn/s/blog_9f7ea4390101101u.html

 

4、 常用函式：

最後補充下常用函式，//其實是我常用的函式...

copy函式，直接複製，比for迴圈高效，最壞為線性複雜度，而且這個可以說是一個copy族函式，還有類似的滿足一定條件的copy函式如copy_if等。

find、find_i：查詢第一個匹配的值或第一個滿足函式使其為true的值位置，沒有返回指定區間的末尾，線性複雜度，還有一些不怎麼常用的find族函式就不多介紹了。

count、count_if： 返回匹配或使函式為true的值的個數，線性複雜度。

search，這是尋找序列是否存在於另一個序列中的函式，挺好用的，某些簡單的尋找公共子串的題就可以這樣寫，時間複雜度二次。

reverse，翻轉一個區間的值，我經常遇到需要這種題，直接reverse了，不需要for迴圈了，主要是方便。

for_each:直接對一個區間內的每個元素執行後面的函式操作，寫起來簡單。

max、min、max_element、min_element:尋找兩個數或者一個區間的最大最小值，都可以新增比較函式引數。

集合操作函式：includes、set_union、set_difference、set_intersection、set_symmetric_difference、前面這些函式的最差複雜度為線性，另外附加一個序列的操作函式merge，相當於歸併排序中的合併函式，時間複雜度為線性，注意這些函式的操作物件都必須是升序的。

這裡舉個例子：

#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");

//合併兩個有序序列，必須為合併後的序列分配空間，否則程式會崩潰。

printf("兩個集合的合併序列為：");

merge(a, a+5, b, b+5, c);

for_each(c, c+10, out);

puts("");

//求兩個集合的並集。

fill(c, c+20, -1);

set_union(a, a+5, b, b+5, c);

printf("兩個集合的並集為：");

for_each(c, c+10, out);

puts("");

//求兩個集合的交集。

fill(c, c+20, -1);

set_intersection(a, a+5, b, b+5, c);

printf("兩個集合的交集為：");

for_each(c, c+10, out);

puts("");

//求兩個集合的差集，這裡為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("");

//求兩個集合的差集，這裡為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("");

//求兩個集合的對稱差

set_symmetric_difference(a, a+5, b, b+5,c);

printf("兩個集合的對稱差為：");

for_each(c, c+10, out);

puts("");

return 0;

}

下面的這個題便說明了STL的方便與實用：

codeforces730A - Toda2

題意：有n個人，每個人有一個rating，目的是使得每個人的rating相同而且儘可能的大，每次可以選取2到5個人，使得每個人的rating減1，如果rating已經為0了，那麼不減少，輸出你的操作過程的每一步，每一步為一個01序列，如果選擇了第i個人，那麼序列中第i位為1。

分析：模擬題，不過比較麻煩，為方便起見，利用STL實現，思路是每次選取兩到三個人進行rating的減小，然後每次選取rating較大的幾個人減少就行了，如果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不失為一種絕佳工具，合理的使用是一種很好的技巧，但是需要指出不要過分依賴於STL，STL裡面函式確實多的你幾乎每個操作都有函式代替，寫起來又簡單。但凡是都有利弊，STl不好的一個地方就是如果碰到某些卡時間、卡空間、各種卡的題目，那些函式的效率問題就大打折扣了，一般手寫的效率會高。

1、STL的容器如queue還有很多函式都比較慢，在碰到那些資料量大的題目時效率確實不高，很容易超時，poj1426 BFS水題吧，用STl容器queue各種超時，一直想不明白，後面自己寫個queue，直接就32ms AC了，透過這個也更加體會到這一點（最致命的一點）

2、STL封裝了大量的資料結構和演算法，使用起來一定需要注意，STl容器的操作都是建立在迭代器之上的，迭代器的使用也需要注意，不然各種問題，程式崩潰…

3、STL演算法極其多，大致分為搜尋、修改、排序、集合與工具等，每一種類中的演算法都比較多，有助於我們快速地完成程式設計。

4、使用STL容器時注意使用自帶的成員函式要比通用演算法高效很多。

5、STL的演算法思想是非常值得借鑑的，你可以去檢視以學習。

6、STL也是存在缺點的，沒有提供任何泛型的圖或樹結構，只能自己實現。