咕咕咕。
D - All Assign Point Add
把数拆分成 \(base + delta\) 。 \(base\) 就是操作一设置的数,初始时认为 \(base = 0\);\(delta\) 的维护可以有两种方法。
一种是我比赛时的做法,类似树状数组的时间戳优化额外维护一个时间戳,时间戳对不上就先清空一下。树状数组的时间戳优化可以参考oi wiki。
另外一种是官方题解的做法,就存一下操作二的修改,有操作一就清空。因为操作数为 \(Q\) ,所以至多清空 \(O(Q)\) 次。
E - Grid Filling
注意到 \(H, W, N\) 都挺小的。
可以在 \(O(HWN)\) 的时间内,枚举每个数字,借助二维前缀和预处理出这个数字在左上角为 \((1, 1)\) 右下角为 \((i, j)\) 这个矩形内的数量,之后借助矩形容斥可以 \(O(1)\) 查询任意矩形内这个数的数量。
然后枚举被删去的那个矩形,再枚举每个数,如果这个数不是仅出现在被删去的矩形内,那么对答案就有 \(1\) 的贡献。这个过程复杂度也为 \(O(HWN)\)。
F - Shiritori
简单 DAG 上博弈。
对于一个状态 \(x\) ,枚举它所有的后继状态,只要有一个先手必败的后继状态, \(x\) 就是先手必胜,如果一个先手必败的后继状态都没有 \(x\) 就是先手必败。
参数都挺小的直接 DFS 就能过了。
G - Generalized Subtraction Game
To be added.
Ex - make 1
To be solved.
标签:AtCoder,Beginner,必败,后继,枚举,base,清空,278,矩形 From: https://www.cnblogs.com/zengzk/p/16907559.html