【比赛记录】ABC359

· · 个人记录

记录

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，也就是叶子节点的贡献。合并时先减去父亲节点子树原有的贡献，然后把子节点子树的数量并上，再用式子计算整个父亲子树与外界的贡献即可。