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