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 博客上去。