【比赛记录】CFR960（Div.2）

KSCD_ · 2024-07-21 12:45:34 · 个人记录

记录

AB 过了以后，C 卡了五发不过，D 赛后一分钟写完，掉 100 分，寄。

题解

A. Submission Bait

发现所取数量的奇偶性会影响到最终的胜负，而所取数量取决于先手第一次取的 x 及以上的个数，所以对桶数组做后缀和，只要有奇数就可以必胜。

B. Array Craft

考虑把 [y,x] 内全赋为 1，那么这个区间内肯定是 a_x 前缀最大，a_y 后缀最大。只要在 [1,y-1] 和 [x+1,n] 交错填上 1 和 -1，使所有值不大于要求值，所以 x,y 就是满足下标条件的位置。

C. Mad MAD Sum

发现一次操作后变成递增，两次操作后除了最后一段其余长度均大于 1。把这两次暴力操作，后面就是前面的段不变，同时最后一段消失。那么可以直接处理贡献。

D. Grid Puzzle

发现长度大于 4 的行一定是直接全涂，用这些行分段，对每一段分别 DP，设 f_{i,0/1,0/1} 表示第 i 行是否选 1,2，是否选 3,4 时把前 i 行全涂白的最小代价，转移一下即可。