日常note

1.插入使相同的最少次数

给定两个序列A,B

每次只能进行把一个元素插入特定位置的操作

求至少对A进行多少次才能使A等于B

设A,B的长度为Len，那么答案为 \(Len-LCS(A,B)\)

2.\(A_{i-1}+A_{i+1} \ge 2\times A_i\)

会发现这个东西，就是一个下凸函数

3.字符串本质不同方案

dp[0]=1;

FOR(i,1,n){

	dp[i]=dp[i-1]*2-sum[str[i]];

	sum[str[i]]=dp[i-1];

}

然后有一个扩展的式子

大概是对于每个字符,取它的概率为\(p_i\),求期望本质不同方案数

dp[0]=1;

FOR(i,1,n){

	dp[i]=(dp[i-1]*2-sum[str[i]])*p[i]+dp[i-1]*(1-p[i]);

	sum[str[i]]=dp[i-1]*p[i]+sum[str[i]]*(1-p[i]);

}

4.树形背包合并是\(O(n^2)\)的

复杂度比较容易证明

把合并两个子树的过程看做枚举以 \(son[x][i]\) 为左端点，以 \(son[y][j]\) 作为右端点路径

这样的路径一共只有 \(n\times (n-1)\) 条

所以下面合并子树的次数也只有 \(n\times (n-1)\) 次

void dfs(int x,int f){

	sz[x]=1;

	LFOR(i,x,E){

		int y=E[i];

		if(y==f)continue;

		dfs(y,x);

		sz[y]+=sz[x];

		memset(DP[x],0,sizeof DP[x]);

		FOR(i,0,sz[x])FOR(j,0,sz[y])dp[x][i+j]+=dp[x][i]*dp[y][j];

		memcpy(dp[x],DP[x],sizeof dp[x]);

	}

}

5.1e5以内因子个数最多为128 [这个数为83160]

6.树上路径问题

比如要表示包含某条路径(x,y)的点对

利用dfs序即可化作二维坐标上的问题

当lca(x,y)!=x&&lca(x,y)!=y， \(a \in [L[x],R[x]]\) ，\(b\in[Lt[y],Rt[y]]\)
当lca(x,y)==x&&lca(x,y)!=y

定义s为y所在的关于x的子树的根节点，\(a\in [1,L[s]-1]\cup[R[s]+1,n]\) ，\(b\in [L[y],R[y]]\)
当x==y

定义s为x子树， \(a \in [1,L[s]-1]\cup[R[s]+1,n]\) ，\(b\in[L[s],R[s]]\)

或者 \(a=L[s]\) \(b\in [1,n]\)

巴特西