联合省选2021游记

前情提要：noip+wc 比队线低 20 多 ### day -2 打板子，学了上下界网络流 机房一大佬整理出了 70 多页pdf的板子/jk ### day -1 打板子，各种不知多少年前就忘掉了的板子 ### day 0 去考场，~~炒鸡很好吃~~ ### day 1 要爆零了，好耶 原来是八点半考试，记成八点了。。。 发压缩包，看见一个 graph 于是打了 dinic，看见一个 matrix 以为是线代相关的，打了个矩乘一个lu分解 ~~然后当然是一个都没用上啦~~ 发密码了看T1，发现自己在打CF 想了想没思路，但感觉会有一车人切T1 怎么才十多分钟就一堆键盘声了 看T2感觉是个构造（？），T3神仙图论想打个朴素暴力就跑 于是开始想T2，中间想用上下界网络流（我是不是一度接近正解？），但最后发现建不出图来 后来想出了 $m=2$ 的部分，大概就是考虑每一行的和，随便找一个对值域没要求的解然后调整 然后发先是不是可以把每相邻的两列都跑一个 $m=2$ 的做法，然后在横向上跑一个类似的东西来解决 期间打了T3的16分暴力，期间 tarjan 打错两次，再怎么优化完全不会/kk 看T1想出来从两边往中间翻的结论，就写了60分的暴力 优化的话，觉得可能是枚举左边的区间然后二分右边，但没想明白怎么二分也没想明白为什么可以二分/kk 后来想到我会模拟退火，于是写了写，没怎么调参居然就过了大样例/jy 然后对拍，直接拍 $n=10^6$ 的，发现大概每 4 组就会错一组？不过数据当然是随机的 于是数据逊的话我这题能直接拿90？/jy 快结束的时候看左边的老哥在代码里写留言，应该是想进迷惑行为大赏（ 出考场听到一堆不同的 T1 做法，但好像大家都切了只有我写了随机化/kk ~~食堂350一顿的饭差评~~ 后来突然想到我 T1 用来 `RAND_MAX` 但没有引入 `cstdlib`，慌了，要是CE了我怕是100都上不了 > qyc：你？T1？写退火？CE了？ 回家测试发现 `RAND_MAX` 是定义在 `cmath` 里的，那没事了 下午看了一下午电视，晚上吃饭的时候突然想到 T2 每相邻两列跑完的解并不唯一，于是最终算答案的时候可能会判成无解？ 那岂不是只有50了。。。不过要是不硬卡的话看起来非常对，希望数据水吧 于是：$[60,100]+[50,100]+16=[126,216]$ 了，当然大概率是 126，乱搞果然没前途 晚上仍然吃炒鸡（ ### day 2 早上又想了想昨天的 T2，感觉好像是个数据就能让他假掉，于是又有 50 没了 话说这是第一次打有 day2 的比赛 去考场，发密码前打了个.....忘了 看题，T1一副可做的样子，准备先想，T2一副不可做的样子，准备25分暴力跑路，T3叫支配？ 支配树？ nm我光知道有这么个东西但是没学啊。。。 不过T3也一副可做的样子，猜了个结论觉得如果 $(u,v)$ 的边加入后 $v$ 的受支配集合发生变化那么所有 $v$ 不经过 $1$ 能到的点的集合都会变 然后就随便写了个 $O(n^2+nq)$ 的玩意，于是我60多行就过了省选 day2T3？ 显然是不可能的，脚后跟想都知道这个结论是假的 然后发现 $set_v=\operatorname{And}_{(u,v)} set_u$，那么再用 `bitset` 维护一下这个 $set$，就能 $O(n^2/w)$ 回答，于是就有了 $O(n^2+\frac{n^2q}{w})$ 做法，再随便水一下树的分就一共 75 了？ 那么这个 T3 是在送温暖？ ~~送nm温暖一堆细节错加上想和对拍的时间一共用了一个半小时~~ 另外这大样例真阴间，一堆错还能直接过 然后赶紧把 T2 暴力打了，这暴力也够难打的。。。 所以此时过去了两个半小时，就得了100分 还剩两个小时，还能切不了T1？ ~~事实证明真切不了~~ 想半天觉得这个 $P$ 中无重复数明显得用，于是如果一个点的权值在 $P$ 中出现过，那么从他开始（就是不一定非要从 $P_1$ 开始匹配）如何往后匹配就是确定的了 那么与处理一下这玩意就为线段树的 `pushup` 提供了基础 那再树剖一下搞到序列上不就能维护了？ ~~说的简单~~，还得单独维护树上往上走和往下走的匹配长度，好麻烦哦，搞不出怎么写 最后还剩四十分钟，弃了，沦为 $25$ 分暴力老哥 写完又想了想 T2，有个状压dp的想法，但复杂度算下来仍然只有 25 分/kk 看昨天写留言的老哥在玩3D建模 于是 $25+25+75=125$ 属实凄惨 出来听 qyc 说自己 T1 写了 4k 多，于是他两天切两题，属实神仙 晚上回家看别人游记才知道 day2T3 是支配树板题，要是当时多学点板子就好了。。。 然后突然想到 day2T3 的图有环，所以直接那样转移是对的吗。。。 看发代码了，于是去测了一下，结果 day1T2 挂了，虽然早就知道这题直接构造肯定是假的，于是只有 $70+25+20+25+25+75=240$ 了/kk 不过好在 day2T3 没假，模拟退火被卡飞 那这样来看人确实无了 CCF 数据给我造水点呀！！！ 教训： - 永远不要相信大样例 - 乱搞没前途，随机化没前途 - 多学科技 - 提高码力 - 构造能救你命(noip T3)，乱构造能把你送走(day1T2)