NOIP前模板整理

图

最短路径

#include <queue>
#define N 1000
typedef long long ll;
using namespace std;
int d[N], w[N][N], num[N];
ll dis[N];
queue<int> que;
void spfa(){
    for (int i=1;i<=n;i++) dis[i]=0x7fffff;
    que.push(1);d[1]=0;dis[1]=0;
    do{
        int h=que.front();
        d[h]=1,que.pop();
        for (int i=1,v;i<=num[h];i++){
            v = s[h][i];
            if (dis[v] > dis[h] + w[h][s[v]]) {
                dis[v] = dis[h] + w[h][v];
                if (!d[v]) que.push(v),d[v]=0;
            }
        }
    }while(!que.empty())
}

void floyd(){
    for (int k=1;k<=n;k++) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++){
                if (a[i][j] > a[i][k]+a[k][j]){
                    a[i][j] = a[i][k]+a[k][j];
                }
            }
        }
    }
} 

struct Node {
    int id,dis;
    bool operator < (const Node& rhs) const{
        return dis>rhs.dis;
    }
};
priority_queue<Node> q;
 
int vis[N],dis[N];
void dijkstra(int s){
    q.push((Node){s,0});
    while(!q.empty()) {
        int u=q.top().id;
        if(vis[u]) continue;
        vis[u]=1;
        trav(u,i) {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                q.push((Node){v,dis[v]});
            }
        }
    }
}

LCA

#define N 100005
#define D 21
struct Edge {
    int v,nxt;
}e[M];
int en=1,front[N];
void adde(int u,int v){
    e[++en]=(Edge){v,front[u]}; front[u]=en;
}
 
int fa[N][D],dep[N];
 
void dfs(int u){
    for(int i=1;i<D;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    trav(u,i) {
        int v=e[i].v;
        if(v!=fa[u][0]) {
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v);
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    int t=dep[u]-dep[v];
    for(int i=0;i<D;i++)
        if(t&(1<<i)) u=fa[u][i];
    if(u==v) return u;
    for(int i=D-1;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int main(){
    //input
    while(t--){
        scanf("%d%d", &u,&v);
        printf("%d
", dep[u]+dep[v]-2*dep[lca(u,v)]);
    }
}

RMQ

#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 50005
using namespace std;
int x, y, t, s, k;
int fa[maxn][20], fi[maxn][20], n, q, a[maxn];
void rmq(){
    for (int i=1;i<=n;i++) fa[i][0] = a[i], fi[i][0] = a[i];
    for (int i=1;i<=floor(log(n)/log(2));i++)
        for (int j=1;j<=n+1-(1<<i);j++){
            fa[j][i] = max(fa[j][i-1], fa[j+(1<<i-1)][i-1]);
            fi[j][i] = min(fi[j][i-1], fi[j+(1<<i-1)][i-1]);
        }
} 
int main(){
    while(scanf("%d%d", &n,&q)!=EOF){
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        rmq();
        for (int i=1;i<=q;i++){
            scanf("%d%d",&x,&y);
            k = (int)(log(y-x+1.0)/log(2.0));
            t=max(fa[x][k],fa[y-(1<<k)+1][k]),s=min(fi[x][k],fi[y-(1<<k)+1][k]);
            printf("%d
",t-s);
        }
    }
    return 0;
} 

输入输出优化

void read(int& x) {
    char c=getchar(); 
    while(!isdigit(c)) c=getchar();
    x=0;
    while(isdigit(c)) x=x*10+c-'0' , c=getchar();
}