ACGO巅峰赛#28 全题解
T1
容易发现，一次合并相当于被动方无变化，增加了主动方的一些代价。
所以我们枚举最终结果是哪一堆 iii，分别考虑 iii 左边和 iii 右边的最小代价。
显然，如果 j=1j=1j=1，那么只能左并右；如果 j=nj=nj=n，那么只能右并左；否则取 min\minmin；
搞一个前缀和、后缀和就好。
时间复杂度：O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)。
T2
看到所求内容想到二分。考虑如何写 check\operatorname{check}check 函数。
我们可以跑最短路，路径长度为使用“硬跨”的次数。
时间复杂度 O(nmlognmlogH)O(nm \log nm \log H)O(nmlognmlogH)。可能卡常一下可以过，我没试。
考虑优化，容易发现每次松弛增加的路径长度为 0/10/10/1，使用 01bfs 即可。
时间复杂度：O(nmlogH)O(nm \log H)O(nmlogH)。
空间复杂度：O(nm)O(nm)O(nm)。
T3
观察到在任意子树中，其根节点在该子树的层序遍历中一定是最早出现的。
假设我们拿到了一个中序遍历区间 [l,r][l,r][l,r]，我们需要寻找根节点，然后递归左右子树。
而根据观察，我们需要在区间 [l,r][l,r][l,r] 内，找到层序位置最小的节点。线段树查询。
时间复杂度：O(nlogn)O(n \log n)O(nlogn)。
空间复杂度：O(n)O(n)O(n)。
T4
注意到数据范围很小，搞个状压跑博弈论就行。
时间复杂度：O(nm+k2k)O(nm+k2^k)O(nm+k2k)，其中 kkk 是可用格子数量。
空间复杂度：O(nm+k2k)O(nm+k2^k)O(nm+k2k)，其中 kkk 是可用格子数量。
T5
设 dpi,jdp_{i,j}dpi,j 表示 [i,j][i,j][i,j] 范围内的答案，有一种转移方法是 dpi,j=mini≤k<j(dpi,k+dpk+1,j)dp_{i,j}=\min_{i \leq k<j}(dp_{i,k}+dp_{k+1,j})dpi,j =mini≤k<j (dpi,k +dpk+1,j )。
如果 si=sjs_i=s_jsi =sj ，那么我们可以先按照 dpi+1,j−1dp_{i+1,j-1}dpi+1,j−1 操作，然后等最后一步的时候带上 si,sjs_i,s_jsi ,sj 一起删除，则 dpi,j=dpi+1,j−1dp_{i,j}=dp_{i+1,j-1}dpi,j =dpi+1,j−1 。
时间复杂度 O(n3)O(n^3)O(n3)。据说可以四边形不等式优化为 O(n2)O(n^2)O(n2)，但是 ACGO 神机过了。
时间复杂度：O(n3)O(n^3)O(n3) 或 O(n2)O(n^2)O(n2)。
空间复杂度：O(n2)O(n^2)O(n2)。
T6
设 dpi,jdp_{i,j}dpi,j 表示前 jjj 个元素分成 iii 段最小代价，cost(i,j)\operatorname{cost}(i,j)cost(i,j) 表示 [i,j][i,j][i,j] 区间的代价，得到 O(n3k)O(n^3k)O(n3k) 转移方程：
dpi,j=mini−1≤k≤j−1dpi−1,k+cost(k+1,j)dp_{i,j}=\min_{i-1 \leq k \leq j-1} dp_{i-1,k}+\operatorname{cost}(k+1,j) dpi,j =i−1≤k≤j−1min dpi−1,k +cost(k+1,j)
考虑加速 cost(k+1,j)\operatorname{cost}(k+1,j)cost(k+1,j) 的计算。如果新增一个数 xxx，那么代价会增加 (2cntx+1)−(2cntx)=cntx\binom{2}{cnt_x+1}-\binom{2}{cnt_x}=cnt_x(cntx +12 )−(cntx 2 )=cntx 。同理，删除一个数 xxx，代价会减少 cntx−1cnt_x-1cntx −1。
此时我们倒序枚举 kkk，同时维护 cost(k+1,j)\operatorname{cost}(k+1,j)cost(k+1,j) 即可做到 O(n2k)O(n^2k)O(n2k)。
容易发现，对于固定的 iii，最优决策点随着 iii 的增加而单调不减，可以使用分治优化 DP 过程。
时间复杂度：O(knlogn)O(kn \log n)O(knlogn)。
空间复杂度：O(nk)O(nk)O(nk)。
Code:
