STL容器
STL 容器是一些模板类,提供了多种组织数据的常用方法。常用的STL容器包括pair(组合)、list(列表,类似于链表)、vector(向量,类似于数组)、priority_queue(优先队列)、set(集合)、map(映射)、stack(栈)等,通过模板的参数我们可以指定容器中的元素类型。
1、pair
相当于一个Struct,访问方式举个例子:pair
#include
#include
#include
#include
#include
using namespace std;
const int N = 1010;
typedef pair
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 ());
for (int i = 0; i <>
return 0;
}
2、List
list是一个循环链表。这个容器的特点:快速插入和删除。作用和vector差不多,但内部是用链表实现。这个容器不支持随机访问,你不能[]或者利用通用算法操作,比如说要排序的话你只能利用成员函数比如list.sort(),而且很重要的一点,list的size()函数是线性的,因为是以遍历函数distance实现的。
例:HDU 5127
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef pair
list l;
int main() {
int n;
while (scanf('%d', &n), n) {
l.clear();
for (int i = 0; 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 ::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; } (const node &a) const { return x >
};
priority_queue
//定义比较结构
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<>
};
priority_queue<>
priority_queue的应用:贪心
例1:POJ 2010
#include
#include
#include
#include
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 <>
int main() {
int n, c, f;
scanf('%d %d %d', &n, &c, &f);
for (int i = 1; i <>
sort(ca+1, ca+1+c, cmp);
n >>= 1;
priority_queue
int sum = 0;
for (int i = 1; i <>
l[n] = sum;
for (int i = 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 <>
ans = ca[i].s;
break;
}
}
printf('%d\n', ans);
return 0;
}
priority_queue的应用:加速搜索
例2:CSU 1780
#include
#include
#include
#include
#include
#include
#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 <>
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 <>
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; 1 || ny>1 || nx>
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 <>
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 <>
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; 1 || ny>1 || nx>
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 <>
for (int j = 1; 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
#include
#include
#include
using namespace std;
int a[1000001];
set
int main() {
int t, n;
scanf('%d', &t);
while (t--) {
scanf('%d', &n);
for (int i = 0; i <>
s.clear();
int st = 0, en = 0, ma = 0;
while (en <>
while (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
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 1010;
int vis[N], d[N];
map
vector
int solve(int x, int n) {
int ma = 0, res, cnt = 1;
queue
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 <>
int y = G[t][i];
if (vis[y]) continue;
vis[y] = 1;
d[y] = d[t] + 1;
if (ma <>
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 <>
char s[15], str[15];
for (int i = 1; i <>
int m;
scanf('%d', &m);
for (int i = 1; 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
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 100010;
stack
template
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 <>
while (!s.empty()) s.pop();
for (int i = 0; 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 <>
printf('%I64d\n', ans);
}
return 0;
}
字符串算法
1、trie树
例:HDU 1075
#include
#include
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')>='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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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<>
{
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<>
{
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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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<>
if(c>='a'&&c<>
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<>
{
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
for(int i=0;i<>
{
if(ch[0][i]) q.push(ch[0][i]);
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;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<>
{
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<>
{
scanf('%s',str);
insert(str);
}
scanf('%d',&n);
char c[3];
for(int i=0;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;
}
长沙信息学竞赛
联系客服