Day0
打了一天的板子。吃完晚饭后去杭州,给我校所有选手都买了瓶饮料希望能攒 RP。
Day1
晚上被室友呼噜吵醒了,响得要死根本睡不着。
早上醒来肚子痛,在酒店上了一次厕所,进考场前又上了一次,debuff 拉满了。
考场左前方是 lhx。
开考先把三个题都看了一遍,T2 看起来是个什么比较暴力的数据结构,T3 感觉不太可做。
T1 稍微玩了一会就会了,很快写完过掉样例,只用了半个小时。
然后做 T2,仔细读了一遍题,发现图没有任何性质(甚至没看到 ),那复杂度至少是 了,毛猜猜是什么四毛子状物。想到了一些传递闭包的神秘剖分之类的东西,可以在图上加点维护传递闭包,然后就要维护每个时刻的信息进行查询。尝试了一下,发现首先块长只能取很小而且没办法方便修改,然后尝试改进做法,搞了一会发现可以对每个块二分出 在范围内的集合,然后再二分出答案,这样块长就可以开到 了,修改直接暴力重构两个块,复杂度是 。
但是此时思维被前面的动态维护传递闭包限制,于是以为要上可持久化线段树维护这个东西,然后直接开写,写完发现只能过最低档,瞬间破防了。搞了很久不会优化,先把 T3 8 分写了,然后继续优化 T2 常数。搞了一整场也只能卡到 8s。最后玉玉症离场。
出来后和同学交流了一下才发现根本不用可持久化线段树,当时直接没绷住,原来人在极度无语时是真的会笑出来的。
很破防,,Day1 已经彻底输了。在酒店了自闭了整个下午。
晚上约了大家一起吃烤肉,好像是学 OI 以来第一次聚餐。感觉还有很多事情没有做,我的 OI 生涯怎么就快要结束了……
Day2
前一天晚上躺了很久睡不着,起来一看发现空调没开。晚上又被室友呼噜吵醒,突然意识到我有耳机,戴上之后勉强能睡着了。但是 byd 耳机没电了会响一下,然后被吵醒了,室友还在打呼噜……最后一晚上醒了四五次,估计实际睡觉时间不到 5h……
先看了眼三个题,怎么 T2 又是非多项式。
T1 应该直接按时间贪,写了个暴力验证了一下,然后用 ODT 维护一下就好了,花了 45min 左右。
T2 看着比较困难,先把 AB 写了,然后想 C 性质。问题变成计数缩点后是只有一个点没有入度的 DAG 的图的数量。把 DAG 容斥的式子写出来,特殊处理一下最后一次转移的系数就行了。然后要对每个点集数强连通分量,可能由于睡得太少没有意识到在不限制只有一个没有入度的点的时候其实是任意图,移个项就能求了。于是思考很久不会做。
看了下 T3,先把暴力写了,然后看了下性质 AB,发现可以用最大值来区分不同的序列,然后写了写,WA 了,调了很久的细节终于过了。
最后没多少时间了 T2 还是没进展,又回去看了看 T3 发现我做法好像不基于性质 B,试图紧急改一个 A 性质做法来结果时间不够了。 遗憾离场。




















