蒟蒻 OIer の 联赛考前模板速记

JuRuoOIer · 2025-10-14 10:20:31 · 算法·理论

说明

小朋友没写过文，心灵还很脆弱，求求别蛐蛐了，有问题告诉我我会改的……

也许在考前打板子的时候你觉得板子写挂是小问题，很容易调。但上了考场后，你的代码里可不只有板子，此时调起来的难度就大了很多。所以把板子一遍写对的能力是十分重要的。

所以，本文旨在简要地概括各联赛级模板的算法思想以辅助记忆。这里默认你会这些板子。

借楼预告今年的山东省 NOIP 迷惑行为大赏。

更新日志：

• 28/11/2025：补充了一点平衡树的内容。
• 27/11/2025：完成本文，且在数学部分补充了一些东西。
• 25/11/2025：完成图论和杂项部分。

进度：完成。

文中给出代码的是作者惯用的写法，您有自己习惯的写法完全可以（而且最好这样做，因为考前改变一些习惯很危险）按照自己的习惯。

数据结构

数据结构模板尽管看上去很长，但其记忆难度其实是最低的。如果你还不能熟练记住，建议跟着下面的文字说明一步步画图，只要脑子里有图就能准确编写。

注：

• 在编写数据结构前，最好先想一想可不可以绕开数据结构。
• Kruskal 算法中涉及并查集，故不再单独写并查集。
• 由于有优先队列和平板电视，故不再单独写二叉堆。
• 由于树状数组被线段树偏序，故不再编写树状数组。

Trie

适用于维护多个串。

算法流程：

• 对每个结点维护结点上信息及出边 trans_i 表示字符 i 方向的下一个点。
• 修改字符串时直接沿着边走到需要的点进行操作即可，如果没有边则创建新点和新边。
• 查询字符串时直接沿着边走到需要的点进行查询即可，如果没有边说明该串不存在。

时间复杂度：单次修改/查询 O(|s|)，s 是操作的串的长度。

注意点：

• 即使查询全程都有边也要判断是否存在该串，以免出现查询某个存在的串的前缀的情况。

:::success[代码（P2580）]

struct node{
    ll trans[30],is,vis;
};
ll n,q,p=1;
string s;
node a[5000010];
void add(ll now,ll dep){
    if(dep==s.length()){
        a[now].is=1;
        return ;
    }
    ll c=s[dep]-'a';
    if(!a[now].trans[c]){
        a[now].trans[c]=(p++);
    }
    add(a[now].trans[c],dep+1);
}
ll query(ll now,ll dep){
    if(dep==s.length()){
        if(!a[now].is){
            return 0;
        }
        if(!a[now].vis){
            a[now].vis=1;
            return 1;
        }
        return 2;;
    }
    ll c=s[dep]-'a';
    if(!a[now].trans[c]){
        return 0;
    }
    return query(a[now].trans[c],dep+1);
}
const string ans[]={"WRONG","OK","REPEAT"};
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        add(0,0);
    }
    cin>>q;
    while(q--){
        cin>>s;
        cout<<ans[query(0,0)]<<endl;
    }
    return 0;
}

:::

ST 表

问题：多次区间查询，且单个位置贡献多次不影响查询的答案（例如最值）。

算法流程：

• 类似于 LCA 的 fa 数组，设 st_{i,j} 表示第 i 项起 2^j 项的最大值（或者其他询问的答案）。
• 外层枚举 i，内层枚举 j，预处理出 ST 表。
• 对于询问 [l,r] 直接将以 l 开头、长度为 \log(r-l+1) 的和以 r 结尾、长度为 \log(r-l+1) 的区间答案进行合并即可。预处理 \log 值即可实现 O(1) 查询。

复杂度：预处理 O(n\log n)，查询单次 O(1)。

:::success[代码（P3865）]

for(int i=1;i<17;i++){
    for(int j=0;j<n;j++){
        st[j][i]=max(st[j][i-1],st[min(j+(1ll<<i-1),n-1)][i-1]);
    } 
}
while(q--){
    cin>>l>>r;
    r--;l--;
    cout<<max(st[l][lg[r-l]],st[r-(1<<lg[r-l])+1][lg[r-l]])<<endl;
}

:::

线段树

如果你对 zkw 不是很熟悉就别写，zkw 也不是就那么完美。这里写最有可读性且不亏空间（因为其他值开 ll 而左右儿子只需要 int 所以空间利用率最低 50\%，但数组只需要二倍所以必然不亏空间）的结构体版本。

问题：多次单点或区间操作，维护容易进行区间合并的信息。

算法流程：

• 操作的区间完全包含节点表示的区间时，直接打标记。
• 操作的区间未完全包含节点表示的区间时，从节点的中点处分开向下递归。
• 每次操作结点前必须 pushdown，修改操作完后需要 pushup。

复杂度：建树 O(n\log n)，单次操作 O(\log n)，其中 n 是叶子数。前两者均需要乘区间合并的复杂度。

:::success[代码（P3372）]

struct node{
    int ls,rs;
    ll s,tag;
};
node t[200010];
ll n,q,a[100010],op,u,v,w,p=2;
void build(ll now,ll l,ll r){
    if(l==r){
        t[now].s=a[l];
        return ;
    }
    ll mid=(l+r>>1);
    t[now].ls=(p++);
    build(t[now].ls,l,mid);
    t[now].rs=(p++);
    build(t[now].rs,mid+1,r);
    t[now].s=t[t[now].ls].s+t[t[now].rs].s;
}
void pushdown(ll now,ll l,ll r){
    ll mid=(l+r>>1);
    t[t[now].ls].s+=t[now].tag*(mid-l+1);
    t[t[now].ls].tag+=t[now].tag;
    t[t[now].rs].s+=t[now].tag*(r-mid);
    t[t[now].rs].tag+=t[now].tag;
    t[now].tag=0;
}
void upd(ll now,ll l,ll r,ll L,ll R,ll c){
    pushdown(now,l,r);
    if(l>=L&&r<=R){
        t[now].tag+=c;
        t[now].s+=(r-l+1)*c;
        return ;
    }
    ll mid=(l+r>>1);
    if(L<=mid){
        upd(t[now].ls,l,mid,L,R,c);
    } 
    if(R>mid){
        upd(t[now].rs,mid+1,r,L,R,c);
    }
    t[now].s=t[t[now].ls].s+t[t[now].rs].s;
}
ll query(ll now,ll l,ll r,ll L,ll R){
    pushdown(now,l,r);
    if(l>=L&&r<=R){
        return t[now].s;
    }
    ll mid=(l+r>>1),ans=0;
    if(L<=mid){
        ans+=query(t[now].ls,l,mid,L,R);
    } 
    if(R>mid){
        ans+=query(t[now].rs,mid+1,r,L,R);
    }
    return ans;
}

:::

例题：

• 扫描线：
  • P1502 窗口的星星
  • P1856 [IOI 1998 / USACO5.5] 矩形周长 Picture
  • P5490 【模板】扫描线 & 矩形面积并
• 线段树上二分：U502676 线段树上二分模版
• 复杂信息维护：
  • P9530 [JOIST 2022] 鱼 2 / Fish 2
  • CF1004F Sonya and Bitwise OR
  • CF1990F Polygonal Segments
• 区间历史和：P8868 [NOIP2022] 比赛
• 权值线段树：P3369 【模板】普通平衡树

单调数据结构

单调队列

问题（例）：求序列上所有长度为 k 的子区间的最值。

算法流程：

• 使用双端队列维护信息。
• 每次加入值前，从前端将所求区间外的信息弹出，从后端将不贡献的（题中就是比要加入的值大/小的）值弹出。

复杂度：O(n)。

:::success[代码（P1886）] deque 非常慢。考场上不要用。

deque<ll> q;
ll n,k,a[1000010];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        while(q.size()&&i-q.front()+1>k){
            q.pop_front();
        }
        while(q.size()&&a[q.back()]>a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<' ';
        }
    }
    cout<<endl;
    q.clear();
    for(int i=0;i<n;i++){
        while(q.size()&&i-q.front()+1>k){
            q.pop_front();
        }
        while(q.size()&&a[q.back()]<a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<' ';
        }
    }
    return 0;
}

:::

单调栈

问题（例）：求序列上每个元素后第一个比它大的元素。

算法流程：

• 使用栈维护信息。
• 每次加入值前，将不贡献的（题中就是比要加入的值大/小的）值弹出。

复杂度：O(n)。

:::success[代码（P5788）] stack 非常慢。考场上不要用。

ll n,a[3000010],ans[3000010];
stack<ll> st;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i;i--){
        while(st.size()&&a[st.top()]<=a[i]){
            st.pop();
        }
        if(st.size()){
            ans[i]=st.top();
        }
        st.push(i);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' '; 
    }
    return 0;
}

:::

例题：

• AT_abc420_f [ABC420F] kirinuki

Treap

问题：维护平衡的二叉搜索树。

算法流程：

• 通过随机赋权值来保证树高是期望 \log 的。建议别用 rand()。
• 书写的要点是插入和删除部分。
  • 插入的过程是按大小关系不断跳直到叶子或对应点，然后进行插入：
  • 如果有对应点则直接次数加一；
  • 如果没有对应点则在当前的叶子下面开新点，然后向上旋转直至按随机的权值这棵树符合堆性质。
  • 删除的过程是按大小关系不断跳直到对应点，然后进行删除，
  • 如果该位置出现多次则直接次数减一；
  • 否则将该位置向下旋转直至变为叶子后删去。
  • 旋转的方法看图说话就行。
• 其余部分就是根据 BST 的性质回答询问即可。

图论

图论部分的理解记忆同样重要，不过此外需要注意一些常犯错的小细节。

树的直径

问题：给定一棵无边权树，求其最长的简单路径。

算法流程：

• 性质：两棵树合并时，新树的直径是在原来两棵树的直径的两端点中的两个点的路径。即新树的直径是原来两棵树的直径之一，或者是从原来一棵树的直径的一端到另一棵树的直径的一端。
• 于是直接 DFS 即可，每次将儿子合并进来时先考虑两棵树各取一端点的情况，此时如果还能用要合并的儿子更新再用要合并的儿子进行更新。如需输出直径，额外记录是哪个儿子即可。

复杂度：O(n)。

注意点：

• 看清楚路径长度是点数还是边数，这影响到下面代码中 dfs 函数第二行 len 数组的初始值。

:::success[代码（B4016）]

ll n,u,v,dep[100010],l[100010],r[100010],len[100010];
vector<ll> a[100010];
void dfs(ll now,ll lst){
    dep[now]=dep[lst]+1;
    l[now]=now;r[now]=now;len[now]=0;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst){
            dfs(a[now][i],now);
            if(len[now]<max(dep[l[now]],dep[r[now]])+max(dep[l[a[now][i]]],dep[r[a[now][i]]])-(dep[now]<<1)){
                if(dep[l[now]]<dep[r[now]]){
                    swap(l[now],r[now]);
                }
                if(dep[l[a[now][i]]]<dep[r[a[now][i]]]){
                    r[now]=r[a[now][i]];
                }
                else{
                    r[now]=l[a[now][i]];
                }
                len[now]=dep[l[now]]+dep[r[now]]-(dep[now]<<1);
            }
            if(len[now]<len[a[now][i]]){
                l[now]=l[a[now][i]];
                r[now]=r[a[now][i]];
                len[now]=len[a[now][i]];
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,1);
    cout<<len[1];
    return 0;
}

:::

例题：

• CF2134D Sliding Tree。

倍增 LCA

问题：给定两个点，求这两个点深度最大的公共祖先。

算法流程：

• 一遍 DFS 求出深度（如果是保证 p_i<i 的父亲表示法不需要 DFS）和每个点的父亲。
• 外层枚举 i，内层枚举每个点，求出各点的第 2^i 级祖先。
• 询问时先将深度较低的点向上跳直至其与另一点深度相同，然后再在两点不相同的前提下尽量往上跳，最终跳到的点的父亲即为答案。向上跳时从大到小枚举 i 并检查跳 2^i 层是否满足条件。

复杂度：O(n\log n)-O(\log n)。

注意点：

• 注意数组第二维大小。
• 注意特判询问的一个点是另一个的祖先的情况，此时显然不应该输出它们的父亲而应该输出其本身。
• 注意求 fa 数组时层数是在外层枚举的。

:::success[代码（P3379）] 需要快读快写才能通过，此时单点用时不超过 1.2 秒。

ll n,q,u,v,rt,fa[500010][30],dep[500010];
vector<ll> a[500010];
void dfs(ll now,ll lst){
    fa[now][0]=lst;
    dep[now]=dep[lst]+1;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst){
            dfs(a[now][i],now);
        }
    }
}
ll lca(ll x,ll y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    for(int i=19;~i;i--){
        if(dep[fa[x][i]]>=dep[y]){
            x=fa[x][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=19;~i;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int main(){
    cin>>n>>q>>rt;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(rt,rt);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    }
    while(q--){
        cin>>u>>v;
        cout<<lca(u,v)<<endl;
    }
    return 0;
}

:::

拓扑排序

问题：给定一个 DAG，将结点排序使得所有边的终点都在起点后面。

算法流程：

• 从所有入度为 0 的点开始多源 BFS，遍历一个点时删掉这个点的所有出边并检查这些边是否是其另一端的最后一条入边（可以通过维护度数实现），如果是则将另一端的点加入队列。这样遍历点的顺序就是拓扑序。

复杂度：O(n)。

:::success[代码（B3644）]

ll n,u,deg[110];
vector<ll> a[110];
queue<ll> q;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>u;
        while(u){
            a[i].push_back(u);
            deg[u]++;
            cin>>u;
        }
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            q.push(i);
        }
    }
    while(q.size()){
        ll now=q.front();
        q.pop();
        cout<<now<<' ';
        for(int i=0;i<a[now].size();i++){
            deg[a[now][i]]--;
            if(!deg[a[now][i]]){
                q.push(a[now][i]);
            }
        }
    }
    return 0;
}

:::

例题：

• P7113 [NOIP2020] 排水系统
• P7077 [CSP-S 2020] 函数调用

最短路

单源最短路：Dijkstra

问题：在边权非负的有向图上求从一个起点出发到其他点的最短路。

算法流程：

• 就是用优先队列进行 BFS，同时维护一下距离以更新。

复杂度：O(m\log n)。

注意点：

• 即使没有负环，只要图上带有负边权，就不能使用 Dijkstra 算法。
• 记得给 dis 数组赋初值。
• vis 打标记的位置别搞错了。

:::success[代码（P3371/P4779）] 看上去在状态里面维护一遍 dis 是冗余的，实则是 C++ 不允许给两个非自定义的类型重载运算符。

struct node{
    ll now,dis;
};
bool operator <(node x,node y){
    return x.dis>y.dis;
}
ll n,m,s,u,v,w,dis[100010],vis[100010];
vector<ll> a[100010],b[100010];
priority_queue<node> q;
void dij(){
    fill(dis+1,dis+n+1,1ll<<62);
    dis[s]=0;
    q.push({s,0});
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        if(vis[tmp.now])continue;
        vis[tmp.now]=1;
        for(int i=0;i<a[tmp.now].size();i++){
            if(!vis[a[tmp.now][i]]&&tmp.dis+b[tmp.now][i]<dis[a[tmp.now][i]]){
                dis[a[tmp.now][i]]=tmp.dis+b[tmp.now][i];
                q.push({a[tmp.now][i],tmp.dis+b[tmp.now][i]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        a[u].push_back(v);
        b[u].push_back(w);
    }
    dij();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

:::

单源最短路：SPFA

问题：在有负边权的有向图上求从一个起点出发到其他点的最短路，或者判断图中是否有负环。

算法流程：

• 类似于 Djikstra，不过使用队列维护边。枚举边时只有不在队列内且 dis 被更新的边才进入队列。
• 如需判负环，则额外维护每个点进入队列的次数，如果达到 n 次则说明出现负环。

复杂度：O(nm)。

注意点：

• 如果条件允许使用 Dijkstra 算法，就不要使用 SPFA 算法。
• 检查题目需不需要判负环。

:::success[代码（P3371）] inq 数组表示当前点是否在队列内，cnt 数组记录当前点进队的次数。

queue<ll> q;
void spfa(){
    fill(dis+1,dis+n+1,(1ll<<31)-1);
    dis[s]=0;
    cnt[s]=1;
    inq[s]=1;
    q.push(s);
    while(!q.empty()){
        ll now=q.front();
        q.pop();
        inq[now]=0;
        for(int i=0;i<a[now].size();i++){
            if(dis[now]+b[now][i]<dis[a[now][i]]){
                dis[a[now][i]]=dis[now]+b[now][i];
                if(!inq[a[now][i]]){
                    q.push(a[now][i]);
                    inq[a[now][i]]=1;
                    cnt[a[now][i]]++;
                    if(cnt[a[now][i]]>=n){
            //判负环，板题中不需要
                        cout<<"orz"<<endl;
                        return ;
                    }
                }
            }
        }
    }
}

:::

全源最短路：Floyd

问题：求一个有向带边权图中任两点间的最短路。

算法流程：

• 类似区间 DP。
• 初始值有边的赋成对应的边权，没边的赋成 +inf。
• DP 时外层枚举中转点，内层枚举所有点对，直接转移即可。

复杂度：O(n^3)。

注意点：

• 记得初始化。初值要够大。
• 读入时记得判重边。
• 记得区分有向图无向图。
• Floyd 可以判负环，只要看 dis[i][i] 是否等于 0 即可。

:::success[代码]

ll n,m,u,v,w,dp[110][110];
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        dp[u][v]=min(dp[u][v],w);
        dp[v][u]=min(dp[v][u],w);
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dp[j][k]=min(dp[j][i]+dp[i][k],dp[j][k]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<dp[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

:::

最小生成树

Prim 算法

问题：求一个无向图边权和最小的生成树。

算法流程：

• 用小根堆维护所有边，从 1 号点开始将所有出边加入堆中，每次取出堆顶元素检查该边的另一端是否已经在树中，如果不在则将其加入树中，并将其所有出边加入堆中。

复杂度：O(m\log m)。

:::success[代码（P3366）]

struct node{
    ll v,w;
};
bool operator <(node x,node y){
    return x.w>y.w;
}
ll n,m,u,v,w,vis[5010];
vector<ll> a[5010],b[5010];
priority_queue<node> q;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        a[u].push_back(v);
        b[u].push_back(w);
        a[v].push_back(u);
        b[v].push_back(w);
    }
    ll cnt=0,ans=0;
    vis[1]=1;
    for(int i=0;i<a[1].size();i++){
        q.push({a[1][i],b[1][i]});
    }
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        if(vis[tmp.v])continue;
        vis[tmp.v]=1;
        ans+=tmp.w;
        cnt++;
        if(cnt==n-1)break;
        for(int i=0;i<a[tmp.v].size();i++){
            if(!vis[a[tmp.v][i]]){
                q.push({a[tmp.v][i],b[tmp.v][i]});
            }
        }
    }
    if(cnt==n-1){
        cout<<ans;
    }
    else{
        cout<<"orz";
    }
    return 0;
}

:::

Kruskal 算法

问题：求一个无向图边权和最小的生成树。

算法流程：

• 按边权从小到大枚举每条边，如果该边两端点不在同一并查集中，则选取该边并将两端点所在并查集合并。

算法流程（并查集）：

• 合并时将其中一个点所在集合的树根的父亲设置为另一个点所在集合的树根。
• 查找时暴力跳父亲。
• 按秩合并：维护并查集大小，合并时将小的合并到大的上。
• 路径压缩：查找时将自己的父亲设置为父亲的父亲。

复杂度：O(m\log n) 或 O(m\alpha(n))，视并查集实现而定。

:::success[代码（P3366）] 这里并查集只进行了路径压缩。

struct node{
    ll u,v,w;
};
bool operator <(node x,node y){
    return x.w<y.w;
}
ll n,m,cnt,fa[200010];
node a[200010];
ll fnd(ll x){
    if(fa[x]!=x)fa[x]=fnd(fa[x]);
    return fa[x];
}
void merg(ll x,ll y){
    fa[fnd(x)]=fa[y];
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    sort(a,a+m);
    ll cnt=0,ans=0;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=0;i<m;i++){
        if(fnd(a[i].u)!=fnd(a[i].v)){
            merg(a[i].u,a[i].v);
            ans+=a[i].w;
            cnt++;
            if(cnt==n-1){
                break;
            }
        }
    }
    if(cnt==n-1){
        cout<<ans;
    }
    else{
        cout<<"orz";
    }
    return 0;
}

:::

例题（最小生成树）：

• P14362 [CSP-S 2025] 道路修复（注：此题直接外层暴力内层套个板子就可以跑进 1.2 秒，练手的话不需要写正解）

例题（Kruskal）：

• 山大校赛 2024 G 路径查询（密码：yesterdayis1207）
• CF2164E Journey

连通性问题（Tarjan 算法）

无向图·割边、边双

问题：求无向图中的各割边。

算法流程：

• 设 dfn_x 为 x 的 DFS 序，low_x 表示从 x 子树内点出发走一条边能到的 dfn 最小的点。
• 进行 DFS，
  • 计算各点的 dfn 及 low 的值。low_u 初始为 dfn_u；对于树边，先对儿子 v 进行 DFS，然后用 low_v 更新 low_u；对于非树边，用 dfn_v 更新 low_u；最终 low_u 取各值中最小的。
  • 如果是树边，则标记其是否是割边。边 (x,y) 是割边的条件是搜索树上 y 是 x 的儿子且 dfn_x<low_y。
• 再次 DFS，找出所有连通分量。

复杂度：O(m)。

注意点：

• 注意判断重边，具体方法是给边进行编号，并在第一次 DFS 时采用编号（而不是终点）判断判断一条边是否是来时的边。
• 无向图缩点后变为树。

:::success[代码（P8436）] 这里只给出了第一次 DFS 的代码；一条边的 is 数组被标记为 1 表示其为割边，另外因为需要再一次 DFS 求具体的边双，故再将非割边树边标记为 2，方便进行第二次 DFS。

void tarjan(ll now,ll lst,ll lstedge){
    fa[now]=lst;
    dfn[now]=++p;
    low[now]=dfn[now];
    vis[now]=1;
    ll mx=0;
    for(int i=0;i<a[now].size();i++){
        if(!dfn[a[now][i]]){
            tarjan(a[now][i],now,id[now][i]);
            low[now]=min(low[now],low[a[now][i]]);
            is[id[now][i]]=2;
            if(dfn[now]<low[a[now][i]]){
                is[id[now][i]]=1;
            }
        }
        else if(id[now][i]!=lstedge){
            low[now]=min(low[now],dfn[a[now][i]]);
        }
    }
}

:::

无向图·割点、点双

问题：求无向图中的各割点。

算法流程：

• 类似于边双，但判别点 u 是割点的条件是该点于树上存在至少一个儿子 v 使得 dfn_u\mathbf{\le}low_v，如果 u 是根节点则要求存在至少两个这样的儿子。

复杂度：O(n)。

注意点：

• 注意一个点可能被包含在多个点双内。

:::success[代码（P3388/P8435）] 在 P8435 中为了准确找到各点双，我们还需要额外记录各边是否在点双内，所以仍然保留了 P8436 中的 is 数组，并额外增加 isp 数组记录各点是否为割点。

void tarjan(ll now,ll lst,ll lstedge){
    ll cnt=0;
    fa[now]=lst;
    dfn[now]=++p;
    low[now]=dfn[now];
    vis[now]=1;
    ll mx=0;
    for(int i=0;i<a[now].size();i++){
        if(!dfn[a[now][i]]){
            tarjan(a[now][i],now,id[now][i]);
            low[now]=min(low[now],low[a[now][i]]);
            is[id[now][i]]=1;
            if(dfn[now]<=low[a[now][i]]){
                is[id[now][i]]=2;
                cnt++;
            }
        }
        else if(id[now][i]!=lstedge){
            low[now]=min(low[now],dfn[a[now][i]]);
        }
    }
    if(lstedge==-1){
        isp[now]=(cnt>=2);
    }
    else isp[now]=(cnt>=1);
}

:::

有向图·缩点（强连通分量，SCC）

问题：给定一张有向图，找出其所有的强连通分量。

算法流程：

• 判定是 dfn_i=low_i 时出现一个点双。更新 low 时需要判断边的另一端点是否已经入栈，因为有向图可能出现前向边。
• 用栈维护所有搜过的点，如果遍历完当前点的出边后发现其符合上述判定，则将栈内点不断弹出至该点被弹出，这个过程中弹出的所有点构成一个 SCC。

复杂度：O(n)。

注意点：

• 有向图缩点后变为 DAG，且上述算法得到的各 SCC 自动满足逆拓扑序。
• 看清楚图的连通性（不保证？弱连通？保证存在能到达其他所有点的点？）。

:::success[代码（P3387）] 题里有一个拓扑排序的部分。

ll n,m,u,v,dfn[10010],low[10010],ins[10010],bel[10010],p,pos,deg[10010],dp[10010],sz[10010],w[10010];
//ins 是否在栈中，bel 属于哪个 scc，sz 存 scc 大小，deg 和 dp 用于拓扑排序 
vector<ll> aa[10010],a[10010];
//aa 存原图，a 存新图
stack<ll> st;
queue<ll> q;
void dfs(ll now,ll lst){
    dfn[now]=(++pos);
    low[now]=pos;
    st.push(now);
    ins[now]=1;
    for(int i=0;i<aa[now].size();i++){
        if(!dfn[aa[now][i]]){
            dfs(aa[now][i],now);
            low[now]=min(low[now],low[aa[now][i]]);
        }
        else if(ins[aa[now][i]]){
            low[now]=min(low[now],dfn[aa[now][i]]);
        }
    }
    if(low[now]==dfn[now]){
        while(st.top()!=now){
            sz[p]+=w[st.top()];
            ins[st.top()]=0;
            bel[st.top()]=p;
            st.pop();
        } 
        sz[p]+=w[st.top()];
        ins[st.top()]=0;
        bel[st.top()]=(p++);
        st.pop();
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(int i=0;i<m;i++){
        cin>>u>>v;
        aa[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            dfs(i,i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<aa[i].size();j++){
            if(bel[i]==bel[aa[i][j]]){
                continue;
            }
            a[bel[i]].push_back(bel[aa[i][j]]);
            deg[bel[aa[i][j]]]++;
        }
    }
    for(int i=0;i<p;i++){
        if(!deg[i]){
            q.push(i);
            dp[i]=sz[i];
        }
    }
    ll ans=0;
    while(q.size()){
        ll now=q.front();
        q.pop();
        ans=max(ans,dp[now]);
        for(int i=0;i<a[now].size();i++){
            dp[a[now][i]]=max(dp[a[now][i]],dp[now]+sz[a[now][i]]);
            deg[a[now][i]]--;
            if(!deg[a[now][i]]){
                q.push(a[now][i]);
            }
        }
    }
    cout<<ans;
    return 0;
}

:::

字符串

2025 版大纲中，联赛范围内需要背模板的字符串算法只有 KMP 和马拉车（显然哈希是不用背的）。这两种算法的代码都不长，但都比较难以理解，所以一定确保背诵的准确性。

为了防止被某个审核打回，特此声明：以下记 s[i,j] 表示 \overline{s_i,s_{i+1},\dots,s_j}。

哈希

问题：判断两个集合或序列是否相等。

本身显然没啥可背的，不过可以背几个大模数。当然考场上花三分钟从 10^9 开始枚举跑素数判断也可以。

模板题：

• 集合哈希：P8819 [CSP-S 2022] 星战
• 进制哈希：P3370 【模板】字符串哈希

KMP 算法

问题：给定待匹配的字符串 s 和模式串 t，求 s 中与 t 相等的子串的个数。

算法流程：

• 预处理 fail_i 表示 t[0,i-1] 的最长公共前后缀的长度（即最大的 j 使得 t[0,j-1]=t[i-j+1,i]，没有为 0）（减一是为了方便后面跳）。考虑已知 fail[1,i]，求 fail_{i+1}，
  • 如果 t_{fail{i}}=t_i，则 fail_{i+1}=i。
  • 否则不断跳 fail 直至 p=0 或者 t_p=t_i，这里 p 是最终跳到的位置。
  • 若 t_p=t_i，则 fail_{i+1}=p+1；
  • 否则 fail_{i+1}=0。
  • 由于上述 fail 是 1-index，输出 fail 数组时输出的仍是 fail[1,|s|]。
• 枚举 s 的每一项，设当前 t 上的指针在 t_p 处，
  • 若 s_i\neq t_p 则跳 fail 直至 s_i=t_p 或者 p=0。
  • 如果 s_i=t_p，则 p 移至 p+1，否则不动。
  • 判断是否匹配成功，如果 p=|t| 则记录位置并跳一次 fail。

复杂度：O(|s|+|t|)。

:::success[代码（P3375）]

string s,t;
ll fail[1000010];
int main(){
    ios::sync_with_stdio(0);
    cin>>s>>t;
    ll p;
    for(int i=1;i<t.length();i++){
        p=fail[i];
        while(p&&t[p]!=t[i]){
            p=fail[p];
        }
        if(t[p]==t[i])fail[i+1]=p+1;
        else fail[i+1]=0;
    }
    p=0;
    for(int i=0;i<s.length();i++){
        while(p&&s[i]!=t[p]){
            p=fail[p];
        }
        if(s[i]==t[p]){
            p++;
        }
        if(p==t.length()){
            cout<<i+2-t.length()<<endl;
            p=fail[p];
        }
    }
    for(int i=1;i<=t.length();i++){
        cout<<fail[i]<<' ';
    }
    return 0;
}

:::

Manacher / 马拉车算法

问题：给定字符串 s，求以 s 中每个位置为中心的最长回文串长。

算法流程：

• 向原串头尾加入不同的特殊字符，并在原串的每两个字符之间加入相同特殊字符。
• 维护当前最长的回文串的右端点 mx 及其中心 mxi。
• 枚举到 s_i 时，
  • 如果 i<mx，则 i 处初始的右端点取以关于 mxi 对称位置为中心的 len 和 i 的较小值，对应算出 i 处初始的答案 len_i=\min\{mx-i,len_{2mx-i}\}。
  • 否则 len_i 初始取 1。
• 然后从初始位置起暴力扩展直至无法继续扩展。
• 答案取所有 len_i 的最大值减 1（因为最外侧是匹配失败的）。

复杂度：O(|s|)。

:::success[代码（P3805）] 注意空间开两倍。

ll len[220000010],mx,mxi;
string tmp,s;
int main(){
    ios::sync_with_stdio(0);
    cin>>tmp;
    s='*';
    for(int i=0;i<tmp.length();i++){
        s+='$';
        s+=tmp[i];
    }
    s+='$';
    s+='#';
    for(int i=1;i<s.length()-1;i++){
        if(mx>i){
            len[i]=min(mx-i,len[(mxi<<1)-i]);
        }
        else{
            len[i]=1;
        }
        while(s[i+len[i]]==s[i-len[i]]){
            len[i]++;
        }
        if(i+len[i]>mx){
            mx=i+len[i];
            mxi=i;
        }
    }
    ll ans=0;
    for(int i=0;i<s.length();i++){
        ans=max(ans,len[i]);
    }
    cout<<ans-1;
    return 0;
}

:::

DP

联赛 DP 没有真正需要死记硬背的模板，重点在熟悉并理解各个基本模型的转移思路。

树形 DP 和 DAG 上 DP 已经在图论一节（分别是“树的直径”和“强连通分量”部分）提过了，这里不再浪费篇幅。树形 DP 额外提供一个简单的例题 P14150 不动鸣神，恒常乐土这题跟我没关系哈要攻击攻击出题人去。

背包

01 背包

问题：若干个物品，每个物品有价值和代价，在代价不超过限制的前提下选取价值和最大的物品集合。每个物品只允许选择最多一次。

思路：

• 枚举物品和时间，判断当前时间是否能选该物品，如果能则尝试用选取该物品的答案更新当前答案。

方程：

其中 c_i 是物品的代价，w_i 是物品的价值。dp_{i,j} 初值为 0。

复杂度：O(nt)，其中 n 是物品数量，t 是时间。

:::success[代码（P1048）]

for(int i=1;i<=n;i++){
  for(int j=0;j<=t;j++){
    dp[i&1][j]=dp[i-1&1][j];
    if(j>=c[i]){
      dp[i&1][j]=max(dp[i&1][j],dp[i-1&1][j-c[i]]+w[i]);
    }
  }
}
ll ans=0;
for(int i=0;i<=t;i++){
  ans=max(ans,dp[n&1][i]);
}

:::

完全背包

问题：若干个物品，每个物品有价值和代价，在代价不超过限制的前提下选取价值和最大的物品集合。每个物品允许选择任意多次。

思路：

• 暴力转移是枚举出现次数，但实际上可以通过复用 j 较小时的已求出的信息来实现 O(1) 转移。

方程：

其中 c_i 是物品的代价，w_i 是物品的价值。dp_{i,j} 初值为 0。

复杂度：O(nt)，其中 n 是物品数量，t 是时间。

注意点：

• 为了确保转移到 dp_{i,j} 时第二维小于 j 的部分已经处理完成，应该正序枚举时间。

:::success[代码（P1616）]

for(int i=1;i<=n;i++){
  for(int j=0;j<=t;j++){
    dp[i&1][j]=dp[i-1&1][j];
    if(j>=c[i]){
      dp[i&1][j]=max(dp[i&1][j],dp[i&1][j-c[i]]+w[i]);
    }
  }
}
ll ans=0;
for(int i=0;i<=t;i++){
  ans=max(ans,dp[n&1][i]);
}

:::

多重背包与二进制分组

问题：若干个物品，每个物品有价值和代价，在代价不超过限制的前提下选取价值和最大的物品集合。每个物品选择次数有一个上限。

思路：

• 将物品个数拆成前若干个 2 的整数次幂相加的形式，例如 30=1+2+4+8+14，就能实现凑出所有可能的情况，然后跑 01 背包即可。

方程与 01 背包完全一致。

复杂度：O(nt\log V)，其中 n 是物品数量，t 是时间，V 是单个物品的最大出现次数。

广为流传的二进制分组题是要使用 AC 自动机的 CF710F，笔者反而没找到二进制分组优化背包的题，所以有空的时候我再把多重背包的题造出来吧（如果有了评论区撅我）。

区间 DP

问题：通常用于子串合并类问题，也存在类似于 P9119 这样每次只向一侧添加一个数的问题。下面以更常见的前一类为例。

思路：

• 最外层枚举区间长度，然后枚举左端点，最后枚举断点更新答案。

状态数：O(n^3)，转移不为 O(1) 则需要乘转移复杂度。

注意点：

• 注意枚举顺序，确保后枚举到的区间所需信息先被枚举到。

:::success[代码（P1880）] 本题是环上的，记得空间开两倍。

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
        f[i][i]=0;
        f[i+n][i+n]=0;
        g[i][i]=0;
        g[i+n][i+n]=0;
    }
    for(int i=1;i<=(n<<1);i++){
        qzh[i]=qzh[i-1]+a[i];
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=(n<<1)-i;j++){
            for(int k=j;k<j+i;k++){
                f[j][j+i]=min(f[j][j+i],f[j][k]+f[k+1][j+i]+qzh[j+i]-qzh[j-1]);
                g[j][j+i]=max(g[j][j+i],g[j][k]+g[k+1][j+i]+qzh[j+i]-qzh[j-1]);
            }
        }
    }
    ll mn=999999999999999999ll,mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,g[i][i+n-1]);
        mn=min(mn,f[i][i+n-1]);
    }
    cout<<mn<<endl<<mx;
    return 0;
}

:::

例题：

• P1775 石子合并（弱化版）
• P7914 [CSP-S 2021] 括号序列
• P9119 [春季测试 2023] 圣诞树

数位 DP

问题：通常是求一定范围内数位上满足一定条件的数有多少，或者一定范围内第 k 个满足条件的数是多少。

思路：

• 将需要维护的信息设到状态上。
• 对数字的范围有要求时，通常需要记录当前位以前是否都在边界上，如果是则当前位需要考虑边界问题。
• 如果问题是求第 k 个数，则可以在外面套一层二分答案来解决。

复杂度视实现。

注意点：

• 通常采用记忆化搜索的方式来编写数位 DP，因为比较好写。但不一定非要这样，例如 P7961 大家普遍采用的还是传统写法。

:::success[代码（P10958）]

ll T,n,now[20],dp[20][4][2];
ll dfs(ll dep,ll cnt,bool flg,bool lim){
    if(dep<0)return flg;
    if(!lim&&dp[dep][cnt][flg]!=-1){
        //这里记得判，记忆化中只记有答案的情况 
        return dp[dep][cnt][flg];
    }
    ll ans=0;
    for(int i=0;i<=(lim?now[dep]:9);i++){
        ans+=dfs(dep-1,((cnt<<1)&3)+(i==6),flg||cnt==3&&i==6,lim&&i==now[dep]);
    }
    if(!lim){
        dp[dep][cnt][flg]=ans;
    } 
    return ans;
}
bool check(ll mid){
    ll mxd=0,tmp=mid;
    while(tmp){
        now[mxd++]=tmp%10;
        tmp/=10;
    }
    return dfs(mxd-1,0,0,1)>=n;
}
int main(){
    memset(dp,-1,sizeof(dp));
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n;
        ll l=665,r=99999999666ll;
        while(l<=r){
            ll mid=(l+r>>1);
            if(check(mid)){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        cout<<l<<endl;
    }
    return 0;
}

:::

例题：

• P7961 [NOIP2021] 数列
• P10959 月之谜

状压 DP

问题：需要在 DP 下标里维护状态的问题。最明显的特征是存在某一个数的范围极小。

思路：

• 将状态压成进制串（通常是二进制，方便位运算判断状态合法性）并枚举状态进行转移。
  • 例如 P1896 中通过将其左移一位和右移一位的值取或后再与原串取与来确定行内是否互相影响，将上一行及其左移一位、右移一位的值取或后与当前行取与来确定当前行与上一行是否影响。

:::success[代码（P1896）]

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<(1<<n);i++){
        if(!(((i<<1)|(i>>1))&i)){
            cnt[p]=popcount(i);
            dp[0][cnt[p]][p]=1;
            s[p++]=i;
        }
    } 
    for(int i=1;i<n;i++){
        for(int j=0;j<p;j++){
            for(int k=0;k<p;k++){
                if(((s[k]<<1)|(s[k]>>1)|s[k])&s[j]){
                    continue;
                }
                for(int l=cnt[k];l<=m;l++){
                    dp[i][l+cnt[j]][j]+=dp[i-1][l][k];
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<p;i++){
        ans+=dp[n-1][m][i];
    } 
    cout<<ans;
    return 0;
}

:::

例题：

• P2704 [NOI2001] 炮兵阵地
• P11856 [CSP-J 2022 山东] 吟诗（笑点解析：《CSP-J》）

分步 DP

没有找到我之前做的板子，这里先简单说一下吧。

就是例如给定一个无向图，上面有三个标记，每个单位时间内每个标记可以移动至多一条边，且每单位时间后三个标记两两间距离不能超过 d。求将所有标记移到终点 t 的路径长度最小和。