STL容器

STL 容器是一些模板类，提供了多种组织数据的常用方法。常用的STL容器包括pair（组合）、list（列表，类似于链表）、vector（向量，类似于数组）、priority_queue（优先队列）、set（集合）、map（映射）、stack（栈）等，通过模板的参数我们可以指定容器中的元素类型。

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);
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是一个循环链表。这个容器的特点：快速插入和删除。作用和vector差不多，但内部是用链表实现。这个容器不支持随机访问，你不能[]或者利用通用算法操作，比如说要排序的话你只能利用成员函数比如list.sort()，而且很重要的一点，list的size()函数是线性的，因为是以遍历函数distance实现的。

例：HDU 5127

#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

相当于一个不定长数组，利用这个你可以添加任意多的元素，容器以连续数组的方式存储元素序列，可以将vector 看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时，vector将是一个理想的选择。这个完全相当于把一个数组当成一个元素来进行使用了，可以直接相等，赋值操作等。比较经典的使用包括：

a、利用vector防止递归爆栈。
b、利用vector来实现邻接表。
c、利用vector存储空间占用比较大的矩阵。

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;

priority_queue的应用：贪心

例1：POJ 2010

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

priority_queue的应用：加速搜索

例2：CSU 1780
#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，顾名思义，集合，无重复元素，插入的元素自动按增序排列。内部实现: 红黑树，一种平衡的二叉排序树。容器最主要的功能就是判重，也可以进行二分查找。要允许重复元素，选用multiset即可。容器性能：set与map的查找、删除、插入性能都是对数复杂度。没有定义比较方式的元素需要进行重载，重载方式和优先队列一样。

set的应用：判重

例：UVA 11572
#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

这个容器适用于那些需要进行映射（可以根据Key找到对应的Value，作为hash还是不错的），因此map是关联数组。要允许重复元素，使用multimap。

map的应用：映射

例：HDU 4460
#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里面它属于容器适配器，对容器的重新包装，后进先出结构。

stack的应用：单调栈的实现

例：POJ 2559
#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;
}

---

字符串算法

1、trie树

例：HDU 1075
#include <cstdio>
#include <string>
using namespace std;
struct trie
{
trie * next[26];
int index;
};
trie *thead;
char dic[1000000][20];
inline trie * newnode()
{
int i;
trie *t;
t=(trie*)malloc(sizeof(trie));
memset(t,0,sizeof(trie));
return t;
}
void insert(trie * s,char x[],int pos)
{
int i;
trie *t;
for(i=0; x[i] ;i++) {
if(s->next[ x[i]-'a' ] ) s=s->next[ x[i]-'a' ];
else{
t=newnode();
s->next[x[i]-'a' ]=t;
s=t;
}
}//for
s->index=pos;
}
void deltrie(trie * s)
{
int i;
for(i=0; i < 26;i++) {
if(s->next[i] ) deltrie(s->next[i]);
}
free(s);
s=NULL;
}
int find(trie *s, char x[])
{
int i;
if(x[0] == 0)return -1;
for(i=0; x[i] ;i++) {
if(s->next[ x[i]-'a' ] ) s=s->next[ x[i]-'a' ];
elsebreak;
}
if(x[i]==0) returns->index;
else return -1;
}
int main()
{
int t,n,i,j,all;
charword[20],mars[20],ch;
thead=newnode();
while(scanf("%s",word)==1)
if(word[0]=='S')break;
i=1;
while(scanf("%s",dic[i])==1&& dic[i][0]!='E') {
scanf("%s",mars);
insert(thead,mars,i);
i++;
}
all=i;
while(scanf("%s",word)==1)
if(word[0]=='S')break;
getchar(); j=0;
while(scanf("%c",&ch)==1&& ch!='E') {
if(ch>='a'&& ch<='z') {
mars[j]=ch;j++;
}
else {
mars[j]=0;
t=find( thead , mars );
j=0;
if(t>0)printf("%s",dic[t]);
else if(mars[0]!=0)printf("%s",mars);
printf("%c",ch);
}
}//while
deltrie(thead);
}

2、KMP

例：HDU 2087

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=1000+10;
char s1[maxn],s2[maxn];
int next[maxn],ans;
void Kmp()
{
int n=strlen(s1);
int m=strlen(s2);
if(m>n) return ;
int j=0;
for(int i=0;i<n;++i)
{
while(j&&s1[i]!=s2[j]) j=next[j];
if(s1[i]==s2[j]) j++;
if(j==m) {ans++;j=0;}
}
}
void getnext()
{
int n=strlen(s2);
next[0]=next[1]=0;
for(int i=1;i<n;++i)
{
int j=next[i];
while(j&&s2[i]!=s2[j]) j=next[j];
next[i+1]=(s2[i]==s2[j])?j+1:0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%s",s1))
{
if(s1[0]=='#') break;
scanf("%s",s2);
ans=0;
getnext();
Kmp();
printf("%d\n",ans);
}
return 0;
}

3、AC自动机

例：UVA 11468

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=2000+10;
double p[110],dp[maxn][110];
bool vis[maxn][110];
int ch[maxn][63],val[maxn],next[maxn],size,n;
int idx(char c)
{
if(c>='0'&&c<='9') return c-'0';
if(c>='a'&&c<='z') return c-'a'+10;
return c-'A'+10+26;
}
void Init()
{
memset(vis,0,sizeof(vis));
memset(ch[0],0,sizeof(ch[0]));
memset(next,0,sizeof(next));
memset(val,0,sizeof(val));
memset(p,0,sizeof(p));
size=0;
}
void insert(const char *s)
{
int u=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int c=idx(s[i]);
if(!ch[u][c])
{
ch[u][c]=++size;
memset(ch[size],0,sizeof(ch[size]));
val[size]=0;
}
u=ch[u][c];
}
val[u]=1;
}
void build()
{
queue<int>q;
for(int i=0;i<62;++i)
{
if(ch[0][i]) q.push(ch[0][i]);
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<62;++i)
{
int v=ch[u][i];
if(!v) {ch[u][i]=ch[next[u]][i];continue;}
q.push(v);
int j=next[u];
while(j&&!ch[j][i]) j=next[j];
next[v]=ch[j][i];
val[v]|=val[next[v]];
}
}
}
double f(int u,int L)
{
if(L==0) return 1.0;
if(vis[u][L]) return dp[u][L];
vis[u][L]=true;
dp[u][L]=0;
for(int i=0;i<62;++i)
{
if(!val[ch[u][i]])
dp[u][L]+=p[i]*f(ch[u][i],L-1);
}
return dp[u][L];
}
char str[110];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,tcase=0;
scanf("%d",&t);
while(t--)
{
tcase++;
Init();
int K;
scanf("%d",&K);
for(int i=0;i<K;++i)
{
scanf("%s",str);
insert(str);
}
scanf("%d",&n);
char c[3];
for(int i=0;i<n;++i)
{
scanf("%s",c);
scanf("%lf",&p[idx(c[0])]);
}
build();
int L;
scanf("%d",&L);
double ans=f(0,L);
printf("Case #%d: %lf\n",tcase,ans);
}
return 0;
}