The 48th ICPC Asia Hefei Regional Contest
套路题多，要熟悉使用板子
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | ||||
| B | 3 | Dilworth’s Theorem, DP | Upsolved | B.cpp |
| C | 2 | Palindrome Automaton | Solved | C.cpp |
| D | ||||
| E | 0 | Brute Force | Solved | E.cpp |
| F | 0 | Brute Force | Solved | F.cpp |
| G | 1 | Binary Search, DP | Solved | G.cpp |
| H | ||||
| I | 2 | Brute Force | Solved | I.cpp |
| J | 2 | MST, DFS | Solved | J.cpp |
| K | ||||
| L |
*B. Queue Sorting
给一个可重数集，$i\ (1\le i\le 500)$ 有 $a_i\ (\sum a_i\le 500)$ 个，问有多少序列符合能拆成最多两个不降子序列。
根据 Dilworth 定理，最小链分解数等于最长反链长度，即最长下降子序列长度不能超过 $2$ 。
考虑按照值的大小依次插入数字，对于每次加入的数字 $i$ ，只要不是最后一个，必定形成一个长度为 $2$ 的下降子序列。
设 $dp(i,j)$ 表示，数字 $1\sim i$ 已经全部插入，最后一个长度为 $2$ 的下降子序列考前的那个数字的位置是 $j$ 。
令 $sum_x=\sum_{y\le x} a_y$ ，每次 $i+1$ 插入的时候是不能放到位置 $j$ 前面的，所以相当于对 $[j+1,sum_{i}]$ 和 $a_{i+1}$ 个位置做插板。
因为要考虑新的 $j’$ 的位置，所以枚举有 $x$ 个 $i+1$ 直接加到最后了，第一个不是最后的位置是 $k$ ，转移是
$$
dp(i+1,k)=\sum_{j, x} dp(i,j)\times {k-j-1 \choose a_{i+1}-x-1}
$$
组合数的含义是，新序列灵活的位置有 $k-j-1$ 个，其中有 $a_{i+1}-x-1$ 个是 $i+1$ 。
特殊处理全都放到最后的情况：$dp(i+1,j)=dp(i,j)$ 。答案是 $\sum dp(n,*)$ 。
复杂度 $O(n\times \max a_i\times (\sum a_i)^2)$ ，比较大但是跑不满 。
C. Cyclic Substrings
首尾相接的字符串 $S$，对每个回文子串 $t$，出现次数是 $f(t)$ ，长度是 $g(t)$ ，求 $\sum f(t)^2\times g(t)$ 。
回文树，一个串的出现次数就是对应节点在 $fail$ 树上的子树总出现次数。
对于循环，考虑倍长成 $S+S$，一个串只有在结束位置 $>|S|$ 时才被计数，这样不会数重。
但还要保证只计数串长 $\le |S|$ 的串，因此在统计答案的时候只有节点代表的长度符合要求才被算进答案即可（注意这并不影响该节点向其 $fail$ 树上的父节点贡献累计出现次数）。
复杂度 $O(|S||\Sigma|)$ 。
E. Matrix Distances
签到，按颜色分类计算，XY分离，排序，前缀和。
F. Colorful Balloons
签到，map 统计字符串出现次数。
G. Streak Manipulation
给一个长为 $n\ (1\le n\le 2\times 10^5)$ 的 $01$ 序列，最多把 $m\ (0\le m\le n)$ 个 $0$ 变 $1$ 。
对于修改后所有极长的 $1$ 连续段，最大化其中第 $k\ (1\le k\le 5)$ 长的长度。
二分答案，尝试是否能搞出来至少 $k$ 个长度超过 $mid$ 的段。
令 $dp[i][j]$ 表示到 $i$ 为止，搞出 $j$ 个符合要求的段最少需要修改多少次。
由于极长，需要满足当前位置是这一段的最后一个，需要 $i=n$ 或 $i+1$ 的位置是 $0$ 。
然后找出 $i-mid$ 往前的第一个 $0$ ，然后中间这段的 $0$ 都得改成 $1$ 。
对于前面的代价，找一个 $dp[*][j-1]$ 的前缀最小值即可，记录前缀 $\min$ 优化一下。
复杂度 $O(nk\log n)$ 。
I. Linguistics Puzzle
给一个 $n\ (n\le 52)$ 进制的乘法表，每个数位都一对一映射到了一个字母，还原每个字母代表的数位，多解输出任意解。
乘法表里的数字最多两位，因此先求出每个数位在个位和十位（进的位）分别应该出现多少次。
然后对给出的字符表计算同样的结果，按照两个次数构成的 pair 分类。
这样每个字符/数位都会分到某一类中，感性理解一类里的元素不会很多，因此在此约束下，暴搜每个数位对应的字符。
复杂度我不会证明，但是真闲的没事可以打表找一下上界 。
J. Takeout Delivering
一个有边权无向图 $(n\le 3\times 10^5,m\le 10^6)$ ，找一个 $1$ 到 $n$ 的路径，最小化路径上最大边权+次大边权。
枚举最大边，枚举 $1,n$ 分别连接这个边的哪个端点，次大边来自这两段路径。
变成最小化路径最大边权，答案一定在最小生成树上，从 $1,n$ 分别 DFS 一遍最小生成树求出到每个点的瓶颈边即可。
判断答案时注意要保证两段的瓶颈边权均不超过枚举的边权。
复杂度 $O(m\log n)$ 。
The 48th ICPC Asia Hefei Regional Contest