2021省选游记

· · 个人记录

NOIP

本来没抱什么希望，结果考的还可以（虽然前

## 寒假 年前学莫反，推式子推得头疼，年后调分治又调的头疼。。。听到了本校和hzoi大佬的课 期间打了第一场[CF](https://codeforces.com/contest/1480/standings/participant/109448503#p109448503) 开始在 acwing 上刷蓝书的搜索题 ## 开学 颓废了一寒假，月考排名翻了 8 倍（36->330+） ### 3.21 周练时ycx来告我要停课，晚上成功请到了假。开始被巨佬吊打 [模拟赛](https://www.cnblogs.com/9Rings/p/14742083.html) ### ... CF打到了1441，没想到之后再没打过CF ### ... 得知考联合省选B卷，没什么感受。开始找一些省选的水题做。ycx发现去年D1T2考了点分树板子，一起嘲笑了ta，结果想起来自己对点分树的印象只有曾经学过。。。 后来某天得知在本校考，终于不用去阴间考场用阴间笔记本了 ### 3.31 感冒。。。荒废了两天 ### 4.7 请了周四周五的假，十分的慌。学校周五春游，血亏。。。 ### 4.8 上午复习了一些数论，下午调过了一道被卡常网络流，胡乱写了些DP 春游推迟了一周，nice 下午dky来了（好像刚考完一模），对话： ``` for(;;） ｛ I: %%% dky: fAKe ｝ ``` ### 4.9 上午搞完了数学，补完了最短路和最小生成树的一些题。学习了模拟退火 下午英语节，没去。 虽然就在本校，还是去试了一下机 晚上打了一堆板子，但没有写数据结构，想着省选时间比较长就没有写，大概看了看。晚上最后一题写了一道**序列上的模拟退火** ，在校没调出来，回家才A。背了头文件和gedit配置。收拾东西时发现没口香糖了，大艹。睡前十分紧张，不过12点前还是睡着了 ## Day 1 早早到了考场，和巨佬们聊了一会。听说有人进了考场又被赶出来了。 8点多进场，调了配置、打了头文件，结果gedit的外部工具一直不对，最后发现DOCUMENT->DOCMUENT。。。好在最后发现了，大概8.25拍上了快读和cin，等发题。原来以为楼里有厕所，只是不给开，今天才知道竟然没有，于是上厕所还得下楼，差评。不发面包差评 T1一眼排序，枚举倍数（第二档分的提示挺明显的），时间复杂度 $O(n\ln a)$，感觉非常稳。就改变策略先把T1过了，8.50和 $O(n^2)$ 暴力拍上后突然意识到可能 $a_i$ 都相同且很小，调和级数的 $\sum_{i=1}^n\frac ni\approx n\ln n$ 就假了。上了个厕所后想到可以把 $a_i$ 去重，这样如果有多个相同去重后的 $n$ 就小，都不同就可以调和级数，最终复杂度 $O(n\ln a)$，本机极限数据跑得很稳。9.10拍上就不管了 T2第一眼：退火。。。但按照去年的情况，T2就退火绝对要完。不难想到每次翻的一定是两个最值，考虑贪心，但一直在尝试分类讨论+权值线段树，最后没想好细节。边打暴力边想DP，发现显然不能做，最后还是退火了。一开始直接随机位置，样例2都过不去，改写成每次翻两个最值的位置并 $O(n)$ 更新最值，对拍一下就炸了，调小规模后发现我的写法在 $m$ 次都翻了且两个最值都是没翻过的时会死循环，于是随机时加上上次翻的位置，调半小时参后能稳过样例2，但样例3一遍都跑不完，感觉可以用权值线段树加速，但没有写。 T3一开始看错题（路径->边），Floyed传递闭包后小样例都过不去。重新看题后直接 $O(n^2m^2)$，写完还早，一顿卡常+玄学剪枝，大样例跑4s。 大概12点停止得分，随便检查了一会，交卷前T1多开了一个LL，发现退火概率接受不优的当前解时大于号写反了，当时大脑一片空白，~~仔细思考后~~还是改了。 出考场巨佬hhy说T2贪心：翻的一定是前面一段+后面一段，也听到有人说可以枚举最小值，二分最大值，emmm...总之我是死了。ycxT2也写了退火，ys $O(m^2)$ 贪心暴踩我40pts。下午本来想再写写板子，结果第一次体会到水群的快乐，几乎一直在颓废。突然想起蓝书上的搜索还差一个**IDA\***，就写了第一道。晚上写了一道交互、一道构造就睡了。 ## Day 2 早期收拾东西没找到身份证和准考证，貌似在学校机房，就直接走了。结果不在？？？赶紧给父母打电话，最后还是在家找到，及时送到学校了（感谢父母）。倒数第二个进场，赶在发卷前写完了头文件，只是心态没有调整好。开考前老师说昨天上厕所的人太多，今天要少去，一定有我的贡献（Day1貌似去了5次）。 一看T1又准备~~退火~~暴力。想起以前做过一道类似的题：求 $a_i\mod a_j$ 的次大值。好像是排序后 $O(1)$ 算，于是想到这个题也应该排序，枚举模数，然后就卡住了。T2没有任何想法，按照模拟赛的经验链上的分应该比较好搞。T3想了一会状压DP，后来发现按 $n$ 的大小分了很多档，盲猜正解是dfs+剪枝。 回头先写了T1暴力，发现对于降序排列的 $a$，当前模数为 $a_k$，那么如果 $a_i+a_j>a_k$，那一定是 $i=k+1,j=k+2$（因为 $a_i+a_j\in[0,2a_k]$，而 $a_{k+1},a_{k+2}$ 是最大的）；如果 $a_i+a_j<a_k$，就可以双指针扫一遍，时间 $O(n^2)$。写完拍上就去看T2了。T2仍旧没有思路，写暴力是突然想起T1有可能 $i<k 或 j<k$，那就死了。回去加上后时间变成了 $O(n^2\log n)$（枚举模数后把剩下的先模再排序），感觉不太稳。对拍时发现这种情况好像不可能，但又不会证（最后拍了1.5h后还是删了）。同时看到由于数据随机，答案的 $k$ 很小，因此我的剪枝很快就剪掉了，更进一步，考虑多个相同的数只有两个有用，可以手动去重，想了想不知道怎么卡。此时已经快10.30了，就去写了T3的dfs，估价函数为把剩余队都变成当前队的最小 $b$ 之和，时间大概是 $O(n\cdot ans)$。和 $O(n\cdot n!)$ 暴力拍上后发现还没暴力跑得快。。。估计和数据有关。 $n=11$ 时有可能跑过去，但没有这档分，估价函数已经不会改了，于是想算一下让剩下队合法的最大 $b$ 之和，如果这可以接受就直接加上剩余队数的阶乘，感觉要DP，可惜不会。此时T2还有链上的分，就放弃T3了。链上像是个莫队，但并没有想出来怎么维护前缀（看别人游记说可以用线段树维护，因为题目保证 $P_i$ 互不相同，但 $O(n^{\frac 32}\log n)$ 也不太能过），最后写了个子序列自动机，但随便卡卡就到 $O(qc\log n)$ 了，还不如暴力。于是尝试排序后利用上次的信息，样例水的要死，随便写都过了，但过不了对拍。最后剩20min时放弃。惯例重新编译+测样例后还有10min 最后闲得没事胡乱看了看代码，越看T1的双指针越觉得不对。当时大脑一片空白，已经忘了写T1时的思路（甚至没想起来看看草稿纸），虽然对拍了2h都没错，但非常怀疑是因为随机数据水了，临交卷前下定决心加了个 `j=m`，把 $O(n^2)$ 搞成了 $O(n^3)$，赛后又觉得 $i<k 或 j<k$ 有可能，于是70pts->20pts，心态炸裂 考完大佬说T2树剖/倍增维护向上，二分向下可以 $O(n\log^2n)$，ycx写了链上的倍增，暴踩我20pts 下午学校还有周练，果断翘掉去快乐的打游戏，某一时刻想起了自己T1的双指针为什么是对的，于是1min抵消了前面1h的努力。。。 ## 赛后 ### 估分 100+30（退火应该有10pts）+16+30（都不知道有没有）+25+60=261 Day2直接爆炸 ### 4.12 回去上whk，早晨一见班主任就被问考得怎么样。。。gg 发现自己的whk啥都听不懂 开始颓废写游记 ### 4.13 机房集体翘课去打球 讲了扩展欧拉定理的证明 ~~感觉并没有什么用~~ 发现D1T2一车人A了，一车人80pts。教练说今天要出分，然而并没有。 ### 4.14 生物课睡觉被抓+物理~~血案~~学案全错 洛谷民间的民间数据：100+40+20+80+45+65=350。~~数据好水~~ D1T1退火过了两个点，D2T1如果不改就A了，还有一些勉强卡过去的点 ### 4.15 中午在宿舍ycx告我差1分进队 下午在操场上躺着看初中生足球联赛，有一队40min被灌了3个球，前锋直接被换下跑圈去了 最终100+20+16+10+25+60=231，D2T1但凡写个 $O(n^3)$ 暴力就进队了 ## 总结 我是傻逼 有心情再写吧