ABC369 笔记
Garbage_fish
·
·
个人记录
简单题合集，给 CSP-J 攒信心用的，14:30 开始打。
A
样例都把三种情况全部列出来了，两点相同 1 种，两点不同中间距离奇数 2 种，否则 3 种，三个 if。
## [B](https://www.luogu.com.cn/problem/AT_abc369_b)
模拟即可。
思考在洛谷打还是打 VP 犹豫了三分钟，$14:36$ AC。
## [C](https://www.luogu.com.cn/problem/AT_abc369_c)
乍一看没啥思路，但等差数列相邻两个数的差相等，处理出 $2$ 个数之间的差，构成数组 $b$，尺取法找 $b$ 中连续相同的最长段，如果这一个段距离是 $len$，那么每一个连续子段都能构成答案，答案就有 $len(len+1)\div 2$ 个。再加上 $n$ 个数单独也算等差数列。$O(n)$ 可过。
$14:43$ AC。
## [D](https://www.luogu.com.cn/problem/AT_abc369_d)
上厕所回来，很容易想到设状态 $f_{i,0/1}$ 表示取到第 $i$ 个数攻击偶数次 / 奇数次。转移方程很好写：
$$f_{i,0}\gets \max(f_{i,0},f_{i,1}+2a_i)$$
$$f_{i,1}\gets \max(f_{i,1},f_{i,0}+a_i)$$
$\max$ 中前一个数表示不打，后一个数表示打。$O(n)$ 可过。
$14:51$ AC。
## [E](https://www.luogu.com.cn/problem/AT_abc369_e)
这题不和 [ABC375F](https://www.luogu.com.cn/problem/AT_abc375_f) 一样吗，跑一次 Floyd，$k$ 这么小直接暴力枚举接这五条边的顺序和正反怎么接，没了。$O(n^3+q2^kk!)$ 可过。
$15:12$ AC，有个小细节写挂了调了一会。
## [G](https://www.luogu.com.cn/problem/AT_abc369_g)
看 F 没思路，感觉有点像 J 2022 T4，但好像并不是，而且我也忘了那题了，先看 G。
瞪眼没什么思路，但画图很容易发现青木一定会尽量选叶子节点，选叶子节点的最优策略是尽量选重链，能让高桥走 $2$ 倍重链的距离，那么这就是一个超级弱化版的 [CF526G](https://www.luogu.com.cn/problem/CF526G)。树剖统计每条链边权和，按大到小排序取即可。
$15:34$ AC，$2\times 10^5$ 看漏个 $2$ 错一发 RE。
## [F](https://www.luogu.com.cn/problem/AT_abc369_f)
和 larsr 处理事情耽搁了一会，突然发现可以按行为第一关键字，列为第二关键字排序，用树状数组 $\text{query}(x)$ 已经维护了的行中，$[1,x]$ 列的最多硬币数，然后就可以愉快的转移了。设 $f_i$ 表示第 $i$ 个硬币为终点，最多取的硬币数。
$$f_i={\text{query}(y_i)}+1$$
再把 $f_i$ update 进 $y_i$ 的位置就行了。
然后思考了一下怎么打路径，想了一种按 $f_i$ 大小贪心取方法但是错误的，发现可以在树状数组中同时维护最大值和这个最大值是从哪个数来的，这样转移的时候也可以知道这一步是从哪个数来的，一个递归回去即可。$O(n\log w)$ 可过。
$16:00$ AC。