为二次精选后的题目。
A
题意略
因为只有三种不同的字母
考虑将交换量化，成为将一个字母挪到最前方所需的次数，用$f_{i,j}$表示从第i位开始向后的字符串在k次交换之内得到的字符串数量，然后记忆化搜索即可，每次一定是将“一种”最近的字母挪到最前面。
考虑该状态最多有几种不同的量
B 超好题
题意：代价经过的所有数中前K大数和。
求$(1,1)\to(h,w)$的最小代价。
$h,w\leq 30$
这种题目（前k大和、第k大期望$\dots$ ）有一个套路：枚举第K大数。
我们枚举第K大数，就钦定$A_{mi,mj}$是第K大，那么中间大于等于它的就应该有至少K个，（这样才能保证是第K大的数)。
更好理解地，枚举被选中作为代价的数中的最小数
所以接下来考虑类似dp的做法：从$(1,1)$开始,向右下走，代价被记录为大于等于$A_{mi,mj}$的数之和（如果这个数被视作“第k大左边的数”）。
相等的数既可以放在左边是也可以放在右边。
然后易得 $dp(i,j,k+1)=dp(comei,comej,k)+A_{i,j},A_{i,j}\geq A_{mi,mj}$
那么最终的答案即为$dp(h,w,K)$因为“被选入”的一定是前k大。
对于左右$A_{mi,mj}$求$\min dp(h,w,K)$即可
即可
对于第(前)k大的题目，学会钦定第(前)k大的数后dp
C 超好题
题意：给出九宫格内每个点经过的次数，求从(1,1)出发回到(1,1)的闭合回路能否实现（并构造）。
由于每个$A_{i,j}\geq 1$
所以考虑构造“绕一圈、多的次数经过中间点”的方案（如图、稍后证明）
考虑对于能互相到达的点连边，这样图中就有12条边，又有8个互相独立的方程，所以还差4个量待枚举。
考虑枚举哪四个量能够使边的经过次数确定下来。
由于九宫格的中心对称性，我们考虑枚举这四条边被往返的次数。
枚举了红色的这四条边，由于四个角上的点有且仅有两条连接的边，所以蓝色的箭头就都可以确定下来，那么已知边上的点的总经过次数，可以确定绿色箭头。
举个例子：
已知$A(1,2),A(1,3), a,b$
那么$x_=A(1,2)-a-1-(A(1,3)-b-1)$
枚举四个红色箭头并check即可
check：每个绿色箭头都大于等于0，且和等于A(2,2)
最后输出方案即可。
[证明](待补充)
考虑确定一个状态需要确定哪些量
D
翻译题目 Histogram
发现是“直方图”的意思，然后将题意图形化，数形结合。
对于与位置无关的序列问题，一般将其排序
然后可以发现把$A_i$看作高度，$C_i$看作长度，代价是需要填充的面积，每一种高度会造成x的代价，然后可以发现，低的可以变成高的，但高的就不能变成低的，将$A_i$排序，然后可以得到dp方程$dp_i$表示前i个且第i个的高度不变的最小代价？（将这个看作“仓库建设”）
$$
dp_i=\min_{j=0}^{i-1}{dp_j+cost(j+1,i)}
$$
其中$cost(l,r)$表示将区间$[l,r]$全部变成$A_r$的代价，我们画一个直方图就可以简单地统计出来。
令$S_i=\sum^{i}_{j=1} c_i\times (a_i-a_j)$可以用类前缀和$O(n)$求出。
令$C_i=\sum^{i}_{j=0}c_j$ 可以很简单的$O(n)$
分别表示宽的和和“需要填补面积的和”
然后可以表示出$s_2=C_{i-1}\times (a_r-a_l)$
$s1=S_l$
所以$cost(i,j)=S_{tot}-s_1-s_2=S_r-S_l-C_{i-1}\times (a_r-a_l)$
然后就是个非常简单的斜率优化啦/kk
与前缀和有关的题目，尤其是一些区间内某些量乘积之和，数形结合是一种不错的选择
E
观察可以发现一些性质，在此给出非常简单的证明
引理:玩家在时刻a和时刻b(a<b)分别出现在点m，情况a不会劣于情况b 很明显敌人原本可能到达的点现在还是能够到达，并且有可能多出新的能够到达的点。 性质1:玩家只会向下走 玩家初始是出现在根节点的，所以第一步一定向下走。 若在一步向下走后回到了这个点本身，不会优于开始状况（引理1） 性质2:敌人只会向上走 我们称每个敌人本身及下方的区域为***的区域，在双方最优决策下，玩家无法到达被***的区域。 如果有一步，敌人向下走，那么被***的区域只会变小至少1.不优于向下走.发现了这些性质之后，这个问题就变成了玩家和敌人的“相遇问题”
所以敌人能够封住这个点的充要条件是敌人能够比玩家先到达这个点本身或其祖先节点。
然后进行一次$dfs$处理方式和LCA相同，处理出向上倍增的f数组，将每个敌人的位置向上跳$\lfloor depth \rfloor$次，再从根节点$Dfs$即可。
若有多个移动物，试着确定其中一部分的移动方向
F
简单化题意：给出一个字符串，会对其进行非临时的单点修改，问每次修改后的字符串需要删去至少多少个字符才能不包含字串abc
不考虑修改的情况下：
删完abc 子序列有一些方法
删完最后一个c前的ab子序列
删完第一个a后的bc子序列
···
考虑分治
将删完abc分成子问题考虑。
$A(l,r)$ 区间$[l,r]$的a的个数(删完所有a的最小代价)
$B(l,r)$ 区间$[l,r]$的b的个数(删完所有b的最小代价)
$C(l,r)$ 区间$[l,r]$的c的个数(删完所有c的最小代价)
$AB(l,r)$ 删完$[l,r]$的ab的最小代价
$BC(l,r)$ 删完$[l,r]$的bc的最小代价
$ABC(l,r)$ 删完$[l,r]$的abc的最小代价
考虑怎么转移？
首先$A(l,r)$,$B(l,r)$,$C(l,r)$的转移很明显
$\left{\begin{matrix}A(l,r)=A(l,mid)+A(mid+1,r)\B(l,r)=B(l,mid)+B(mid+1,r)\C(l,r)=C(l,mid)+C(mid+1,r)\end{matrix}\right.
$
接下来考虑$AB(l,r),BC(l,r)$的转移
令$[l,mid]$为$S_1$ $[mid+1,r]$为$S_2$
把这个区间内删完一种子序列就是让左区间的最长前缀子序列+右区间里面的最长后缀子序列长度小于本串要把一个区间的ab删完，
就是把两边的ab都删完，并且把$S_1$的a删完或是把$S_2$的b删完。但把一边的a或b删完后该区间不可能出现ab
所以
$AB(l,r)=\min{AB(S_1)+B(S_2),A(S_1)+AB(S_2)}$
BC同理
最后考虑$ABC$的转移
同理 我们首先需要删完两边abc，然后接下来有一些选择
删完$S_1$中的a(自然也不会有ab)。
删完$S_2$中的b(自然与不会有bc)。
删完$S_1$中最第一个a后方的b并删完$S_2$中最后一个c前面的b
即
$$
ABC(l,r)=\min{ABC(S_1)+C(S_2),A(S_1)+ABC(S_2),AB(S_1)+BC(S_2)}
$$
详细解释：$AB(S_1)+BC(S_2)$ 左边的ab删完了，左边能拿出的前缀就只有a了，同理右边能拿出的最长后缀只有c故无法凑成abc
因为需要进行$O(\log n)$ 级别的单点修改，所以保留区
考虑分治+线段树
建一棵线段树，每次push_up是一次分治。