Dijkstra

#include<bits/stdc++.h>

using namespace std;

int n,m,s,x,y,c,dis[500005],v[500005],ans=0,sum=0,head[500005],pre[500005];

struct EDGE
{
    int cost;
    int go;
    int next;
}edge[500004];

void dijkstra()
{
    for(int i=0;i<=n;i++) dis[i]=2147483647;
    memset(v,0,sizeof(v));
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int flag=0;
        for(int j=1;j<=n;j++)
        {
            if(v[j]==0&&dis[j]<dis[flag]) flag=j;//距离最短的最小 
        }
        v[flag]=1;//记忆化标记 
        if(flag==0) break; 
        for(int j=head[flag];j!=0;j=edge[j].next)
        {
            int to=edge[j].go;
            if(dis[to]>dis[flag]+edge[j].cost)
            dis[to]=dis[flag]+edge[j].cost,pre[to]=flag;//pre用于输出路径 
        }   
    }
}
void add(int x,int y,int cc)
{
    sum++;
    edge[sum].go=y,edge[sum].cost=cc;
    edge[sum].next=head[x],head[x]=sum;
}

int main() 
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) cin>>x>>y>>c,add(x,y,c);
    dijkstra();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

最小表示法

例题：P1368

#include<bits/stdc++.h>

using namespace std;

int n,a[600005];
int mins()
{
    int i=1,j=2;
    while(i<=n&&j<=n)
    {
        int k=0;
        while(k<=n&&a[i+k]==a[j+k]) k++;
        //if(k==n) break;
        if(a[i+k]>a[j+k]) i=i+k+1;
        else j=j+k+1;
        if(i==j) j++;
    }
    return min(i,j);
}

int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n+1;i<=n*2;i++) a[i]=a[i-n];
    int s=mins();
    for(int i=1;i<=n;i++)
    cout<<a[s+i-1]<<" ";

    return 0;
}

用处：

有 环S 和 环T 判断是否一致

若暴力判断需要O(n^2)

若取每个环的最小表示法再判断是否一致则需要O(n)

单调队列&单调栈

单调栈

方便找左边或右边第一个比a[i]大或小的元素（O(n)）

int st[5000005]
int tp=0;
for(int i=n;i>=1;i--)
{
    while(tp&&a[i]>=a[s[tp]]) tp--;
    f[i]=s[tp];
    s[++tp]=i; 
} 

单调队列

方便找一段区间内的最大值或最小值（O(n)）

优化dp

#include<bits/stdc++.h>

using namespace std;

long long k,n,a[1000005],ansmax[1000005],ansmin[1000005],q[1000005];

void getmin()
{
    memset(q,0,sizeof(q));
    int t,h;t=0;h=1;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q[h]+k-1<i) h++;
        while(h<=t&&a[i]<a[q[t]]) t--;
        q[++t]=i;
        ansmin[i]=a[q[h]];
    }
}
void getmax()
{
    memset(q,0,sizeof(q));
    int t,h;t=0;h=1;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q[h]+k-1<i) h++;
        while(h<=t&&a[i]>a[q[t]]) t--;
        q[++t]=i;
        ansmax[i]=a[q[h]];
    }
}


int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    getmin();
    getmax();
    for(int i=k;i<=n-1;i++) cout<<ansmin[i]<<" ";
    cout<<ansmin[n]<<endl;
    for(int i=k;i<=n-1;i++) cout<<ansmax[i]<<" ";
    cout<<ansmax[n];

    return 0;
}

树状数组

#include<bits/stdc++.h>

using namespace std;

long long c[500005],n,m,kk,w,k;
long long lowbit(int a)//区间长度
{
    return a-(a&(a-1));//同等于n&(-n)
}

void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
long long sum(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        add(i,k);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>kk>>w>>k;
        if(kk==1)
            add(w,k);
        else
        {
            cout<<sum(k)-sum(w-1)<<endl;
        }
    }
    return 0;
}

记住下标从一开始，否则会陷入死循环