标签格式

• 思路
• 算法
• 特殊

CF1155F

标签

分析性质
图论，状压 DP，枚举
记录方案，

思路

做的时候想了几个错误做法，还看错题了。

因为边双的形态必然是由一个点加多条链组成的（耳分解）（一个环 = 一个点 + 一条链），即糖葫芦型。

又因为 \(n\le 14\) 考虑暴力。

先预处理出 \(path_{i,j,S}\) 代表一条链，经过了 \(S\) 中所有点，且两个端点为 \(i,j\) 的一个方案。

直接对于每个点作为其中一个端点暴力即可。

然后 DP，设 \(dp_{S}\) 中存了 \(S\) 作为一个边双的最少边数，枚举所有链，即 \(S\) 的所有子集，将答案取 \(\min\) 。

最终输出方案可采取回退，一条链一条链输出。

带注释 code

经验

边双的形态必然是耳分解形态的，同理，能耳分解的一定是边双。

补充

耳分解指每次一条链（若 \(x_1 = x_k\) 也视为一条链），与边双互为充要。

开耳分解指每次的链满足（\(x_1 \not= x_k\)），与点双满足互为充要。

CF1610G

标签

贪心思想
Hash，字符串，倍增，DP

单调栈

思路

首先若要进行消去操作必然消去一段连续的区间，即若一次操作为 \([l,r]\) 则在这之前 \([l + 1, r - 1]\) 内的都已被消去。

正确性

在 \([l,r]\) 中有字符时，因为 \(s_l = (\) 且消去后变优，故有 \(s_{l + 1} = (\)，同理，\(s_{l + 1\sim \frac{l + r - 1}{2}}\) 都为 \((\)，如果 \(r - l + 1\) 为奇数，那 \(s_{mid} = (\) 可以将左半边操作全部右移一位。

即一个位置最多作为一个可消除区间的左端点，单调栈处理即可。设 \(to_i\) 中记录可消除区间的右端点，若没有则为 \(i - 1\)。

于是从后往前设 \(f_i\) 为 \(s_{i\sim n}\) 的最优序列。有 \(f_i = \min(s_i + f_{i + 1}, f_{to_i + 1})\)。

但这样是 \(O(n^2)\) 的，因为 \(\min\) 的比较是 \(O(n)\) 的。

考虑如何优化比较，想到用倍增维护 \(s_{i\sim n}\) 的 \(2^j\) 长度的前缀的 Hash 值，比较两个字符串时倍增一下找出第一个不同的位置即可。

写法

先当作 \(f_i = s_i + f_{i + 1}\) 处理。

开一个数组 \(S_i\) 代表 \(s_{i\sim n}\) 的实际开始位置。

初始化 \(S_i = i\)。然后将 \(f_{to_i + 1}\) 与 \(f_i\)（当前）比较一下，若 \(f_{to_i + 1}\) 更优，只需设 \(S_i = S_{to_i + 1}\) 即可，因为可能存在 \(to_i + 1\) 也被消去的可能。

代码

code

经验

用 Hash 维护 st 表可以 \(O(\log n)\) 判断两个子串大小。

最优解问题通过操作最优性简化题目，采用 DP 贪心的思想。