给出⼀个字符串 (s) ，由前 (16) 个⼩写字⺟组成。你现在可以把每个小写字⺟替换成 (uparrow) 或者 ( ightarrow) 。然后从 ((0, 0)) 出发，遍历字符串，遇到 (uparrow) 向上⾛⼀步，遇到 ( ightarrow) 向右⾛⼀步。求出折线下方覆盖面积的最大值
(|s|leq3 imes 10^5)
考虑每一对字母 ((p, q)) ， (p) 替换为 (uparrow) 时对 (q) 替换为 ( ightarrow) 的贡献是独立的，因此可以在原串中计算所有字母对的贡献，枚举 (2^{16}) 种替换方案，并用两两之间贡献计算答案，时间复杂度 (O(16^2 imes(|s|+2^{16})))
URAL1544 Classmates 3
给定一张连通无向图，每个点有两种颜色，一次操作可以选择一个点 (u) ，将它与它相同颜色连通块中的所有颜色翻转，问最少翻转多少次使得每个点颜色相同
(nleq50)
先将相同颜色连通块合并，得到一张二分图。对于每个点，求出它到所有点的最短路，按距离分层，答案即为到原点最远的点的距离，容易发现只有任意相邻两层之间有边，因此这是最优构造
CF884D Boxes And Balls
有 (n) 个盒子与 (n) 种颜色的球，第 (i) 种颜色的球个数为 (a_i)
初始时所有球都在 (1) 号盒，每次操作你可以取出该盒子所有球，将这些球分为 (2) 或 (3) 组，将每组放到一个空盒子中，操作代价为该盒子操作前球数。问将第 (i) 种颜色的球放到第 (i) 个盒子，最少的代价。
(nleq2 imes10^5)
倒着考虑拆分的过程，容易发现这是能一次合并 (2) 或 (3) 堆的合并果子。当 (n) 为奇数时，显然不断合并最小的三个，直到只剩一个时，为最优答案；否则，增加一个个数为 (0) 的球，即可解决 (n) 为偶数的情况。
CF884F Anti-Palindromize
给定一个长为 (n) 的串 (s) ，且 (n) 为偶数，每个位置有一个权值 (b_i) ，找到 (s) 的一个排列 (t) ，满足 (t_i eq t_{n-i+1}) ，最大化 (displaystylesum_{i=1}^nb_i[s_i=t_i])
(nleq100)
一种直观的方式是构建网络流，用最大费用最大流，如果没有 (s_i eq s_{n-i+1}) 的限制，能够轻易地表示成匹配的形式，否则可以对每对点 (i, n-i+1) 建一个小写字母虚点限制流量。
有一种贪心做法。找出所有满足 (s_i=s_{n-i+1}) 的数对 ((i, n-i+1)) ；设一共有 (k) 对这样的数对，对于每一对，考虑替换其中 (b) 较小的那一个，记 (cnt(x)) 为有多少个小写字母 (x) 在 (k) 个数对中是被替换的那一个。
若不存在一个 (x) 满足 (2 imes cnt(x)>k) ，可以通过某种构造分配所有被替换的位置，答案即为 (b) 之和减去被替换位置的 (b) 之和
否则，一定会与非 pair 位置交换，考虑把多余的 (x) 放到外部匹配，由于一定有解，只把 (x) 放到外部是可行的，也可以发现这是最优解
CF1117F Crisp String
给一个由前 (p) 个小写字母构成的长度为 (n) 的字符串 (s) ，再给一个 (p imes p) 的邻接矩阵 (G) （保证(G_{i, j}=G_{j, i}) ），若一个字符串的所有相邻的字符 (i) 和 (j) 满足 (G_{i, j}=1) ，那么称这个字符串是“好的”（空串也是好的）。
你每次能够选择一种字符并把当前串内所有这个字符删去，但操作后的字符串必须还是好的。问最终能够得到的字符串的最小长度。
保证一开始的串是好的。
(nleq10^5; pleq17)
考虑一对 (G_{i, j}=0) 的 ((i, j)) 带来的限制，如果一段区间 ([l, r]) 满足 (s_l=i, s_r=j) ，且不存在 (k) 使得 (l<k<r, s_k=i) 或 (j) ，那么区间 ([l, r]) 中的所有非 (i, j) 字符不能在 (i) 或 (j) 被删之前删完
令二进制状态 (S) 中第 (i) 位为 (1) 表示字符 (i) 没被删，若 (T) 为全集去掉区间 ([l, r]) 中的所有非 (i, j) 字符，则 (T) 的所有 (i, j) 这两位都为 (1) 的子集是非法的。确定了所有非法状态后，能从全集出发，只经过合法状态所能到达的就是可选答案集合，暴力计算即可
对于原串每一位 (i) ，将它作为候选区间右端点，枚举左端点，即每种字符上一次出现位置
时间复杂度 (O(p^3 imes(n+2^p))) ，常数较小
CF1320D Reachable Strings
给定一个 (01) 串。每次询问两个等长的子串，询问是否可以从一个经过数次变换变成另一个。变换操作的定义是每次选定一个包含 (110) 或者 (011) 的子段，让 (110 o 011) 或者 (011 o110)
(n, qleq2 imes10^5)
无论怎么操作，只可能挪动长为偶数的 (1) 连续段。去掉长为偶数的 (1) 连续段后，将每一段长为奇数的 (1) 连续段看作一个点，不对 (0) 操作，则每个间隔完全匹配的两个字符串能够通过操作变得一致。
构造答案可以考虑，对于每个 (1) 连续段，若长为偶数，直接丢到最前面；否则丢 (len-1) 个到最前面
判断魔改后的”性质串“是否相同可以 hash
放一份神仙代码之后看看（）https://codeforces.com/contest/1320/submission/72172140