|
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; } }; 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; 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; 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')> 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; } 长沙信息学竞赛 |
|
|
