Demo entry 6648278

123

   

Submitted by anonymous on Oct 23, 2017 at 15:21
Language: C++. Code size: 42.5 kB.

模板底子
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int,int> II;
const int maxn = 2e5+10;
const int maxint = 0x3f3f3f3f;
const int mod = 1e9+7;
int main ()
{
    return 0;
} 
斐波那契博弈
/*有一堆物品,两人轮流取物品,先手最少取一个,至多无上限,但不能把物品取完,之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件,取走最后一件物品的人获胜。
结论是:先手胜当且仅当n不是斐波那契数(n为物品总数)*/
int f[maxn];   
void Init()    
{    
    f[0] = f[1] = 1;    
    for(int i=2;i<maxn;i++)    
        f[i] = f[i-1] + f[i-2];    
}  
int main()    
{    
    Init();    
    int n;    
    while(cin>>n)    
    {    
        if(n == 0) break;    
        bool flag = 0;    
        for(int i=0;i<maxn;i++)    
        {    
            if(f[i] == n)    
            {    
                flag = 1;    
                break;    
            }    
        }    
        if(flag) puts("后手必胜");    
        else puts("先手必胜");    
    }    
    return 0;    
}
 
威佐夫博弈
/*有两堆各若干的物品,两人轮流从其中一堆取至少一件物品,至多不限,或从两堆中同时取相同件物品,规定最后取完者胜利。
若两堆物品的初始值为(x,y),且x<y,则另z=y-x;记w=(int)[((sqrt(5)+1)/2)*z];若w=x,则先手必败,否则先手必胜。*/
int main()
{
    int n1,n2,temp;  
    while(cin>>n1>>n2)  
    {  
        if(n1>n2)  swap(n1,n2);  
        temp=floor((n2-n1)*(1+sqrt(5.0))/2.0);  
        if(temp==n1) cout<<"后手必胜"<<endl;  
        else cout<<"先手必胜"<<endl;  
    }  
    return 0;
}
尼姆博弈
/*有任意堆物品,每堆物品的个数是任意的,双方轮流从中取物品,每一次只能从一堆物品中取部分或全部物品,最少取一件,取到最后一件物品的人获胜。
结论就是:把每堆物品数全部异或起来,如果得到的值为0,那么先手必败,否则先手必胜。*/ 
int main()
{
    int n,ans,temp;  
    while(cin>>n)  
    {  
        temp=0;  
        for(int i=0;i<n;i++)  
        {  
            cin>>ans;  
            temp^=ans;  
        }  
        if(temp==0) cout<<"后手必胜"<<endl;  
        else cout<<"先手必胜"<<endl;  
    }   
    return 0;
}
巴什博弈
//只有一堆n个物品,两个人轮流从中取物,规定每次最少取一个,最多取m个,最后取光者为胜。
int main()
{
    int n,m;  
    while(cin>>n>>m)  
    if(n%(m+1)==0) cout<<"后手必胜"<<endl;  
    else cout<<"先手必胜"<<endl;  
    return 0;
}
最小树形图
const double g=10.0,eps=1e-9;
const int N=100+10,maxn=100000+10,inf=0x3f3f3f;
double x[N],y[N];
int n,m;
int pre[N];
bool vis[N],in[N];
double w[N][N];
double dis(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&w[u][i]<inf)
           dfs(i);
}
double dirmst(int u)
{
    double ans=0;
    dfs(u);
    for(int i=1;i<=n;i++)
        if(!vis[i])
          return -1;
    memset(vis,0,sizeof vis);
    while(1){
        for(int i=1;i<=n;i++)
        {
            if(i!=u&&!in[i])
            {
                w[i][i]=inf;
                pre[i]=i;
                for(int j=1;j<=n;j++)
                    if(!in[j]&&w[j][i]<w[pre[i]][i])
                        pre[i]=j;
            }
        }
        int i;
        for(i=1;i<=n;i++)
        {
            if(i!=u&&!in[i])
            {
                int j=i,cnt=0;
                while(j!=u&&pre[j]!=i&&cnt<=n)cnt++,j=pre[j];
                if(j==u||cnt>n)continue;
                break;
            }
        }
        if(i>n)
        {
            for(int j=1;j<=n;j++)
                if(j!=u&&!in[j])
                    ans+=w[pre[j]][j];
            return ans;
        }
        int j=i;
        memset(vis,0,sizeof vis);
        do{
            ans+=w[pre[j]][j],j=pre[j],vis[j]=in[j]=1;
        }while(j!=i);
        in[i]=0;
        for(int k=1;k<=n;k++)
            if(vis[k])
               for(int j=1;j<=n;j++)
                  if(!vis[j])
                  {
                      if(w[i][j]>w[k][j])w[i][j]=w[k][j];
                      if(w[j][k]<inf&&w[j][k]-w[pre[k]][k]<w[j][i])
                        w[j][i]=w[j][k]-w[pre[k]][k];
                  }
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&x[i],&y[i]);
        for(int i=1;i<=n;i++)
        {
            vis[i]=in[i]=0;
            for(int j=1;j<=n;j++)
                w[i][j]=inf;
        }
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==b)continue;
            w[a][b]=dis(a,b);
        }
        double ans=dirmst(1);
        if(ans<0)printf("poor snoopy\n");
        else printf("%.2f\n",ans);
    }
    return 0;
}
费用流
struct mmp{
    int a , b;
};
struct list1{
    int next , back , to , r , v;
}ll[250001];
int n , m , ans;
int adj[501] , top;
int h , t , f[501] , d[501] , b[501] , q[5001];
void list1(int x , int y , int w , int z)
{
    top++;
    ll[top].v = z;
    ll[top].r = w;
    ll[top].back = top+1;
    ll[top].to = y;
    ll[top].next = adj[x];
    adj[x] = top;
    top++;
    ll[top].v = -z;
    ll[top].r = 0;
    ll[top].back = top-1;
    ll[top].to = x;
    ll[top].next = adj[y];
    adj[y] = top;
}
mmp spfa(int x , int y)
{
    int i , p , pp , mi;
    mmp g;
    for (i = 0 ; i <= n ; i++)
    {
        f[i] = 0;
        d[i] = 1;
        b[i] = 0;
    }
    h = 1;
    t = 1;
    q[1] = x;
    f[x] = 1;
    d[x] = 0;
    while (h <= t)
    {
        p = q[h];
        f[p] = 0;
        for (i = adj[p] ; i != 0 ; i = ll[i].next)
        {
            if (ll[i].r > 0)
            {
                pp = ll[i].to;
                if (d[pp] == 1 || d[pp] > d[p]+ll[i].v)
                {
                    d[pp] = d[p]+ll[i].v;
                    b[pp] = i;
                    if (f[pp] == 0)
                    {
                        f[pp] = 1;
                        t++;
                        q[t] = pp;
                    }
                }
            }
        }
        h++;
    }
    if (d[y] == 1) 
g.a = 0;
    else
    {
        mi = 1;
        i = y;
        while (b[i] != 0)
        {
            if (mi == 1)
                mi = ll[b[i]].r;
            else
                mi = min(mi,ll[b[i]].r);
            i = ll[ll[b[i]].back].to;
        }
        i = y;
        while (b[i] != 0)
        {
            ll[b[i]].r -= mi;
            ll[ll[b[i]].back].r += mi;
            i = ll[ll[b[i]].back].to;
        }
        g.a = mi;
        g.b = mi*d[y];
    }
    return g;
}
int main ()
{
    int i , j , k , x , y , z;
    mmp g;
    while (~scanf("%d%d",&n,&m))
    {
        for (i = 1 ; i <= n ; i++) adj[i] = 0;
        top = 0;
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d%d%d",&x,&y,&z,&k);
            list1(x,y,z,-k);
        }
        ans = 0;
        while (1)
        {
            g = spfa(1,n);
            if (g.a == 0)
                break;
            ans += g.b;
        }
        printf("%d\n",-ans);
    }
    return 0;
}
最大流
最小割=最大流
struct mmp{
    int next , back , r , to;
}ll[401];
int a7 = 2*(1e9+7);
int m , n , ans; 
int adj[201] , top;
int f[201] , b[201] , h , t , q[201];
void list1(int x , int y , int z)
{
    top++;
    ll[top].r = z;
    ll[top].back = top+1;
    ll[top].to = y;
    ll[top].next = adj[x];
    adj[x] = top;
    top++;
    ll[top].r = 0;
    ll[top].back = top-1;
    ll[top].to = x;
    ll[top].next = adj[y];
    adj[y] = top;
}
int bfs(int x , int y)
{
    int i , j , k;
    for (i = 1 ; i <= n ; i++)
    {
        b[i] = n;
        f[i] = 0;
    }
    h = 1;
    t = 1;
    q[1] = x;
    f[x] = 1;
    b[x] = 0;
    while (h <= t)
    {
        i = q[h];
        for (j = adj[i] ; j != 0 ; j = ll[j].next)
        {
            k = ll[j].to;
            if (ll[j].r > 0 && f[k] == 0)
            {
                t++;
                q[t] = k;
                f[k] = 1;
                b[k] = b[i]+1;
                if (k == y)
                    return 1;
            }
        }
        h++;
    }
    return 0;
}
int dfs(int x , int y , int mi)
{
    int i , j , k;
    if (x == y) return mi;
    for (; f[x] != 0 ; f[x] = ll[f[x]].next)
    {
        i = f[x];
        j = ll[i].to;
        if (b[j] == b[x]+1 && ll[i].r > 0)
        {
            k = dfs(j,y,min(mi,ll[i].r));
            if (k > 0)
            {
                ll[i].r -= k;
                ll[ll[i].back].r += k;
                return k;
            }
        }
    }
    return 0;
}
int main ()
{
    int i , j , k , x , y , z;
    while (~scanf("%d%d",&m,&n))
    {
        top = 0;
        for (i = 1 ; i <= n ; i++)
           adj[i] = 0;
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            list1(x,y,z);
        }
        ans = 0;
        while (1)
        {
            k = bfs(1,n);
            if (k == 0) break;
            for (i = 1 ; i <= n ; i++)
                f[i] = adj[i];
            while (1)
            {
                k = dfs(1,n,a7);
                if (k == 0) break;
                ans += k;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
最小边数最小割
#define maxn 2000
#define inf 1ll<<60
#define mod 100001
#define maxm 3000
int n,m;
int level[maxn],que[maxn];
int head[maxn],lon;
int S, T;
__int64 min(__int64 a,__int64 b)
{
    if(a<b) return a;
    else return b;
}
struct EDGE
{
    int next,to;
    __int64 c;
}e[maxm];
void edgeini()
{
    memset(head,-1,sizeof(head));
    lon=-1;
}
void edgemake(int from,int to,__int64 c)
{
    e[++lon].c=c;
    e[lon].to=to;
    e[lon].next=head[from];
    head[from]=lon;
}
void make(int from,int to,__int64 c)
{
    edgemake(from,to,c);
    edgemake(to,from,0);
}
bool makelevel(int s,int t)
{
    memset(level,0,sizeof(level));
    int front=1,end=0;
    que[++end]=s;
    level[s]=1;
    while(front<=end)
    {
        int u=que[front++];
        if(u==t) return true;
        for(int k=head[u];k!=-1;k=e[k].next)
        {
            int v=e[k].to;
            if(!level[v]&&e[k].c)
            {
                que[++end]=v;
                level[v]=level[u]+1;
            }
        }
    }
    return false;
}
__int64 dfs(int now,int t,__int64 maxf)
{
    if(now==t||maxf==0) return maxf;
    __int64 ret=0;
    for(int k=head[now];k!=-1;k=e[k].next)
    {
        int u=e[k].to;
        if(level[u]==level[now]+1&&e[k].c)
        {
            __int64 f=dfs(u,t,min(e[k].c,maxf-ret));
            e[k].c-=f;
            e[k^1].c+=f;
            ret+=f;
            if(ret==maxf) return ret;
        }
    }
    if(ret==0) level[now]=0;
    return ret;
}
__int64 maxflow(int s,int t)
{
    __int64 ret=0;
    while(makelevel(s,t))
        ret+=dfs(s,t,inf);
    return ret;
}
int main()
{
    int cas;
    int sum=0;
    scanf("%d",&cas);
    while(cas--)
    {
        sum++;
        int i,j;
        int u,v,flag;
        __int64 w;
        scanf("%d%d",&n,&m);
        edgeini();
        scanf("%d%d",&S,&T);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%I64d",&u,&v,&w);
            make(u,v,w*mod+1);
        }
        printf("%d\n",maxflow(S,T)%mod);
    }
    return 0; 
}
二分图匹配
最小顶点覆盖=最大匹配
最大独立集=n-最大匹配
int n , m , a[1001][1001] , p[1001] , f[1001] , sum; 
int dfs(int x)
{
    int i;
    for (i = 1 ; i <= n ; i++)
    {
        if (a[x][i] && f[i] == 0)
        {
            f[i] = 1;
            if (p[i] == 0 || dfs(p[i]))
            {
                p[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main ()
{
    int i , j , x , y , t;
    cin >> t;
    while (t)
    {
        t--;
        scanf("%d%d",&n,&m);
        for (i = 1 ; i <= n ; i++)
        {
            p[i] = 0;
            for (j = 1 ; j <= n ; j++)
                a[i][j] = 0;
        }
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d",&x,&y);
            a[x][y] = 1;
        }
        sum = 0;
        for (i = 1 ; i <= n ; i++)
        {
            for (j = 1 ; j <= n ; j++)
                f[j] = 0;
            if (dfs(i))
                sum++;
        }
        printf("%d\n",n-sum);
    }
    return 0;
}  
最大权匹配
int a7 = 1e9+7;
int n;
int a[301][301]; //村民愿意付的钱 
int p[301]; //记录房子被哪个村民匹配(初始为0) 
int q1[301]; //村民付钱的期望值 
int q2[301]; //房子被购买的期望值(初始为0)
int f1[301]; //每轮被匹配过的村民 
int f2[301]; //每轮被匹配过的房子 
int g[301]; //房子被购买还差多少期望值 
int dfs(int x)
{
    int i , gap;
    f1[x] = 1;
    for (i = 1 ; i <= n ; i++)
    {
        if (f2[i] == 0)
        {
            gap = q1[x]+q2[i]-a[x][i];
            if (gap == 0)
            {
                f2[i] = 1;
                if (p[i] == 0 || dfs(p[i]))
                {
                    p[i] = x;
                    return 1;
                }   
            }
            else g[i] = min(g[i],gap);
        }
    }   
    return 0;
}
int km()
{
    int i , j , k , ans;
    for (i = 1 ; i <= n ; i++)
    {
        p[i] = 0;
        q2[i] = 0;
    }
    for (i = 1 ; i <= n ; i++)
    {
        q1[i] = a[i][1];
        for (j = 2 ; j <= n ; j++)
            q1[i] = max(q1[i],a[i][j]);
    }
    for (i = 1 ; i <= n ; i++)
    {
        for (j = 1 ; j <= n ; j++)
            g[j] = a7;
        while (1)
        {
            for (j = 1 ; j <= n ; j++)
            {
                f1[j] = 0;
                f2[j] = 0;
            }
            if (dfs(i)) break;
            k = a7;
            for (j = 1 ; j <= n ; j++)
                if (f2[j] == 0)
                    k = min(k,g[j]);
            for (j = 1 ; j <= n ; j++)
            {
                if (f1[j]) q1[j] -= k;
                if (f2[j]) q2[j] += k;
                else g[j] -= k;
            }
        }
    }
    ans = 0;
    for (i = 1 ; i <= n ; i++)
        ans += a[p[i]][i];
    return ans;
}
int main ()
{
    int i , j;
    while (~scanf("%d",&n))
    {
        for (i = 1 ; i <= n ; i++)
            for (j = 1 ; j <= n ; j++)
                scanf("%d",&a[i][j]);
        printf("%d\n",km());
    }
    return 0;
}
LCA
struct mmp{
    int p , d;
}tr[maxn*8];
struct abc{
    int x , y , l , d;
}lca[maxn*5];
int n , m , f[maxn] , id[maxn] , len , ans , fa[maxn];
vector <int> a[maxn];
vector <mmp> q;
bool cmp(abc x , abc y)
{
    return x.d > y.d;
}
mmp find(mmp p1 , mmp p2)
{
    if (p1.d == -1 || p2.d == -1) 
    {
        if (p1.d == -1) return p2;
        else return p1;
    }
    else
    {
        if (p2.d < p1.d) return p2;
        else return p1;
    }
}
void putin(int num , int l , int r , int x , mmp p)
{
    if (l <= x && x <= r)
    {
        if (l == r) tr[num] = p;
        else
        {
            int nn = num*2 , mm = (l+r)/2;
            putin(nn,l,mm,x,p);
            putin(nn+1,mm+1,r,x,p);
            tr[num] = find(tr[nn],tr[nn+1]);
        }
    }
}
 
mmp getout(int num , int l , int r , int x , int y)
{
    if (x > r || l > y) 
    {
        mmp p;
        p.d = -1;
        return p;
    }
    else
    {
        if (x <= l && r <= y) return tr[num];
        else 
        {
            int nn = num*2 , mm = (l+r)/2;
            return find(getout(nn,l,mm,x,y),getout(nn+1,mm+1,r,x,y));
        }
    }
}
void dfs(int p , int d , int b)
{
    mmp pp;
    pp.p = p;
    pp.d = d;
    q.push_back(pp);
    id[p] = q.size();
    fa[p] = b;
    for (int i = 0 ; i < a[p].size() ; i++)
    {
        if (a[p][i] != b) 
        {
            dfs(a[p][i],d+1,p);
            q.push_back(pp);
        }
    }
}
void cutdown(int p)
{
    if (!f[p])
    {
        f[p] = 1;
        for (int i = 0 ; i < a[p].size() ; i++) if (a[p][i] != fa[p]) cutdown(a[p][i]);
    }
}
int main ()
{
    int i , j , x , y;
    while (~scanf("%d",&n))
    {
        ans = 0;
        for (i = 0 ; i <= n ; i++)
        {
            a[i].clear();
            f[i] = 0;
        }
        q.clear();
        for (i = 1 ; i <= n ; i++)
        {
            scanf("%d%d",&x,&y);
            a[x].push_back(y);
            a[y].push_back(x);
        }
        dfs(0,0,-1);
        len = q.size();
        for (i = 0 ; i < len ; i++) 
putin(1,1,len,i+1,q[i]);
        scanf("%d",&m);
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d",&x,&y);
            mmp p = getout(1,1,len,min(id[x],id[y]),max(id[x],id[y]));
            lca[i].x = x;
            lca[i].y = y;
            lca[i].l = p.p;
            lca[i].d = p.d;
        }
        sort(lca+1,lca+m+1,cmp);
        for (i = 1 ; i <= m ; i++)
        {
            if (!f[lca[i].x] && !f[lca[i].y])
            {
                ans++;
                cutdown(lca[i].l);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
强连通分量缩点
struct mmp{
    LL x , y , r;
    int c;
}p[maxn];
int n , id[maxn] , vis[maxn] , scc , cost[maxn] , ru[maxn] , ans;
vector <int> a[maxn] , q , b[maxn] , c[maxn];
LL dis;
LL distance(int i , int j)
{
    LL dx = abs(p[i].x-p[j].x);
    LL dy = abs(p[i].y-p[j].y);
    return dx*dx+dy*dy;
}
void dfs1(int pp)
{
    vis[pp] = 1;
    for (int i = 0 ; i < a[pp].size() ; i++) 
if (!vis[a[pp][i]]) dfs1(a[pp][i]);
    q.push_back(pp);
    return;
}
int dfs2(int pp)
{
    int mi;
    id[pp] = scc;
    mi = p[pp].c;
    vis[pp] = 1;
    for (int i = 0 ; i < b[pp].size() ; i++) 
if (!vis[b[pp][i]]) mi = min(mi,dfs2(b[pp][i]));
    return mi;
}
int main ()
{
    int t , tt , i , j , x , y;
    cin >> tt;
    for (t = 1 ; t <= tt ; t++)
    {
        scanf("%d",&n);
        scc = 0;
        ans = 0;
        for (i = 1 ; i <= n ; i++)
        {
            a[i].clear();
            b[i].clear();
            c[i].clear();
            id[i] = 0;
            vis[i] = 0;
            cost[i] = 0;
            ru[i] = 0;
            scanf("%lld%lld%lld%d",&p[i].x,&p[i].y,&p[i].r,&p[i].c);
            p[i].r *= p[i].r;
        }
        for (i = 1 ; i <= n ; i++)
        {
            for (j = i+1 ; j <= n ; j++)
            {
                dis = distance(i,j);
                if (dis <= p[i].r) 
                {
                    a[i].push_back(j);
                    b[j].push_back(i);
                }
                if (dis <= p[j].r) 
                {
                    a[j].push_back(i);
                    b[i].push_back(j);
                }
            } 
        }
        for (i = 1 ; i <= n ; i++) if (!vis[i]) dfs1(i);
        for (i = 1 ; i <= n ; i++) vis[i] = 0;
        for (i = q.size()-1 ; i >= 0 ; i--) 
        {
            if (!vis[q[i]]) 
            {
                scc++;
                cost[scc] = dfs2(q[i]);
            }
        }
        for (i = 1 ; i <= n ; i++)
        {
            for (j = 0 ; j < a[i].size() ; j++)
            {
                x = id[i];
                y = id[a[i][j]];
                if (x != y) 
                {
                    c[x].push_back(y);
                    ru[y]++;
                }
            }
        }
        for (i = 1 ; i <= scc ; i++) 
if (!ru[i]) ans += cost[i];
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}
双集合最短路
struct mmp{
    int x; 
    long long r;
    mmp(){}
    mmp(int a , long long b){x = a; r = b;}
};
bool operator < (mmp x , mmp y)
{
    return x.r > y.r;
}
vector <mmp> ed[100010];
int n , m , k , p[100010] , c[100010][20];
long long dis[100010] , ans;
void dijkstra(int b)
{
    int i;
    for (i = 0 ; i <= n ; i++)
        dis[i] = 10000000001;
    priority_queue<mmp> q;
    dis[b] = 0;
    q.push(mmp(b,dis[b]));
    while (!q.empty())
    {
        mmp x = q.top();
        q.pop();
        if (dis[x.x] < x.r) continue;
        for (i = 0 ; i < ed[x.x].size() ; i++)
        {
            mmp y = ed[x.x][i];
            if (dis[y.x] > x.r+y.r)
            {
                dis[y.x] = x.r+y.r;
                q.push(mmp(y.x,dis[y.x]));
            }
        }
    }
}
void rundis(int v , int j)
{
    int i;
    ed[0].clear();
    for (i = 1 ; i <= k ; i++)
        if (c[i][j] == v) ed[0].push_back(mmp(p[i],0));
    dijkstra(0);
    for (i = 1 ; i <= k ; i++)
        if (c[i][j] != v) ans = min(ans,dis[p[i]]);
}
int main()
{
    int t , tt , i , j , x , y; 
    long long z;
    cin >> tt;
    for (t = 1 ; t <= tt ; t++)
    {
        cin >> n >> m;
        for (i = 0 ; i <= n ; i++)
        {
            ed[i].clear();
        }
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d%lld",&x,&y,&z);
            ed[x].push_back(mmp(y,z));
        }
        cin >> k;
        for (i = 1 ; i <= k ; i++)
        {
            scanf("%d",&p[i]);
            x = p[i];
            for (j = 1 ; j <= 18 ; j++)
            {
                c[i][j] = x%2;
                x /= 2;
            }
        }
        ans = 10000000001;
        for (j = 1 ; j <= 18 ; j++)
        {
            rundis(0,j);
            rundis(1,j);
        }
        cout << "Case #" << t << ": " << ans << "\n";
    }
    return 0;
}
次短路
typedef pair<long long,long long> P;  
struct edge{  
    long long to;
    long long v;  
    edge(long long to,long long v):to(to),v(v){}  
    edge(){}  
};
const long long maxn = 100010;  
const long long maxe = 200010;  
const long long INF = 9223372036854775807;
long long V,E;  
vector<edge> g[maxn];  
long long d[maxn],d2[maxn];
void dijkstra(long long s)  
{  
    priority_queue<P,vector<P>,greater<P> > pq;  
    for(long long i=1;i<=V;i++)  
    {  
        d[i]=INF;  
        d2[i]=INF;  
    }  
    d[s]=0;  
    pq.push(P(0,s));  
    while(pq.size())  
    {  
        P nowe=pq.top();pq.pop();  
        if(nowe.first>d2[nowe.second]) continue;  
        for(long long v=0;v<(long long)g[nowe.second].size();v++)  
        {  
            edge nexte=g[nowe.second][v];  
            long long dis=nowe.first+nexte.v;  
            if(d[nexte.to]>dis)  
            {  
                swap(dis,d[nexte.to]);  
                pq.push(P(d[nexte.to],nexte.to));  
            }  
            if(d2[nexte.to]>dis&&d[nexte.to]<dis)
            {  
                d2[nexte.to]=dis;  
                pq.push(P(d2[nexte.to],nexte.to));
            }  
        }  
    }  
}  
int main()  
{  
    long long s , t;
    cin >> t;
    while (t--)
    {
        scanf("%lld%lld",&V,&E);  
        {  
            for(long long i=1;i<=V;i++)  
                g[i].clear();  
            for(long long i=1;i<=E;i++)  
            {  
                long long v,f,t;  
                scanf("%lld%lld%lld",&f,&t,&v);  
                g[f].push_back(edge(t,v));  
                g[t].push_back(edge(f,v));  
            }  
            s=1;
            dijkstra(s);  
            printf("%lld\n",d2[V]);  
        }  
    }
    return 0;  
}  
最小生成树
struct mmp{
    int x , y , z;
}a[10001];
int n , m , k , f[101] , ans , sum;
int getf(int x)
{
    if (f[x] == x)
        return x;
    else
    {
        f[x] = getf(f[x]);
        return f[x];
    }
}
bool cmp(struct mmp x , struct mmp y)
{
    return x.z < y.z;
}
int main ()
{
    int i , j , fx , fy , x , y , z , t;
    scanf("%d",&n);
    while (n > 0)
    {
        m = n*(n-1)/2;
        for (i = 1 ; i <= n ; i++)
            f[i] = i;
        k = 0;
        sum = 0;
        for (i = 1 ; i <= m ; i++)
        {
            scanf("%d%d%d%d",&x,&y,&z,&t);
            if (t == 0)
            {
                k++;
                a[k].x = x;
                a[k].y = y;
                a[k].z = z;
            }
            else
            {
                fx = getf(x);
                fy = getf(y);
                if (fx != fy)
                {
                    f[fx] = fy;
                    sum++;
                }
            }
        }
        ans = 0;
        sort(a+1,a+k+1,cmp);
        for (i = 1 ; i <= k && sum < n-1 ; i++)
        {
            fx = getf(a[i].x);
            fy = getf(a[i].y);
            if (fx != fy)
            {
                ans += a[i].z;
                f[fx] = fy;
                sum++;
            }
        }
        printf("%d\n",ans);
        scanf("%d",&n);
    }
    return 0;
}
树状数组
int n , a[50001] , tr[50001] , lb[50001];
int t , tt;
char c[100];
void putin(int x , int y)
{
    while (x <= n)
    {
        tr[x] += y;
        x += lb[x];
   }
}
int sum(int x)
{
    int s = 0;
    while (x > 0)
    {
        s += tr[x];
        x -= lb[x];
    }
    return s;
}
int main ()
{
    int i , j , x , y;
    cin >> tt;
    for (t = 1 ; t <= tt ; t++)
    {
        scanf("%d",&n);
        for (i = 1 ; i <= n ; i++)
        {
            lb[i] = i&(-i);
            tr[i] = 0;
        }
        for (i = 1 ; i <= n ; i++)
        {
            scanf("%d",&a[i]);
            putin(i,a[i]);
        }
        printf("Case %d:\n",t);
        scanf("%s",c);
        while (c[0] != 'E')
        {
            scanf("%d%d",&x,&y);
            if (c[0] == 'A')
                putin(x,y);
            if (c[0] == 'S')
                putin(x,-y);
            if (c[0] == 'Q')
                printf("%d\n",sum(y)-sum(x-1));         }
            scanf("%s",c);
        }
    }
    return 0;
}
线段树逆序对
struct mmp{
    int n , p;
}a[500001];
int n , b[500001];
long long tr[2000001] , ans;
bool cmp1(mmp x , mmp y)
{
    return x.n < y.n;
}
bool cmp2(mmp x , mmp y)
{
    return x.p < y.p;
}
 
void putin(int num , int l , int r , int x)
{
    if (l <= x && x <= r)
    {
        if (l == r)
            tr[num]++;
        else
        {
            int nn = num*2 , mm = (l+r)/2;
            putin(nn,l,mm,x);
            putin(nn+1,mm+1,r,x);
            tr[num] = tr[nn]+tr[nn+1];
        }
    }
}
 
long long getout(int num , int l , int r , int x , int y)
{
    if (l > y || x > r)
        return 0;
    else
    {
        if (x <= l && r <= y)
            return tr[num];
        else
        {
            int nn = num*2 , mm = (l+r)/2;
            return getout(nn,l,mm,x,y)+getout(nn+1,mm+1,r,x,y);
        }
    }
}
int main ()
{
    int i , j;
    cin >> n;
    while (n != 0)
    {
        for (i = 1 ; i <= n*4 ; i++)
            tr[i] = 0;
        for (i = 1 ; i <= n ; i++)
        {
            scanf("%d",&a[i].n);
            a[i].p = i;
        }
        sort(a+1,a+n+1,cmp1);
        b[1] = 1;
        j = 1;
        for (i = 2 ; i <= n ; i++)
        {
            if (a[i].n > a[i-1].n) j++;
            b[i] = j;
        }
        for (i = 1 ; i <= n ; i++)
            a[i].n = b[i];
        sort(a+1,a+n+1,cmp2);
        ans = 0;
        for (i = 1 ; i <= n ; i++)
        {
            putin(1,1,j,a[i].n);
            ans += getout(1,1,j,a[i].n+1,j);
        }
        printf("%lld\n",ans);
        scanf("%d",&n);
    }
    return 0;
}
矩形面积并
int n,t[10005];
double hhh[10005],sum[10005];
struct data{double x1,x2,y;int f;}a[10005];
inline bool operator<(data a,data b){return a.y<b.y;}
int find(double x)
{
    int l=1,r=2*n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(hhh[mid]<x)l=mid+1;
        else if(hhh[mid]==x)return mid;
        else r=mid-1;
    }
}
void pushup(int k,int l,int r)
{
    if(t[k])sum[k]=hhh[r+1]-hhh[l];
    else if(l==r)sum[k]=0;
    else sum[k]=sum[k<<1]+sum[k<<1|1];
}
void update(int k,int l,int r,int x,int y,int f)
{
    if(x==l&&y==r)
    {t[k]+=f;pushup(k,l,r);return;}
    int mid=(l+r)>>1;
    if(y<=mid)update(k<<1,l,mid,x,y,f);
    else if(x>mid)update(k<<1|1,mid+1,r,x,y,f);
    else
    {
        update(k<<1,l,mid,x,mid,f);
        update(k<<1|1,mid+1,r,mid+1,y,f);
    }
    pushup(k,l,r);
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(t,0,sizeof(t));
        memset(sum,0,sizeof(sum));
        double x1,y1,x2,y2;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[2*i-1].x1=a[2*i].x1=x1;
            a[2*i-1].x2=a[2*i].x2=x2;
            a[2*i-1].y=y1;a[2*i].y=y2;
            a[2*i-1].f=1;a[2*i].f=-1;
            hhh[2*i-1]=x1;hhh[2*i]=x2;
        }
        sort(hhh+1,hhh+2*n+1);
        sort(a+1,a+2*n+1);
        double ans=0;
        for(int i=1;i<=2*n;i++)
        {
            int l=find(a[i].x1),r=find(a[i].x2)-1;
            if(l<=r)update(1,1,2*n,l,r,a[i].f);
            ans+=sum[1]*(a[i+1].y-a[i].y);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}
主席树
struct mmp{
    int l , r , s;
}tr[600001];
int n , q , a[30001];
int l[1000001] , top , root[30001]; 
int setup(int l , int r)
{
    top++;
    int rt = top;
    tr[rt].l = 0;
    tr[rt].r = 0;
    tr[rt].s = 0;
    if (l == r) return rt;
    int mm = (l+r)/2;
    tr[rt].l = setup(l,mm);
    tr[rt].r = setup(mm+1,r);
    return rt;
}
void putin(int l , int r , int &x , int y , int p , int s)
{
    top++;
    x = top;
    tr[x] = tr[y];
    tr[x].s += s;
    if (l == r) return;
    int mm = (l+r)/2;
    if (mm >= p)
        putin(l,mm,tr[x].l,tr[y].l,p,s);
    else
        putin(mm+1,r,tr[x].r,tr[y].r,p,s);
}
int getout(int l , int r , int x , int p)
{
    if (l == r) return tr[x].s;
    int mm = (l+r)/2;
    if (mm >= p)
        return tr[tr[x].r].s + getout(l,mm,tr[x].l,p);
    else
        return getout(mm+1,r,tr[x].r,p);
}
 
int main ()
{
    int i , j , x , y , z;
    cin >> n;
    for (i = 1 ; i <= n ; i++)
        scanf("%d",&a[i]);
    root[0] = setup(1,n);
    for (i = 1 ; i <= n ; i++)
    {
        int z = a[i];
        if (l[z] == 0)
        {
            putin(1,n,root[i],root[i-1],i,1);
        }
        else
        {
            putin(1,n,root[i],root[i-1],l[z],-1);
            putin(1,n,root[i],root[i],i,1);
        }
        l[z] = i;
    }
    cin >> q;
    for (i = 1 ; i <= q ; i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",getout(1,n,root[y],x));
    }
    return 0;
}
最长回文子串
char a[300005] , b[300005];
int pos , p[300005] , ma , n;
 
int manacher()
{
    int i;
    pos = 1;
    ma = 0;
    for (i = 0 ; i <= n ; i++)
        p[i] = 0;
    for (i = 1 ; i <= n ; i++)
    {
        if (i < p[pos]+pos)
            p[i] = min(p[pos]+pos-i,p[2*pos-i]);
        else
            p[pos] = 1;
        while (b[i-p[i]]==b[i+p[i]])
            p[i]++;
        if (i+p[i]>pos+p[pos])
            pos = i;
        ma = max(ma,p[i]);
    }
    return ma - 1;
}
int main ()
{
    int i , j;
    while (~scanf("%s",a))
    {
        n = strlen(a);
        b[0] = '#';
        for (i = 1 ; i <= n ; i++)
        {
            b[i*2-1] = '%';
            b[i*2] = a[i-1];  
        }
        b[n*2+1] = '%';
        b[n * 2 + 2] = '\0';
        n = n*2+1;
        cout << manacher() << "\n";
    }
    return 0;
}
字典树
struct mmp{
    int p[26] , s;
}tr[1000001];
char a[11];
int top , l; 
void putin()
{
    int i , p=0;
    for (i = 0 ; i < l ; i++)
    {
        if (tr[p].p[a[i]-'a'] == 0)
        {
            top++;
            tr[p].p[a[i]-'a'] = top;
            p = top;
        }
        else p = tr[p].p[a[i]-'a'];
        tr[p].s++;
    }
}
int getout()
{
    int i , p=0 , gg=0;
    for (i = 0 ; i < l ; i++)
    {
        p = tr[p].p[a[i]-'a'];
        if (p == 0)
        {
            gg = 1;
            break;
        }
    }
    if (gg)
        return 0;
    else
        return tr[p].s;    
}
int main ()
{
    int i , j;
    gets(a);
    l = strlen(a);
    while (l > 0)
    {
        putin();
        gets(a);
        l = strlen(a);
    }
    while (~scanf("%s",&a))
    {
        l = strlen(a);
        printf("%d\n",getout());
    }
    return 0;
}
kmp
char a[100000] , b[100000] , c;
int la , lb , next[100000] , x , y , tt;
void getnext()
{
    int j = 0 , k = -1;
    next[0] = -1;
    while (j < lb)
    {
        if (k == -1 || b[j] == b[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else k = next[k];
    }
} 
int kmp()
{
    int count = 0 , i = 0 , j = 0;
    getnext();
    while (i < la)
    {
        if (j == -1 || a[i] == b[j])
        {
            i++;
            j++;
        }
        else j = next[j];
        if (j == lb)
        {
            count++;
            j = next[j];
        }
    }
    return count;
} 
int main ()
{
    int i , j;
    cin >> tt;
    c = getchar();
    while (tt)
    {
        tt--;
        gets(b);
        lb = strlen(b);
        gets(a);
        la = strlen(a);
        cout << kmp() << "\n";
    }
    return 0;
}
矩阵快速幂
int n , x , a7 = 1e9+7;
long long d[102][102] , d0[102][102] , a[102][102] , b[102][102];
void quickpow(int t)
{
    int i , j,  k;
    if (t == 1) return;
    quickpow(t/2);
    memset(a,0,sizeof(a));
    for (i = 1 ; i <= 101 ; i++)
    {
        for (j = 1 ; j <= 101 ; j++)
        {
            for (k = 1 ; k <= 101 ; k++)
            {
                a[i][k] += d[i][j]*d[j][k];
                a[i][k] %= a7; 
            }
        }
    }
    if (t%2 == 1)
    {
        for (i = 1 ; i <= 101 ; i++)
            for (j = 1 ; j <= 101 ; j++)
                b[i][j] = a[i][j];
        memset(a,0,sizeof(a));
        for (i = 1 ; i <= 101 ; i++)
        {
            for (j = 1 ; j <= 101 ; j++)
            {
                for (k = 1 ; k <= 101 ; k++)
                {
                    a[i][k] += b[i][j]*d0[j][k];
                    a[i][k] %= a7;
                }
            }
        }
    }
    for (i = 1 ; i <= 101 ; i++)
        for (j = 1 ; j <= 101 ; j++)
            d[i][j] = a[i][j];
}
int main ()
{
    int i , j;
    cin >> n >> x;
    if (x == 0)
        cout << "1\n";
    else
    {
        for (i = 1 ; i <= n ; i++)
        {
            scanf("%d",&j);
            d[j][1]++;
            d[j][101]++;
        }
        d[101][101] = 1;
        for (i = 1 ; i < 100 ; i++)
            d[i][i+1] = 1;
        for (i = 1 ; i <= 101 ; i++)
        {
            for (j = 1 ; j <= 101 ; j++)
            {
                d0[i][j] = d[i][j];
            }
        }
        quickpow(x);
        cout << (d[1][101]+d[101][101])%a7 << "\n";
    }
    return 0;
}
数位dp
山谷数字
int t;
long long l , dp[1001][1001][2] , ans , ma , a7 = 1e9+7;
char a[1001];
long long dfs(int x , int p , int s , int c)
{
    int i , mm;
    long long aa = 0;
    if (x == l) return 1;
    if (dp[x][p][s] >= 0 && c == 0) return dp[x][p][s];
    if (c == 0)
        mm = 9;   } 
    else
        mm = a[x]-'0';
    for (i = 0 ; i <= mm ; i++)
    {
        if (s == 0)
        {
            if (i > p)
            {
                if (i == mm && c == 1)
                    aa += dfs(x+1,i,1,1);
                else
                    aa += dfs(x+1,i,1,0);
                aa %= a7;
            }
            else
            {
                if (i == mm && c == 1)
                    aa += dfs(x+1,i,0,1);
                else
                    aa += dfs(x+1,i,0,0);
                aa %= a7;
            }
        }
        else
        {
            if (i >= p) 
            {
                if (i == mm && c == 1)
                    aa += dfs(x+1,i,1,1);
                else
                    aa += dfs(x+1,i,1,0);
                aa %= a7;
            }
        }
    }
    if (c == 0) dp[x][p][s] = aa;
    return aa;
}
int main ()
{
    int i , j;
    cin >> t;
    while (t--)
    {
        scanf("%s",a);
        l = strlen(a);
        for (i = 0 ; i <= 101 ; i++)
        {
            for (j = 0 ; j <= 101 ; j++)
            {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }
        ans = 0;
        for (i = 0 ; i < l ; i++)
        {
            if (i == 0)
                ma = a[i]-'0';
            else
                ma = 9;
            for (j = 1 ; j <= ma ; j++)
            {
                if (i == 0 && j == ma)
                    ans += dfs(i+1,j,0,1);
                else
                    ans += dfs(i+1,j,0,0);
                ans %= a7;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
高精度乘法
typedef long long LL;
typedef pair <int,int> II;
const int maxn = 1e5+10;
const int maxint = 0x3f3f3f3f;
const int mod = 1e9+7;
const double pi = acos(0.0)*2.0;
typedef complex <double> CD;
//Cooley—Tukey的fft算法,迭代实现。
//c为false时计算逆fft 
void fft(vector <CD> &a , bool c)
{
    int i , j , k , n = a.size();
    //原地快速 bit reversal 
    for (i = 0 , j = 0 ; i < n ; i++)
    {
        if (j > i) swap(a[i],a[j]);
        k = n;
        while (j & (k >>= 1)) j &= ~k;
        j |= k;
    }
    double pp = c ? -pi : pi;
    for (int step = 1 ; step < n ; step <<= 1)
    {
        //通过一系列蝴蝶操作合并为一个2*step点dft 
        double alpha = pp/step;
        //为求高效,枚举下标k,对于一个下标k执行所有dft合并中该下标对应的蝴蝶操作,即通过e[k]和o[k]求x[k] 
        for (k = 0 ; k < step ; k++)
        {
            //计算omegak^k 
            CD omegak = exp(CD(0,alpha*k));
            for (int ep = k ; ep < n ; ep += step << 1)
            {
                //ep是某次dft合并中e[k]的下标 
                int op = ep + step; //op是dft合并中o[k]在原始序列中的下标 
                CD t = omegak*a[op]; //蝴蝶操作:x1*omega^k 
                a[op] = a[ep]-t; //蝴蝶操作:y1 = x0-t
                a[ep] += t; //蝴蝶操作:y0 = x0+t;
            }
        }
    }
    if (c) for (i = 0 ; i < n ; i++) a[i] /= n;
}
//fft实现快速多项式乘法 
vector <double> operator *(const vector <double> &v1 , const vector <double> &v2)
{
    int i , s1 = v1.size() , s2 = v2.size() , s = 2;
    while (s < s1+s2) s <<= 1;
    vector <CD> a(s,0) , b(s,0); //把fft的输入长度补成2的幂,不小于v1和v2的长度和
    for (i = 0 ; i < s1 ; i++) a[i] = v1[i];
    fft(a,0);
    for (i = 0 ; i < s2 ; i++) b[i] = v2[i];
    fft(b,0);
    for (i = 0 ; i < s ; i++) a[i] *= b[i];
    fft(a,1);
    vector <double> res(s1+s2-1);
    for (i = 0 ; i < s1+s2-1 ; i++) res[i] = a[i].real(); //虚部均为0 
    return res;
}
vector <double> v1 , v2 , res;
int f[maxn*2];
char s1[maxn] , s2[maxn];
int main ()
{
    int T , n , m , c , a , b , i;
    while (~scanf("%s%s",s1,s2))
    {
        v1.clear();
        v2.clear();
        for (i = 0 ; s1[i] ; i++) v1.push_back(s1[i]-'0');
        for (i = 0 ; s2[i] ; i++) v2.push_back(s2[i]-'0');
        res = v1*v2;
        f[0] = 0;
        for (i = 0 ; i < res.size() ; i++) f[i+1] = (int)(res[i]+0.5);
        for (i = res.size()-1 ; i >= 0 ; i--)
        {
            f[i] += f[i+1]/10;
            f[i+1] %= 10;
        }
        int pre = 0;
        while (pre < res.size() && !f[pre]) pre++;
        if (pre > res.size()) 
            putchar('0');
        else
            for (i = pre ; i <= res.size() ; i++) printf("%d",f[i]);
        puts("");
    }
    //system("PAUSE");
    return 0;
}
/*大根堆*/
#include <queue>
priority_queue <int> q;  
n = q.size(); 返回堆大小
bool = q.empty(); 判断堆是否为空
q.push(n); 加入堆
n = q.top(); 查询顶
q.pop();    删除顶
q.clear(); 清空set
队列queuepop删头元素push从尾加入元素
q.front();
q.back();
q.earse();
 
 
二分搜索/离散化
#include <algorithm>
i = Lower_bound(a,n,t);
a 数组指针(有序)0~n-1
n 数组长度
t key
i 小于等于t的第一个值的位置
j = upper_bound(a,n,t);
j 大于x的第一个值的位置
 
 
有序去重
#include <iostream>
ans = unique(a+1,a+n+1)-a; (返回指针-头指针)
ans 最终长度
a[] 有序
n 数组长度
 
 
离散化模板
int i , size , n , a[100001] , b[100001];
scanf("%d",&n);
for (i = 1 ; i <= n ; i++)
scanf("%d",&a[i]);
sort(a,a+n);
size = unique(a+1,a+n+1)-a;
for (i = 1 ; i <= n ; i++)  
{
b[i] = lower_bound(a+1,a+size+1,b[i])-a; 
    printf("%d ",b[i]);
}
printf("\n");
 
 
stl <set>
#include <set>
set <int> q;
set <int> ::iterator iter; 迭代器(指针)
n = q.size(); 返回set大小
bool = q.empty(); 判断set是否为空
iter = q.begin(); 返回头指针
iter = q.end(); 返回尾指针
q.clear(); 清空set
q.insert(key); 插入key
n = q.count(key); 返回key值出现与否
q.erase(key/iter); 删除key值或iter位置的值
iter = q.find(key); 返回key值位置指针(没有则返回end()
multiset可以统计多个count情况
 
 
stl <vector>
#include <vector>
vector <int> q;
vector <int> ::iterator iter;
n = q.size(); 返回vector大小
bool = q.empty(); 判断vector是否为空
iter = q.begin();返回头指针
iter = q.end();返回尾指针
a = q.front();返回头元素
a = q.back();返回尾元素
q.clear(); 清空vector
q.erase(key/iter); 删除key值或iter位置的值
n = q.count(key); 查询key值出现的次数
iter = q.find(key); 返回key值位置指针(没有则返回end()
q.pop_back();移除尾元素
q.push_back(key);在尾添加元素
 
 
vector / set遍历模板(set有序)
for (iter = q.begin() ; iter != q.end() ; iter++)
cout << *iter << “\n;
for (int i = 0 ; i < q.size() ; i++)
cout << q[i] << “\n;
 
 
时间随机化
#include <ctime>
srand(time(NULL)); 
 
 
数组重置
#include <cstring>
int n , a[100001];
memset(a,0,n);
 
 
自定义快速排序
#include <algorithm>
struct mmp{
    int a , b;
}f[100001];
int n;
bool cmp(struct mmp x , struct mmp y)
{
    If (x.a == y.a)
        return x.b < y.b;
    else
        return x.a < y.a;     
}
sort(f+1,f+n+1,cmp);
 
 
结构体重载算符(改变堆的方向)
struct mmp {  
    int x , d;  
    mmp(){} 重载赋值
    mmp(int a , int b){x = a; d = b;} 重载赋值
    内:bool operator < (const mmp &b) const  
    {  
        return this->d > b.d;  
    }  
}q[100001];  
外:bool operator < (mmp a , mmp b)
{
    return a.d > b.d;
}
q[0] = mmp(1,1); 重载后可以直接赋值
 
 
stl <map>
#include <map>
map <char,int> q;
map <char,int> ::iterator iter; 
q[a] = 1; 插入pair(a,1) 
cout << q[a] << “\n; 输出1
pair <char,int> x = (a,2);
q.insert(x); 插入pair x(插入时后者覆盖前者)
cout << q[a] << “\n; 输出2
iter = q.find(a); 返回‘a’处指针(不存在返回end()
if (iter != q.end()) 判断存在性
    q.erase(iter); 删除iter位置的pair
q.erase(a);(无法判断存在性)
cout << q[a] << “\n; 输出0(已删除)
q.size();
q.clear();
q.empty();
 
 
map遍历模板(first有序)
for (iter = q.begin() ; iter != q.end() ; iter++)
cout << iter->first << -> << iter->second << “\n;

This snippet took 0.15 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).