2020 省选联考 游记 ?

坐标 HB，联考 A 卷 ### day0 根据我一场好一场不好的诅咒，我本来在模拟赛发挥良好的情况下需要一场 CF 调整运势的，但是助教和家长都强烈反对，只好作罢。 于是这是颓废的一天，补了星姐B限的录播，再把自己的博客翻了一遍，在惊叹于我几个月前咋这么能肝的同时找到了成吨的错别字和病句，想了想之后继续去颓了。 勉强把 BM 和线性递推写了一遍，一边祈祷不会出整式递推题。 ### day1 昨晚 10:00 就睡了，但是翻来覆去了半个小时才睡着。尽管如此，睡眠时间依旧比平常多了近三小时，导致整个人特别亢奋。 看到其他学校的选手被拦在门口不让进，但是自己出示本校的通行证就放行，人生第一次感受到主场的巨大优势（并不） 排队进场的时候突然想起来昨天没写一遍带花树，再次祈祷不会出一般图匹配。 向总给我发了三块大的巧克力，加上自己带的，我的键盘前放着半斤巧克力。 发题的时候我又把虚拟机玩坏了，明明是之前一直在用的电脑，却只记住了有哪些方法可以玩坏...好在可以继续 windows 编程。 T1 观察了一下，发现是前缀和后缀和取 $\min$，这个可以二分，但是更好的想法是在线段树上进行二分。于是码，1h 码完，在发现和样例对不上，于是猜将最优的位置挪动到下一个冰人的位置上不会使得答案变差。猜完后对了，但是因为使用了 multiset 需要跑 4s，于是改成了线段树就只需要跑 2.6s 了。 写暴力，对拍，1.5h 的时候 T1 就拍上了。 T2 原题，就在最近考过，但是我当时没场切。不过我记得用到了下降幂，于是把下降幂带进去发现转化成了二项式定理，于是码，然后 5min 就过了所有样例。虽然感觉贼稳，但还是写了个 1000 的拍子，然后发现当模数小于 $m$ 时会错...改了改就过了。 2h 有了 200pts，感觉螺旋稳，于是开 T3。 T3 给了俩满秩的线性基，相当于其他数要对于集合中的部分数存在偏序关系。想了想转化成一张表示偏序关系的有向图，并且爆搜两个集合内的值可以唯一确定剩余点的值。在加上 $A=B$ 的部分分，这就水出来了 40pts。 我一直感觉这个数据范围和这个复杂的限制长的非常网络流，但是我却错误地认为这个东西一定和费用流有关，于是在费用流了 1h 后无奈打出 GG。 当然也写了点退火之类的乱搞，但是得到的答案实在太差于是干脆没交。 最后是 100+100+40=240，但是校内还有三个 200+，[zeven](https://www.luogu.com.cn/user/127693) 甚至有 250，CSP 爆炸的我顿时感觉很不稳。 下午睡觉，晚上去机房发现只有 [yurzhang](https://www.luogu.com.cn/user/126486) 在，于是乎开始颓。把星姐的录播补完之后发现才 7 点，于是看了一小时 lpl。20:00 开始打 AGC，果然又是只会 A 的一天呢，但是终于一场比赛爆炸后，一场好一场炸的诅咒应该就会消失了，于是心满意足地回家睡觉了。 ### day2 早上 6:20 就醒了，看天花板到 7:00 才起来，吃早饭的同时复习了一遍斯特林数。 发现身份证不见了，赶紧打电话给助教，还好找到了。 在校门口看到除了校外选手被拦住了，还有一个 [zeven](https://www.luogu.com.cn/user/127693) 也在傻傻地等。发现其没带通行证后嘲讽并把她带了进去。 解包的时候整个人特别兴奋，因为实在是炸过太多次 day2 了，而这次显然是一场不能炸的考试。 看完三道题之后感觉 T3 最可做，我昨晚水群的时候跟群友聊过一个类似的题，于是半小时码完，发现 n 为偶数的时候答案负了，于是猜直接取反输出。造极限数据卡了卡常感觉螺旋稳，手造了几组没问题就丢了。 T2 按套路按位分解，然后发现每个点的贡献是一段不足 $2^k$ 的段和 $2^k$ 的段交替，这显然可以用树上差分表示，并且通常定义的倍增数组可以直接做。于是乎推了一会就码，码了大概 40min 过了所有样例。接下来写暴力拍，发现极限数据需要跑 3s，于是预处理 dfs 序来模拟 dfs，减小递归的常数。在重构的时候犯了几个低级错误花了一些时间。 2h 又有了 200pts，感觉螺旋稳，于是开 T1。 T1 发现每个元素的贡献只和相对顺序和当前位置有关，直接 dp 就有 60pts，码完后一遍卡常一遍继续思考。然后发现只需要知道已填集合到单点的入度和出度就可以 $O(1)$ 转移，而这个信息也可以 $O(m2^m)$ 处理出来，于是迅速码...码完一跑，极限数据 3.3s，并且用了 750+MB 的空间。 ...尴尬了 记得 POI 有个状压最短路卡空间，需要利用只有从 $1$ 少的状态到 $1$ 多的状态的转移这个性质，将空间压到组合数级别。 还剩 1.5h，码码码，调调调，卡卡卡，尽可能地去精细实现每一步，终于在还剩 15min 时将空间卡到了 514MB。 ...恋恋你在逗我吧 实在卡不动了，于是退而只求其次，改成 $m=22$ 就只需要 267MB 的空间，一测发现需要 2.1s，在有限的卡常后卡到了 2.04s... 认了，希望 CCF 的少爷机比 hsy 的破电脑好。 最后 70+100+100=270，问了一圈发现都没过 T3，但是 [zeven](https://www.luogu.com.cn/user/127693) 自称过了 T1，一问才知道他要 2.5s，膜之。[蒋队](https://www.luogu.com.cn/user/62267) 似乎状态不是很好，没讨论就走人了。 然后教练就说要开始努力文化课了... 我努力省选不就是为了不学文化课吗？[大哭] upd：CCF 少爷机 nb，D2T1 测出来了 80pts