联合省选2022游寄

· · 个人记录

今年刚刚幼儿园学前班的我很荣幸的参加了联合省选。——题寄

从前的从前

一切的一切，得从去年的NOIP说起……

那天，我突然得知，我NOIP T2 数组访问越界，直接挂掉40分，T4 暴力也写挂，只剩下了可怜的224分，大概也就比大众分低了60-70分，还好，一定可以翻盘吧！

寄的从前

NOIP之后，我决定好好练习，争取省选翻盘。 在12月，我针对我的薄弱项——网络流，多项式等进行了补充；在1月，参加了WC，本来写了压位trie和交互的80分，结果交互数组又访问越界了（梅开二度），直接爆0，100分压线银牌（本来180+稳金）；2、3、4月一直训练加模拟赛，感觉水平有所提高，但是面对省选，联想到NOIP成绩，还是心虚不已。

寄的现在

DAY0

省选在育才中学举办，我就在谢家湾长大，四舍五入就是在我家省选,不过这并不能改变什么。来到育才中学试机，电脑很新，键盘也很好用，甚至还有虚拟机，给育才点赞！在现场写了一些模板，测了测读写效率，然后就离开了。回到家后头脑放空，复习了一下模板，然后早早地上床睡觉了。

DAY1

8：10进入考场，8：25下发密码，然后8：26我的电脑就卡死了……似乎开了个好头？

读完T1，发现是大模拟，感觉数据范围很小，直接模拟就可以了，直接map<string,string>莽！大概写了40分钟，过了样例直接下一题。

T2，一眼插值，考虑枚举一条链算答案，好像只会算第一问？复杂度O(n^5)?跳过！

T3，好多特殊性质，好像只有楼下可以费用流，写完之后发现好像有正权回路，而且好像复杂度奇高，只能放弃。写了个状压，再拿了B性质第一问的分，走人。

发现T1好像变得很长再缩短，map套string好像复杂度太高，改写了个哈希。

再回去看T2暴力，写了第一个数据点的大暴力，再写了个O(n^3k)的暴力，好像有17分？感觉这样下去一定寄飞了，去想那个k<=200000的怎么做，在12:00时发现不用枚举链，直接枚举最小值，整棵树的贡献就直接计算了,复杂度O(nk)?写完后 发现分段插值以下不就O(n^3)了吗？但是时间只剩下了不到半个小时，只能手速飞快地乱码一通，12：55刚好写完，也没时间调了，说不定是对的呢？

感觉今天T3是真的阴间，但是T2如果多一些时间我应该可以切掉，不过没有如果…………

期望得分：100+24~73+28=152~201

DAY2

感觉昨天发挥不好也不差，脑袋继续放空。

看到T1，质数，整除，值域2000？感觉很有寿司晚宴那味了，很可做。先把质数根号分治，然后大质数预处理，小质数容斥，大概1个小时过了样例，不过极限数据好像要跑1.2s,感觉要TLE，想了想可以把43归到大质数内，这样状态数减半，就只用跑0.6s了，写了个对拍，感觉很稳，然后看下一题。

一看T2，这不是WCT1吗？这是给人做的吗？分析了一下几个操作，感觉权值相等可以直接逆序对算出来，有分了！从括号树的角度来理解，最后是要合并成一条链，从每次合并两颗子树的角度来思考，分析了很久，发现好像y的贡献是固定的，x的贡献算不来，写了一个自认为很有道理的x=0的贪心，花费了超多时间。

还剩下一个小时看T3，先写了个裸的枚举排列，好像有12分！然后一直想多项式复杂度的dp，终于设出来了一个三方的状态 f[x][i][j]，表示x子树，x与父亲交换，出去的是d[i]，进来的是d[j]，然后可以讨论一个节点与父亲，左右儿子交换的顺序来转移，将转移列出来，刚好也是三方的，然后又是最后半个小时，狂敲键盘，在12：50过了拍。

期望得分：100+24？+44=168？

赛后

拿到D1T2代码，拍了一下，发现插值代码的分段讨论错了，果然在最后时间没检查还是不行呀。

D1T1好像没有问题。

结果发现D2T1好像题面没有保证质数不重复？我没去重呀！淦，WA飞。把去重加上就AC了。我们机房所有人都没去重，无一幸免。不过经过反复读题，感觉并没有讲清楚质数是否重复的问题，我们机房（包括教练）的所有人读题都认为不应该有重复，就看出题人是怎么理解的了。

最终得分应该很难上300了，省队应该没啥希望了，明年还有一年，加油吧！

upd:D1T2得分分布看错了，应该是38分；又看错了，是31分。

官方得分

100+31+28+100+0+44=303

D2T1没有重复！ 总的来说，只有D2T2挂分了，x=0的贪心是伪的，然后权值相同的求逆序对，我把左右括号写反了！

教练拿官方数据测了一下全CQ的成绩，但看省选成绩，我rk8，但是算标准分，离省队还真就差NOIP数组越界的那40分。

今年刚刚幼儿园学前班的我很荣幸的爆炸了。——后寄