日常note

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

给定两个序列A,B

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

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

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

2.(A_{i-1}+A_{i+1} ge 2 imes 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 imes (n-1)) 条

所以下面合并子树的次数也只有 (n imes (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序即可化作二维坐标上的问题

1. 当lca(x,y)!=x&&lca(x,y)!=y， (a in [L[x],R[x]]) ，(bin[Lt[y],Rt[y]])

2. 当lca(x,y)==x&&lca(x,y)!=y

   定义s为y所在的关于x的子树的根节点，(ain [1,L[s]-1]cup[R[s]+1,n]) ，(bin [L[y],R[y]])

3. 当x==y

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

   或者 (a=L[s]) (bin [1,n])