CF1610G. AmShZ Wins a Bet
题目描述：
对于一个串，一次操作可以在其中任意位置加上左括号和右括号，且左括号在右括号左侧，现在经过若干次操作得到串 $S$，求字典序最小的可能的原串。
$1\leq |S|\leq 3\cdot 10^5$。
思路
若删除了若干个括号对，那么这些括号对一定可以转化为不交叉的关系，相互之间要么包含，要么无关，也就是说，任意两对括号之间互不干扰，没删除一对括号，字典序必须减少。
由此推出，删掉的括号对之间一定都是左括号，右括号右侧的不管。那么我们将这个括号对改为相邻的括号，于是我们得出结论，只能删除相邻的括号对，也就是说，若要删除左括号 $l$ 和右括号 $r$，那么 $s_{[l+1,r-1]}$ 一定是括号匹配，且一定删除。
于是只要设 $f_{i}$ 表示 $s_{[i,n]}$ 的最优决策，设 $to_i$ 表示最小的满足 $[i,to_i]$ 为括号匹配的点。
$f_i =\left\{\begin{matrix} & \min(s_i + f_{i + 1},f_{to_i + 1}) & (to_i存在)\\ & s_i + f_{i + 1} & \end{matrix}\right.$
可以进行 $O(n^2)$ dp。
接下来可以直接主席树+哈希，复杂度 $O(n log n)$。
有一种巧妙的方法是使用 $ST$ 表简单维护哈希值，复杂度 $O(n\log n)$。
CF1517F. Reunion
题目描述
给定一颗树，每一个点有各有 $\frac{1}{2}$ 的概率为黑点或白点。
一棵树的值为最大的 $r$ 满足存在白点 $x$ 使得满足 $dis(x,y) \leq r$ 的都是白点。
求树的值的期望。
$n\leq 300$。
思路
我们枚举 $r$ 求有多少个状态使得值大于等于 $r$，发现只要求出有多少个状态使得树上每一个点都有一个黑点使得 $dis(x,y)\leq r$ 也就是让黑点覆盖整棵树。
转化之后，设 $f_{i,j,k}$ 表示 $i$ 子树内最深的点与 $i$ 的距离为 $j$，且黑点向上的半径为 $k$。
发现 $j,k$ 不可能同时出现，然后树形 $dp$，$j,k$ 都是 $O(siz_i)$，复杂度上限 $O(n^2)$， 总复杂度 $O(n^3)$。
CF573D. Bear and Cavalry
思路
若忽略对应关系，那么直接将 $h,w$ 分别排序，根据排序不等式，答案为 $\sum h_i w_i$。
考虑有对应关系，首先对 $h,w$ 排序，设 $f_i$ 表示前 $i$ 个的最大值。
根据排序不等式，分类讨论后，我们发现最优方案一定将 $[1,i]$ 分成若干段，每段长度小于 $4$，且不练相对应的边。
于是有一个 $O(nq)$ 大常数 $\texttt{dp}$，这个正解是 $\texttt{ddp}$，通过线段树维护区间矩阵，复杂度 $O(q\log n \omega^3)$，其中 $\omega = 3$。
然而我们可以暴力 $dp$ 卡过去。
CF1225G. To Make 1
题目描述
给定 $n,k$ 和 $n$ 个数 $a_i (1\leq i\leq n)$，保证 $k \nmid a_i$。
每次选择两个数 $x$ 和 $y$，删除 $x,y$ 之后加入数 $f(x+y)$，问是否能经过 $n-1$ 次入上操作使得最终数为 $1$，如果是，构造一个合法方案。
$x$ 能被 $k$ 整除，则 $f(x)=f(\frac{x}{k})$，否则 $f(x)=x$。
$n\leq 16,\sum a_i\leq 2000, k\leq 2000$。
思路
观察到 $n$ 极小，考虑装压 $\texttt{dp}$。
对于一种方案，设 $b_i$ 表示 $a_i$ 这个数在合并过程中被除以 $k$ 除了 $b_i$ 次，那么 $\sum \frac{a_i}{k^{b_i}}=1$。
然后思考假设我们有了 $b$ 数组，如何构造操作方案？
设 $B=max_{i=1}^n b_i$ 将等式两边同时乘以 $k^B$ 得到，$\sum a_i k^{B-b_i}=k^{B}$。
等式右侧一定被 $k$ 整除，所以得到 $\sum_{b_i = B} a_i \equiv 0 \pmod k$。设 $S = \{a_i\mid b_i=B\}$，我们从中随机选取两个数 $x,y$，若 $x+y\equiv 0\pmod k$ 那么直接删除，否则删除后加入 $(x+y) \mod k$，由于 $k \nmid a_i$，所以 $S$ 中没有 $0$ 元素，所以任何时候都不可能只剩下一个元素。
构造完后，我们会得到一个更小的子问题，于是得证方案与 $b_i$ 一一对应，从一个有序的问题转为无序。
问题就是能否构造出 $b_i$，满足 $\sum \frac{a_i}{k^{b_i}} = 1$。
我们画一个柱状图，$i$ 上的值为 $b_i$，从上而下扫描的过程，就是不断加点，或者整体除以 $k$ 的过程。
设 $f_{u,j}$ 表示我们已经加入的点状态为 $u$，然后和为 $j$ 是否可行。
加点指的是 $f_{u,j} \to f_{u \oplus 2^{k}, j + a_k} (2^k \notin u)$。
整体除以为 $f_{u,j} \to f_{u, \frac{j}{k}} (k\mid j)$。
最终查询 $f_{2^n-1,1}$ 即可。
转移复杂度 $O(n2^n\sum a_i)$，进行 $\texttt{bitset}$ 优化则是 $O(\frac{n2^n \sum a_i}{\omega})$。
CF1562E. Rescue Niwen!
题目描述
给定长度为 $n$ 的字符串，求字符串序列 $s_{[1,1]},s_{[1,2]},\cdots,s_{[1,n]},s_{[2,2]},\cdots s_{[n,n]}$ 的最长严格上升子序列。
大小用字典序定义。
$n\leq 5000$。
思路
结论题。
首先有一个结论，若选择了 $s_{[i,j]}$，那么一定选择 $s_{[i,j+1\sum n]}$。
证明：假设我们选择了 $s_{[i,j\sim k]}$ 但是没有选择 $s_{[i,k+1]}$ 而是选择了 $s_{[l,r]}$。
首先 $s_{[l,r]}$ 必须满足 $s_{[l,r]} > s_{[i,k]}$ 且 $s_{[l,r]} \leq s_{[i,k+1]}$。
考虑 $s_{[l,r]}=s_{[i,k+1]}$ 的情况，这个状态下明显 $s_{[i,k_1]}$ 更优。
然后，推出 $|s_{[l,r]}|=|s_{i,k+1}|$，于是 $s_{[l,r-1]}=s_{[i,k]}$ 且 $s_r < s_{k+1}$。
由 $s_{[l,r-1]}=s_{[i,k]}$ 这个信息，我们发现选择 $s_{[i,j\sim k]} \sim s_{[l,r]}$，一定不如 $s_{[l,(r-1+j-k) \sim r]}$，证毕。
于是维护 $f_i$ 表示取到 $s_{[i,n]}$ 的最大子序列长度，设 $g_{i,j}$ 表示 $s_{[i,n]}$ 和 $s_{[j,n]}$ 的 $LCP$，然后 dp 即可。
CF771D. Bear and Company
题目描述
给定长度为 $n$ 的字符串，每次操作可以交换相邻两个位置字符，求最少操作次数使得字符串不包含子串 VK。
$n\leq 75$。
思路
首先对于不是 $V$ 或 $K$ 的，用 $Z$ 代替。
发现相同字符之间不改变顺序，如果我们有了最终的状态 $T$，那么 $T$ 中第 $i$ 个 $j$ 字符与 $S$ 中第 $i$ 个 $j$ 字符相对应，$S_{p1} \longleftrightarrow T_{p2}$，设 $a_{p2}=p1$。
于是从 $S$ 到 $T$ 的最小步数为 $a$ 的逆序对个数。
综上，设 $f_{i,j,k}$ 表示 $T$ 中前 $i+j+k$ 个字符中有 $i$ 个 $V$，$j$ 个 $K$，$k$ 个 $Z$ 情况下最小的逆序对数，简单 dp 即可，复杂度 $O(n^3)$。
