07-25 题解
原题出处（按顺序）：
CF1556E
CF1234F
P9746
CF1316E
P3651
CF17C
CF1842H
A
转化： 括号序列
-
如果 \(a_i\ > b_i\) ， 则有 \(a_i - b_i\) 个左括号
-
如果 \(a_i\ < b_i\) ， 则有 \(b_i - a_i\) 个右括号
（第一个 +1 的位置一定在第一个 -1 的位置的左侧，所以情况一用左括号表示）
问题转化为判断括号序列是否匹配：
- 左右括号和为 0
- 前缀和中左括号数量 \(\ge\) 右括号
按照 1/-1 的套路做前缀和， 用区间数据结构维护（线段树/st 表）
如何统计操作步数？
每次只能让该位置的数 +1 一次， 即每次只能删除一段连续左/右括号中的一个
所以答案就是前缀和数组的最大值
B
观察：
- 只有 20 个小写字母
- 反转子串是一种伪操作， 实际上就是选任意两个不相交的子串拼在一起
枚举以每个位置为起点/终点能贡献的 unique 子串（一共最多 20n 个）
对于每一个 unique 子串， 考虑找一个最大的不相交串使得拼起来长度最大
设当前子串的字符集为 \(S\) ， 实际上就是找 \(max(T)\ (T\ \in C_{\sum}S)\) (T 在 S 的补集中)
因为两个相交子串的字符集肯定有交集， 所以直接对字符集做高维前缀 max 即可
C
鸽
D
我们想要在选 p 的同时保证选的 a 也是最大的
小技巧 ： 对 \(a_i\) 降序排序
设当前考虑到了第 \(i\) 个人， \(p\) 个人中选了\(p_0\) 个， 如果 \(i - p_0 < k\) 那么这第 \(i\) 个人是必须选的
然后就做完了
E
本题中的图实际上是多棵基环树， 并且是内向树
基环树：具有N个点N条边的连通图。
内向树：每个点有且只有一条出边。也就是这棵树给人的大体感觉是向内的。
外向树：每个点有且只有一条入边。也就是这棵树给人的大题感觉是外向的。
Trick：对于基环树， 把环和链分开考虑
首先， 所有点最后构成一个环， 每个点的出度、 入度均为 1
然而目前每个点可能有多个入度
-
如果没有环的话， 直接贪心地保留每个点修改代价最大的入度即可
-
如果有环， 并且环的大小不为 n （否则修改的代价为 0）， 一定要断开环上的一条边， 枚举环上节点， 断掉与该节点的最大出度差最小的那条即可
F
一眼 dp
状态
\(n \le 150\)， 这意味着 \(a, b, c\) 的个数均 \(\le 51\)
那么就可以写到状态里
\(dp(i, a, b, c)\) 表示考虑到了第 \(i\) 位， 整个串 \(a, b, c\) 分别有这些个
再考虑转移
为了不算重， 如果该位置字符为 s， 我们规定他只能转移到 \(pos \ge i\) 的、 \(s\) 第一次出现的位置
（因为如果转移到一个更靠后的位置， 说明 i 到该位置直接的字符全为 s， 与转移到上述位置是等价的）
记这个位置为 \(nxt[i]\)
则：
(dp[nxt[i][0]][a + 1][b][c] += dp[i][a][b][c]) %= MOD;
(dp[nxt[i][1]][a][b + 1][c] += dp[i][a][b][c]) %= MOD;
(dp[nxt[i][2]][a][b][c + 1] += dp[i][a][b][c]) %= MOD;
为什么直接枚举整个串的 \(a, b, c\) 的个数是正确的？
很简单， 如果这种状态不合法， 那么 dp 值为 0， 不用担心
G
鸽
标签：子串,25,07,nxt,题解,位置,括号,dp,前缀 From： https://www.cnblogs.com/Bubblee/p/18327435