22.9.3 总结

A

求字符串插入多少字符后可以变为回文串。
将字符串翻转后与原字符串求最长公共子串。
\(ans=\min(i+j-2*f_{i,j}).(i+j=n-(n\mod 2))\)

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2010;
char s1[N],s2[N];
int f[N][N];
int n,res;
int main() {
	scanf("%s",s1+1); n=strlen(s1+1);
	res=n-1;
	for(int i=n; i>=1; i--) s2[i]=s1[n-i+1];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
			f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1]));
			if(i+j==n-n%2) res=min(res,i+j-2*f[i][j]);
		}
	}
	printf("%d\n",res);
	return 0;
} 

B

C

在一颗树上，有 \(q\) 次询问，每次询问独立。
删除某条边 \(v,fa_v\)，询问某个点 \(u\) 以下内容。
是否到达根节点；若否，是否到达任意特殊点并求出距离。

第一个询问，则是问 \(v\) 是否在 \(1->u\) 路径上，求 \(Lca\) 即可。

第二个询问，我们先钦定一个数组 \(f_u\) 代表 \(u\) 子树内最近特殊点，\(dis_u\) 为 其到根节点距离。
这样就求出子树内特殊点的答案了。

对于子树外特殊点 \(w\), 我们怎么处理呢？
令 \(g\) 为 \(Lca_{u,w}\)
计算为 \(dis_u+dis_w-2*dis_g=dis_u-dis_g+f_g\).
就是求所有 \(g\) 中最大的 \(-dis_g+f_g\).
树上倍增即可。

D

在树上，求 \(\sum_{1\le i<j\le n} (a_i⊕a_j)\times dis_{i,j}\).
看到异或，考虑拆位，然后点分治。