提高组热身赛小计(非题目顺序)

· · 个人记录

T1商务旅行

题意

给定一棵 N 个结点的树，所有边的权值均为 1。从结点 1 出发，依次经过 M 个指定结点，求路径总长度的最小值。

思路

代码首先通过深度优先搜索（DFS）预处理出每个城镇的深度以及祖先信息（用于快速计算最近公共祖先），然后利用最近公共祖先（LCA）算法计算商人按给定顺序经过各个城镇时的最短路径总时间。
计算过程中，每两个连续城镇之间的最短路径长度通过它们的深度与它们 LCA 的深度计算得出（公式为：d[x] + d[y] - 2 * d[LCA(x,y)]），最后将所有连续城镇间的路径长度累加，得到总的旅行时间。
这一实现适用于城镇以树结构连接的场景（无环，任意两城镇间有唯一路径），能高效处理较大规模的输入数据（城镇数达 3×10⁴，经过的城镇数达 3×10⁵）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=30005;
int h[N],fa[N][25];
vector<int>G[N];
void dfs(int x,int f) {
    h[x]=h[f]+1;
    fa[x][0]=f;
    for(int i=1; i<=20; ++i){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int y:G[x]) {
        if(y!=f)dfs(y,x);
    }
}
int LCA(int x,int y) {//倍增 
    if(x==y)return x;
    if(h[x]>h[y])swap(x,y);
    for(int i=20; i>=0; --i) {
        if(h[fa[y][i]]>=h[x]) {
            y=fa[y][i];
        }
    }
    if(x==y)return x;
    for(int i=20; i>=0; --i)
        if(fa[x][i]!=fa[y][i]) {
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<n; ++i) {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    int m;
    cin>>m;
    long long res=0;
    int rs;
    cin>>rs;
    for(int i=1; i<m; ++i) {
        int mw;
        cin>>mw;
        int ac=LCA(rs,mw);
        res+=h[rs]+h[mw]-2*h[ac];
        rs=mw;
    }
    cout<<res<<"\n";
    return 0;
}

T2无线传输

题意

给你一个字符串s1，它是由某个字符串s2不断自我连接形成的（保证至少重复 2 次）。但是字符串s2是不确定的，现在只想知道它的最短长度是多少。

思路

||经典的KMP算法q(≧▽≦q）推导发现：
设循环节的长度为x，那么kmp数组前x个都是0，后面kmp[x+n]=n 先求出kmp数组 答案实际就是len-kmp[len]

代码copy

#include <bits/stdc++.h>
#define N 1000111
using namespace std;
string a;
int k[N];
int main() {
    int n;
    cin>>n>>a;
    k[0]=0;
    k[1]=0;
    for(int i=1,ks=0;i<n;++i) {
        while(ks!=0&&a[i]!=a[ks]) {
            ks=k[ks];
        }
        if(a[i]==a[ks]) k[i+1]=++ks;
        else k[i+1]=0;
    }
    cout<<n-k[n];
    return 0;
}

T3鬼子进村

题意（李云龙）

给定一些操作，查找，删除，与重建，查找时求连通块长度

思路

数据结构：

数组 b[] 标记房子是否被摧毁（1 表示摧毁，0 表示正常）
栈 s[] 记录被摧毁房子的顺序（用于恢复操作）
变量 t 作为栈顶指针

核心逻辑：