1103总结
T1
容易想到只会取到 \(O(n^2)\) 个值，大力动态规划，滑动窗口优化。
滑动窗口的 COST 宏函数写挂了，所以我挂了。
有一个更厉害的思路，容易发现 DP 数组本质上是个分段函数，然后转移就是平移原函数添加一段平的然后再加上一个绝对值函数，根据经典结论，若干绝对值函数叠加是一个形如开口向上二次函数的东西，填一段平的一定会在最低点添，不影响性质。
T2
写挂的题，不过很有意思。
写挂有两个原因，一是图方便用引用，但是没发现被引用的数据其实还有用，然后修改了它，后面又要用它，就寄了。二是转成 \(0-based\) 处理，边转了，但是记录数组先存的边，没有动记录数组。警钟敲烂。
题目本身也是有趣的，首先它定向后必须是个 \(DAG\)，所以只考虑所有的 \(DAG\)，考虑以拓扑序的方式去遍历所有 \(DAG\)，容易发现当拓扑序确定后，定向方式也就确定了，所以一个比较简单的想法是枚举拓扑序。
枚举拓扑序想要转成指数可能不太能用常规方式转，因为的确需要知道每个点的距离, 思考一下其实发现没中过定向方式被计算了多次，所以考虑给这个拓扑序附加一些不影响遍历解空间的性质，比如强制距离单调不降，这样枚举起来就可以大大方方的选一坨独立集，强制转移到它的距离加一，这样的强制加一同样不影响遍历解空间，所以它是对的。
有个东西叫 dilworth 定理, 描述的就是这个东西，最大反链中元素数目等于最小链划分数，我不是很懂这个定理和这道题的关系，但是用这个定理和以上方式思考得出的代码是一样的。
遍历 DAG 的有效方式是通过 TOP 序，尤其是需要定向的 DAG
复杂度 \(O(3^n+n\times2^n)\)
T3
考场上刚出来的题。
指数题看数据范围说话，总感觉子串很麻烦，因为扰乱了信息，所以把子串判掉。
然后觉得如果一个串绕了一圈，也很麻烦，再判掉。
所以现在的环，从某一个子串开始，左端点递增，那右端点也就递增了，所以可以考虑顺序了。
容易发现每个串会尽量往左靠，因为没有子串了，然后最后一个串和第一个串会尽量粘在一起，可以直接把粘在一起的部分减掉，就算减了倒数第二个串的，那其实也没有问题，因为确实可以减掉。
然后阶乘转指数，记录最后一个串的编号和方向，枚举下一个串的编号和方向。
考场上很蠢，每个点为起点算了一遍，其实钦定一个算就行了。
如果把一些 Native 的情况特判掉，可能会得到更加优美的性质，这就是分类讨论题。
T4
字符串替换的题，思路主要有两种。
考虑某个大写字符能替换成什么，发现经过 \(O(\sum)\) 次替换后一定会变成或者多出一个不可替换的字符，所以考虑大力动态规划，设 \(F_{c,i}\) 表示字符 \(c\) 替换成长度为 \(i\) 的不可替换字符串的最小字典序，然后转移顺序不同层已经是固定的，同层转移顺序随意。这样做显然不对，因为有环，但是多做几次他就对了。
考虑按不可替换字符长度为阶段做动态规划，同时处理若干个规则，转移之间如果有环，有两种情况，其一是其它的向它转移过来 \(len\) 个，另一种是下一个大写字符替换为空串，后者可以钦定处理到的位置的顺序转移搞定，前者可以用优先队列类似 DIJ 的思路。
当然，这个思路也可以不考虑转移有环，直接多做几遍就对了。