#include <bits/stdc++.h>
using namespace std;
const int N=510,M=100010;
bool vis[N];
int n,m,a[N][N],dist[N];
int dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    for(int i=1;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(t==-1||dist[t]>dist[j])) t=j;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+a[t][j]);
        vis[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    memset(a,0x3f,sizeof(a));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        a[x][y]=min(a[x][y],w);
    }
    printf("%d\n",dijkstra());
    return 0;
}

题目描述

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

样例

输入：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出：
6 4 6 5

算法1

这个题啊，是数组模拟静态链表，首先让我们来回顾一下单链表的基本操作
插入，先将e[idx]定义为x，下一步，就是将这个节点指向k-1的下一个节点，然后让k-1指向这个节点，最后别忘了idx++；
删除，就直接将k-1指向它下一个节点的下一个节点即可，如果k为头节点，就直接将头节点指向下一个节点就好了。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;
void init()
{
    head=-1;
    idx=0;
}
void add_to_head(int x)
{
    e[idx]=x,ne[idx]=head,head=idx++;
}
void add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(int k)
{
    ne[k]=ne[ne[k]];
}
int main()
{
    int m;
    cin>>m;
    init();
    while(m--)
    {
        int k,x;
        char c;
        cin>>c;
        if(c=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        if(c=='D')
        {
            cin>>k;
            if(!k) head=ne[head];
            else remove(k-1);
        }
        if(c=='I')
        {
            cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i]) 
        cout<<e[i]<<" ";
    cout<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
int n,m,a[N];
LL c1[N],c2[N];
int lowbit(int x)
{
    return x&-x;
}
void add(LL c[],int x,LL y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}
LL Query(LL c[],int x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=c[i];
    return res;
}
LL sum(int x)
{
    return Query(c1,x)*(x+1)-Query(c2,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        add(c1,i,b);
        add(c2,i,(LL)b*i);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,k;
        char op[2];
        scanf("%s%d%d",op,&x,&y);
        if(*op=='C')
        {
            scanf("%d",&k);
            add(c1,x,k);
            add(c2,x,k*x);
            add(c1,y+1,-k);
            add(c2,y+1,-k*(y+1));
        }
        else printf("%lld\n",sum(y)-sum(x-1));
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
int n,m;
LL a[N],c[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}
LL Query(int x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=c[i];
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,k;
        char op[2];
        scanf("%s",op);
        if(*op=='C')
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",Query(x));
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=110,INF=1e9;
int n,w[N][N],f[N][N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==1&j==1) f[i][j]=w[i][j];
            else
            {
                f[i][j]=INF;
                if(i>1) f[i][j]=min(f[i-1][j]+w[i][j],f[i][j]);
                if(j>1) f[i][j]=min(f[i][j-1]+w[i][j],f[i][j]);
            }
        }
    printf("%d\n",f[n][n]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int t,r,c,w[N][N],f[N][N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&r,&c);
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                scanf("%d",&w[i][j]);
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                f[i][j]=max(f[i-1][j]+w[i][j],f[i][j-1]+w[i][j]);
        printf("%d\n",f[r][c]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=11;
char str[N][M];
int n,m,f[N][N];
int tiun(char a[],char b[])
{
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=1;i<=la;i++) f[i][0]=i;
    for(int i=1;i<=lb;i++) f[0][i]=i;
    for(int i=1;i<=la;i++)
    {
        for(int j=1;j<=lb;j++)
        {
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
        }
    }
    return f[la][lb];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%s",str[i]+1);
    while(m--)
    {
        char srt[N];
        int limie;
        scanf("%s %d",srt+1,&limie);
        int sum=0;
        for(int i=0;i<n;i++)
            if(tiun(str[i],srt)<=limie)
                sum++;
        printf("%d\n",sum);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m,f[N][N];
int main()
{
    scanf("%d %s %d %s",&n,a+1,&m,b+1);
    for(int i=1;i<=n;i++) f[i][0]=i;
    for(int i=1;i<=m;i++) f[0][i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]!=b[j])
                f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            else f[i][j]=min(f[i][j],f[i-1][j-1]);
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m,f[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s %s",a+1,b+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}