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 作為棧頂指針

核心邏輯：

• 對于 D x 操作：標記 x 號房子為摧毀狀態，并將 x 入棧
• 對于 R 操作：從棧中取出最后一個被摧毀的房子，恢復其正常狀態
• 對于 Q x 操作：
  1. 尋找 x 左邊最近的被摧毀房子（記為 l）
  2.尋找 x 右邊最近的被摧毀房子（記為 r）
  若 x 本身被摧毀（此時 l 和 r 可能相等），則輸出 0
  否則，能到達的房子數量為 r - l - 1（即左右兩個摧毀點之間的所有房子）

優勢：

利用棧維護摧毀順序，使得恢復操作（R）可以高效執行
通過遍歷棧中元素來查找左右邊界，思路直觀
時間復雜度主要取決于查詢操作中遍歷棧的次數，在實際場景中基本能滿足需求

• 例如樣例中查詢 4 號房子時：
  左邊最近的摧毀點是 3，右邊最近的摧毀點是 5
  因此能到達的房子是 4，共 1 個（對應第一次查詢輸出 1）

代碼

#include<bits/stdc++.h>
#define N 500050
using namespace std;
int n,m;
int t,s[N];
bool b[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		char op;
		cin>>op;
		if(op=='R') {
			b[s[t--]]=0;
			continue;
		}
		int a;
		cin>>a;
		if(op=='D') {
			b[a]=1;
			s[++t]=a;
		}
		if(op=='Q'){//二分求聯通
			int l=0,r=n+1;
			for(int i=1; i<=t; i++) {
				if(s[i]<=a) l=max(s[i],l);
				if(s[i]>=a) r=min(s[i],r);
			}
			if(l==r) cout<<0<<'\n';
			else cout<<r-l-1<<'\n';
		}
	}
}