LNOI 2020 划水记

· · 个人记录

Day -1

想打一个指针版本线段树的板子来着……结果极其颓废，就咕掉了。

Day 0

随机跳了一道题做，结果简单的树状数组扫描线写成了树套树……自闭 /kk

Day 1

开题。

A 好像是一道二分之类的，B 是神仙数论，C 应该是线性基之类的异或相关。

A

看起来题目顺序没什么坑点，于是就先开了 A。

发现 A 的函数图像是单峰的，但是不凸，也就是说朴素二分不了。三分不会（块来 D 菜鸡罢 /cy）

感觉可以用平衡树来实现存储有变化的节点（这里想假了，存了也不全有变化）。

终于调出了平衡树（赛前没写平衡树是个错误的决定（菜鸡代码能力直线下滑）），结果发现想假了。

转念一想这里可以二分冰在下和火在下的交界点（这个位置因为过于紧张就忘了可以删掉平衡树，\log^2 被卡成 60 预定），然后发现可以倍增去求同样答案的最右边界。

B & C

调出 n = 100 的样例已经是 12:45 了。B C 抱灵。

弱省垫底预定（

（现在才发现我不是最近经常崩盘，是之前考得过好了 /kk

Day 2

开题。

A 好像是一道状压 DP，B 是神仙树论，C 应该是反演+生成树计数之类的数数题。

A

还是先开了 A，结果不会设计状态，只会写时空 O(4^n) 的屑状压，结果发现这样和 O(n!) 的暴力枚举全排列一个分 = =

一个小时之后还是没想出来，于是打了一个模拟退火，每次交换温度次。结果这个假的模拟退火参调不出来了 /kk

B

好像是一道树上启发式合并的题，开始的思路是把加法改为异或，但是没想出来。又是一个 O(n^2) 的 sb 暴力走人（（（

C

没时间了，30pts sb 暴力滚粗（（（

70 分全是送的分 = = 有思维含量的一分没拿到 紫菜了 /kk /dk