联合省选2021游记

这回不是 Never gonna give you up 了（ ## Day -1919810 省选集训测试 day1 T1 提交前最后 2min 调出来，T3 莽一个第一档暴力，130 分还在队线上/jy fyk 出的分块被带 $\log$ 的东西乱搞，fyk 表示再也不出分块了（ ## Day -114514 省选集训测试day2 $4$ 维数点 cdq 要拆一大车点不会写，记得还有 `bitset` 写的但是不会？ $3$ 个大暴力，$80$ 分，竟然还tm在线上/jy Cirno_9 NOIP爆炸但是按照省选集训的成绩翻了好几个人了，膜拜 有了点信心，但是也很慌，像 d1 那种提交前 2min 调试完的不可能在考场上搞的，还是和ZJ联考，暴力分肯定没那么好拿QAQ ## Day -4 你谷省选计划群 kkk沧桑的说了一句: 想不到省选计划会结束的无声无息 当时啥也没意识到 直到晚上才发现省选计划最后一场模拟赛已经结束了 省选也迫近了啊，回想第一天省选计划做DS的时候调了一下午的题目，有点小慌张，感觉自己并没有提升什么，反而觉得水平相对联赛时还变垃圾了，CF打死都上不了紫，奇奇怪怪的。 ## Day -3 摸鱼被班主任背刺了 叫出去训了一顿。 鱼是不敢摸了，偶尔水下群，复习了可并堆和DP，做了 NaVi_Awson 学长巨大强的博客里面给的一堆题目。 还是好慌QAQ EA也说他慌，但是他这个NOIp省选不是有分就能进？？ ## Day -1 还在考试，不很想考，开卷子发现竟然都是原题/jk 光速码完第一题 第二题是个数学题，我记得有个很短的结论，但是不记得具体是啥，很自闭，于是对着样例乱搞发现过大样例了/cy 开第三题，高维空间游走，只会暴力，爬了。 ~~然后就玩了一个小时的蜘蛛纸牌，两副牌真的打不过啊，发牌机暗算我~~ ## Day 0 动身去WH了，机房面摇神，stO Orz 走之前老师给我们看了高一退役的一群同班同学送来的加油，瞬间感觉 cnm，燃起来了，鲨鲨鲨！ 但是不是很喜欢坐汽车，昏昏欲 熬到了酒店，进去放东西，Garlic 命令和摇神一起吃饭，只能把 NaVi_Awson 学长的饭约推掉了 晚上回来和HB群群友一起颓 generals，说复习了什么那真的是复习了寂寞，要睡觉了发了个说说就跑路了，倒也是没啥压力，毕竟面对的可能是ZJOI，直接 $3$ 暴力走人可能是最优的选择？ ## Day 1 被生物钟叫醒了，想着今天 Day1 就直接起来了，洗漱上厕所然后烧了壶水，泡了一杯先辈红茶，希望先辈保佑我（ 等着 Ezreal 慢慢整完，出门下 17 楼简单吃了个早饭就出发了。 等电梯的时候 Ez 在看QQ，好像fyk昨天晚上还在发说说搞心态/baojin，就瞄到了一句 “如果你猜不到T1的结论怎么办” 还是熟悉的路，熟悉的华科南门，不过这应该是我最后一次作为在役选手来华科考试了，不由得有点感伤/ll 进门，考场门口有几个人，眼睛瞎了一个准考证都没看清，由于脸盲已经忘记NOIp面过的fz啥样，指着 zzy 对 Ezreal 说“这么小应该是fz” 进考场，有点好奇座位周围都是什么神仙，一看右边，Cirno_9！看来中午约的饭能找到人了，Cirno_9 来看了下座位然后对着我 会♂心♂一♂笑 前面是 Periiya，还是第一次见到女OIer啊qwq，有种要被吊打的感觉（实际上在NOIO就被倍杀了） Ezreal坐在神仙阵中，膜拜 Ezreal 想着要适应下考场键盘啥的，想着写个啥好，那就SA吧！ ~~写一半发现自己忘记了要是考SA我岂不是要完蛋~~ 那就NTT吧！ ~~写完还没检查完是不是对的就发密码了要是考多项式我岂不是又要完~~ 开题看题，先看了看三个题，似乎 T1 偏简单，T2 像个构造，T3 不会，就开T1吧 T1给了个 $\{a\}$ 有序，又把正解的复杂度分了好几档，看来是让我线性？但是这 $10^6$ 真的能卡掉 $\log$ 吗？？也许 $\log$ 能被卡常，我觉得线性应该没问题 分析了好久，写了个假的稀巴烂的代码过不了样例，然后fyk说说里的“如果你猜不到T1的结论怎么办”又出现在脑子里，差点爆炸 然后胡改了一下，觉得翻牌只能翻前缀和后缀，用 `set` 维护最大和最小，枚举前后缀删掉的长度，写出来一个 $O(m^2\log n)$ 的东西，好像有 $60$，略略安了点心，因为这里完全没有利用啥性质。 然后分析最大最小值的性质，觉得好像有单调性，在纸上画了一万个图整明白了，写出来个 $O(n+m)$ 的东西，调了一万年终于过了所有样例，感觉非常厉害,但是也意识到这题强数据很难造，必须对拍，此时已经11点了。 小数据的Gen很好写，让他拍着，看后面的，T2大构造不好搞，但是 $m=2$ 的似乎很好写，直接枚举一行的和然后 check 其他行，整了一会自己造了几个数据，算了一下时间好像过不了，然后就选择枚举最小的一行，并且枚举从两头进行 check，虽然有点慌，但是自己造了几个都没怎么卡，就想 $b_{i,j}=0/1$ 怎么搞，看起来像个 $2-SAT$ 但是不是很 $2-SAT$ ，就丢了，还有一档 $n,m\le 3$ ，发现 $n=2$ 和 $m=2$ 本质没啥区别，写了个转置想 $3\times 3$ 怎么写，好像不好搞，看时间好像不咋够了，先去把T3大暴力写了，然后把文件都放好，使劲搞 $3\times 3$，没想到什么正确的构造/ll，最后只好把 $4$ 个数字放在 $4$ 个角尝试混分，哪怕是一个点也行啊/ll 结束了，交完代码之后和 Cirno_9 交流，我预测是 $100+30+16$，Cirno_9 说他有170+，很害怕，pyy 转过来问我写了多少，我说 $146$，pyy 说写的和我差不多，但是我感觉今天这场估计被hsy鲨完了 出去问 Ez 和 Fz，Fz说他T1是个 $2^n$ 大暴力/jk，Ez 预测也有 $170$/ll，今天也是低于队线的一天/ll 出门在毛主席像下看到了EA，不敢确定，问了下 Fz，果然是无上永恒亚历山大/bx/bx 但是EA只是简单的打了招呼，好像很不开心的样子，走的时候还听到EA说了一句“没想到我会栽在这里”，有点害怕QAQ 和 Fz Ez Cirno_9 一起吃饭，找了个人少的麦当劳吃到快 $4$ 点，并且用皇帝的新手机和他们玩的很开心 下午群里 EA 问 C 多少钱，我tm直接害怕成沙雕？？？！！ 回酒店果断开B站看三国演义，不管那么多，放松就完事了 晚上睡觉之前有点担心EA，因为听说他确实爆炸了，而且从中午问 C 之后就没看到说话，很害怕，强行给 EA QQ云加油了一波，睡觉了 ## Day2 起的晚了点，一样的程序到华科，座位表变的很随意，感觉就是列之间 `shuffle` 了一下，一列内 `shift` 了几下，我前面还是 pyy，但是其他人不咋认识。 写了个NTT，一次写对了，感觉还行，但是听到有个人敲键盘声音非常巨大，很烦QAQ 发密码看题，昨天奶的树题不在压轴位奶到了，于是直接开，想了15min左右整出来了个做法，看起来是个 2log 的，于是开始码，码量也不小，不过树剖写的比较多也觉得没啥，大概在1.5h左右过了所有样例，我觉得这题样例应该比较强就没有想着对拍，不过这个大样例要 2.5s 是啥啊，有点怕，2log不可能这么慢啊，一看，二分里面放了个链树剖+线段树，这不是 3log 吗？？ 于是研究了很久怎么降log，但是真的想不到啥好的东西了，然后加了个输出优化，发现跑到了 1.3s ？？？原来这硬盘这么慢吗，还是怕被卡，看了下暴力，发现在链上这个算法是 2log 的，那就不管了，$70$ 分保底呗。 看T2，好像是计数，但是范围很小，因为读错题写了个 $O(nm^2n!)$ 的玩意，过不了样例，然后发现读错题，魔改之后过样例，用贪心把复杂度降到了 $O(n\times n!)$ 有 $60$ 分了，很舒服，然后小研究了一下怎么状压之类的，好像不很简单，爬了。 看 T3，支配？不会是啥支配树之类的吧草，不会啊QAQ 但是lyd书上提到过DAG的支配点求法，不过这个不是DAG，于是我研究了一小会缩点之后怎么搞，没搞出来。 暴力 $n,m\le 10$ 直接爆搜就能行，还有个树分，整了好几个终于写出来了，测了一下 $n=7$ 的树，没啥问题，最后就一直在检查文件检查数组尝试降掉T1的log，都失败了 出场听 Cirno_9 说他整了个暴力的支配树，搞得好的话这场有 $260$ 分/jy/jy 又被狂暴吊打了QAQ Ez说他考得不好，中午本来有更大一车人一起去吃饭，但是酒店要退房了，我和Ez就把东西带走吃了。 晚上来机房颓废，看到有民间数据了就测了下，发现 d2t3 树部分数组开小爆炸了，$-15$ 很难受，是 $100+30+20+100+60+10=320$。 Ez好像惨一点，d1t1被卡了20分，d2t1写的暴力还挂掉了链，少一点 EA又在群里提到了C，我真的不相信这么巨大强的选手连队都没有 不过晚上EA理我了，他好像心情很差很差，聊了会然后他也去测了民间数据   ~~好了好了我知道我省选710分了谢谢EA~~ 《C 多 少 钱》 结束了，不过接下来有理由颓废了qwq ## Day3 上午从kkk手上拿到了民间数据，用lemon测了下全省，半路发现matrix的spj挂了，于是整到中午才开始评测 下午没睡午觉就来了，想看结果~~并且借机颓废~~，得出的结论是EA队长，似乎我和Ez都在线上，挺好，继续颓废 ## Day4 继续颓废&吹水 ## Day5 等了一天的成绩并且骂半天的CCF ## Day6 出成绩了，进队了，比预计还要高一点（ $100+50+16+100+60+10$ 据说d1t1数据巨大水，各种歪比巴伯都能过 d1t2我那个尝试混分的乱搞把那个20分混到了/jk 加权之后B队rk2，pyy省选爆炸了，但是0.2分极限反杀另外一个妹子 ustze省选标准分/bx/bx 晚上听说d2t1链数据边的 $u,v$ 反了，如果出题人用脚重造数据的话 pyy 可能被翻掉？？！ 出了，没变化，pyy 半分优势/bx $\LARGE\texttt{我们 NOI2021 见!}$