免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

STL容器

STL 容器是一些模板類，提供了多種組織數(shù)據(jù)的常用方法。常用的STL容器包括pair（組合）、list（列表，類似于鏈表）、vector（向量，類似于數(shù)組）、priority_queue（優(yōu)先隊(duì)列）、set（集合）、map（映射）、stack（棧）等，通過模板的參數(shù)我們可以指定容器中的元素類型。

1、pair

相當(dāng)于一個(gè)Struct，訪問方式舉個(gè)例子：pair 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。例：

#include   

#include   

#include   

#include   

#include   

using namespace std;  

const int N = 1010;  

typedef pair 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

());  

    for (int i = 0; i <>

    return 0;  

}  

2、List

list是一個(gè)循環(huá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)的。

例：HDU 5127

#include   

#include   

#include   

#include   

#include   

using namespace std;  

typedef long long LL;  

typedef pair p;  

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

相當(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)行使用了，可以直接相等，賦值操作等。比較經(jīng)典的使用包括：

a、利用vector防止遞歸爆棧。

b、利用vector來實(shí)現(xiàn)鄰接表。

c、利用vector存儲(chǔ)空間占用比較大的矩陣。 

4、priority_queue

優(yōu)先隊(duì)列其實(shí)就是堆，在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級(jí)。當(dāng)訪問元素時(shí)，具有最高優(yōu)先級(jí)的元素最先被刪除。優(yōu)先隊(duì)列具有最高級(jí)先出（first in, largest out）的行為特征。重載有兩種方式：直接在struct或者class內(nèi)部定義；定義比較結(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 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<>

};  

priority_queue<>,cmp> q;  

priority_queue的應(yīng)用：貪心

例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  q;  

    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的應(yīng)用：加速搜索

例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 <>, greater > 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 <>

            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 <>, greater > 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 <>

            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，顧名思義，集合，無重復(fù)元素，插入的元素自動(dòng)按增序排列。內(nèi)部實(shí)現(xiàn): 紅黑樹，一種平衡的二叉排序樹。容器最主要的功能就是判重，也可以進(jìn)行二分查找。要允許重復(fù)元素，選用multiset即可。容器性能：set與map的查找、刪除、插入性能都是對(duì)數(shù)復(fù)雜度。沒有定義比較方式的元素需要進(jìn)行重載，重載方式和優(yōu)先隊(duì)列一樣。

set的應(yīng)用：判重

例：UVA 11572

#include   

#include   

#include   

#include   

using namespace std;  

int a[1000001];  

set s;  

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

這個(gè)容器適用于那些需要進(jìn)行映射（可以根據(jù)Key找到對(duì)應(yīng)的Value，作為hash還是不錯(cuò)的），因此map是關(guān)聯(lián)數(shù)組。要允許重復(fù)元素，使用multimap。

map的應(yīng)用：映射

例：HDU 4460

#include   

#include   

#include   

#include   

#include   

#include 

#include   

using namespace std;  

const int N = 1010;  

int vis[N], d[N];  

map  mp;  

vector G[N];  

int solve(int x, int n) {  

    int ma = 0, res, cnt = 1;  

    queue 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 <>

            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里面它屬于容器適配器，對(duì)容器的重新包裝，后進(jìn)先出結(jié)構(gòu)。

stack的應(yīng)用：單調(diào)棧的實(shí)現(xiàn)

例：POJ 2559

#include   

#include   

#include   

#include   

#include   

using namespace std;  

typedef long long LL;  

const int N = 100010;  

stack s;  

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自動(dòng)機(jī)

例：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()  

{  

    queueq;  

    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;  

}