本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-22 23:17:56

记录

AB 速切，C 简单分讨但是调了 20min，DEF 也都正常做，没吃罚时，还行。

题解

A - Count Takahashi

基础判断，略过不表。

B - Couples

记录 $l_i,r_i$ 分别为 $i$ 两次出现的位置，$r_i-l_i=2$ 的 $i$ 的数量即为答案。

C - Tile Distance 2

首先 $y$ 方向的花费一定为 $\left|T_y-S_y\right|$。考虑横向的花费，这里先通过交换保证 $S_x\ge T_x$。然后考虑走到 $T_y$ 行时最多能走到哪一列，首先要到 $(S_x,S_y)$ 所在区域的最左边，然后每走一行可以向右移一格，最后到达目标行后每走两格需要 $1$ 代价，分讨一下即可。

D - Avoid K Palindrome

状压 + 计数 DP。发现 $k$ 特别小，以至于 $2^kn$ 只有 ${10}^6$ 级别，考虑把最近 $k$ 位的情况设入状态，设 $f_{i,j}$ 表示填了前 $i$ 位，且最近的 $k$ 位状态为 $j$ 的方案数，这里用 $0$ 表示 A，用 $1$ 表示 B。

由于要求只有长度为 $k$ 的子串皆不回文，所以边界可以为 $f_k$，方便处理。每次枚举第 $i$ 位填 $0$ 或 $1$，从 $f_{i-1,j}$ 转移时判断 $j$ 右移后加上该位的状态是否合法，即不回文且符合原串要求，若合法就累加即可。

E - Water Tank

发现任意时刻有效的挡板都是高度递减的，也即若 $i<j$ 且 $a_i\le a_j$，那么不考虑 $a_i$ 是不会影响答案的，$i$ 的上一块和 $j$ 之间的高度一定为 $a_i$。

所以用一个栈维护目前的有效挡板，放入二元组 $(h,k)$，表示高度为 $h$ 的目前有 $k$ 块。从 $1$ 到 $n$ 依次处理时，每次都直接压入 $(a_i,1)$，然后处理栈顶直到元素只剩一个或最后两个递减，也就是维护一个单调栈。每次弹出元素时把差值的贡献补上即可。

F - Tree Degree Optimization

显然排序以后不会影响最终答案的值，直接按 $a_i$ 不降排序。考虑如果构造 $f_i<i$ 表示 $i$ 向 $f_i$ 连边，会比较方便处理。

证明比较容易，因为如果一种方案存在 $f_k>k$，那么可以把这两个点交换。具体地，若 $d_{f_k}>d_k$ 直接交换，否则在交换时通过子树移动保持两者的度数不变，保证了方案不劣。同时 $d^2a$ 中 $d$ 增加 $1$ 时，变为 $(d^2+2d+1)a$，产生的代价为 $(2d+1)a$。

所以初始设 $d_i(i\in[2,n])=1,d_1=0$，开小根堆存储所有可能产生的代价及编号，初始压入 $(1,a_1)$。之后每次使用 $k$ 时都把 $d_k$ 加上 $1$，之后压入 $(2d_k+1)a_k$，全部处理完之后得到的即为最小代价。

G - Sum of Tree Distance

考虑把贡献拆到边上，$x$ 连向父亲的边贡献为 $\sum_{i=1}^n s_{x,i}\times (s_{1,i}-s_{x,i})$，合并时使用启发式合并，均摊复杂度 $O(n\log n)$。

具体操作是用 map 维护子树内所有的颜色种类和个数，另外设 $v$ 为目前点连向父亲的边的贡献，初始为 $s_{1,c_x}-1$，也就是叶子节点的贡献。合并时先减去父亲节点子树原有的贡献，然后把子节点子树的数量并上，再用式子计算整个父亲子树与外界的贡献即可。