CSP 2020 游记

# J/S 1 因为是打完第二轮补的，凭印象写点东西吧。 什么都不会，上午 S 组阅读程序 C 题没想到插值，没时间了蒙一个 $84$ 滚了（悲） 下午 J 组抱着稳过的心态凭感觉答，结果分比提高还低（LN 线是真水啊（（（ # J/S 2 ## Day 0 赶去金州，姑姑家在那边，顺便给妈妈烧个头七。本来想翘掉 J 去烧纸的，但是爸爸让我去 J（（（ 虽然就是市区到市区外，没多远，但是也提前一天去比较舒服吧（） 本来想晚上洗个澡来着，但是姑姑着急，就没洗上。 在车上写了个最小生成树，SPFA 没写完（）果然码力退化得这么厉害嘛（（（ ## Day 1 ### J 带了瓶蜜桃乌龙茶，穿着校服，就去了。 A 二进制拆分一波，结果加上初始化 Linux 用了半个小时（悲） B 没想到桶，用的对顶堆切了（） C 感觉是树上标记，利用与和或运算符特性，标记每个节点值的改变是否影响根节点的值，感觉很烦，看 D。 感觉 D 也不能 1min 切，滚去码 C，码码码，100+L 过了大样例，就没管。 C 的话对于树上每个节点，维护几个值： $inf_i$ 表示节点 $i$ 权值的改变是否对根节点权值有影响；$n_i$ 表示如果有影响的话，该影响是否相反（即点权与根节点点权是否相反）；$type_i$ 表示节点 $i$ 的运算种类。 - 如果是与运算，一棵子树是 $1$，另一棵子树 $inf$ 为真，搜索； - 如果是或运算，一棵子树是 $0$，另一棵子树 $inf$ 为真，搜索。 D 先把原图转一下，看着特别难受（） 先想了个 $n^3$ DP（默认 $n, m$ 同阶）： 设 $f_{i, j}$ 为走到 $(i, j)$ 的最大权值和，$g_{i, j, k} = \sum_{o = j}^k a_{i, o}$，则 $$ f_{i, j} = \begin{cases} g_{1, 1, j} & i = 1\\ \max_{k}(f_{i - 1, k} + g_{i, j, k}) & i > 1 \end {cases} $$ 考虑当 $j$ 移动时，$f_{i - 1, k} + g_{i, j, k}$ 的变化在 $j$ 的前后是区间加 / 区间减形式的，可以用线段树维护。 还剩 30min。去年这时候还剩 60min。果然还是变菜了啊（悲） ~~不得不说 Emacs 的游戏真好玩（雾）~~ 期望得分：100 + 100 + 100 + 100 = 400。 ### S 中午睡了一觉，头昏脑胀。 A 出大模拟，爬（全恼） 写了 1h+，调来调去，过了全部样例，造了一下删掉那几天附近的边界觉得特别稳。 B 读了 10min 题，发现特别 ~~SB~~ 简单。 切了，觉得不稳，打了个快读。过了全部样例。 并没有特判 $2^{64}$。 本来打了 `1ull` 的，但是经过一番重构后，就没了（悲） C 假了。 我一开始想的是，把一会加一会乘转化为 $\sum \prod$ 的形式，就是对积求和。 1 和 2 操作很好处理。3 的话如果只执行 1 和 2 的话也可以 $O(c)$ 转化为一个 2 和一堆 1。 然后对于每个 3 求一下这个操作后面的乘积的和 $\sum \prod$，然后计算贡献。 最后求 1 和 2 的贡献。 写了 40min，忘记 3 套 3 了。现在还没和人讨论正解，但感觉这个做法离正解不远（雾） 还是看看 D 罢。 啊这 70pts 不就是支持单点修改和删除的数据结构嘛（） 想上带删除标记的线段树，想了一会没想到更方便的解法，写了 40min，过掉了大样例。 还剩 15min，C 的暴力没打完。 - expected：100 + 100 + 0 + 70 = 270。 - oitiku：80 + 65 + 0 + 70 = 215。 - luogu：40 + 60 + 0 + 70 = 170。 - nowcoder：0 + 0 + 0 + 0 = 0（CE，Clang++11 不支持 `register` 修饰 `typedef` 后的东西（悲） 省一应该差不多，NOIP 翻一波罢。 # 其他 有时间更到 github 博客上去。