AtCoder Regular Contest112 解题报告

A

直接推式子 \(\sum_{i=L}^{R-L} R-(L+C)+1\)

那么分开统计即可

B

显然答案覆盖的是不超过两个连续区间,考虑是正的时候 \(-1\) 完了减少可以让绝对值变大,直接减少可以让绝对值变小,类似负的时候

那么特判连到一起的情况,简单题

C

先需要把这个游戏的一些性质玩清楚

其实这个先后手是和子树大小有关的

如果这个子树的大小为奇数,那么出树之后到先手操作,大小为偶数则为后手操作

从后手角度考虑

对于 \(sz\in \{even\}\) 的子节点,排序从最大的开始选

对于 \(sz\in \{odd\}\) 的子节点,排序之后先选择所有的正收益点,再进入偶数点维护

那么进行一轮 \(dp\) 即可

D

显然的结论是如果某一个角可以到达整个棋盘,那么方案成立

充分必要性均显然,那么不妨设这个角是左上角 \((1,1)\)

\(#\) 相当于一个行列转换器,四角有隐形的 \(#\)

那么对于点 \((i,j)\) 上的 \(#\),用并查集来合并行列

最后统计有多少个非 \(1\) 集合即可

这里行列要分开做


后两题比赛没看,就摸了

上一篇:关于并查集


下一篇:我的第19个代码