[游记] NOIP 2021 游记
2021-11-19 Day -1
18号从教练那得到通知说天大因为防疫问题不能举办 NOIP , 如果找不到地点举办可能就取消了...
明天就是 NOIP 了, 回想起 csp-s 的 " 好 " 成绩, 不禁害怕起来, 何况本来心情就乱七八糟的.
中午班主任换了位置, 和我关系很好的同桌和前桌分开了, 难受.
下午上完第二节课就请了假, 拿到手机后看到 NOIP 考点由天大变成了在郊区的英华国际学校, 估计得很早起床吧. 回家打了俩小时游戏. 最近一直过得很颓废, 期中考试更是一塌糊涂, 不像是智力正常的人考得出来的分数. 晚上随便看了点动态规划和图论便带着乱哄哄的心情睡觉了.
2021-11-20 Day 0
因为开车到考点要一个小时多, 6:10 就起床了. 在车上晃晃悠悠就过去了. 虽然最近一直睡的很少, 昨晚也就睡了 6 小时左右, 但却不怎么困.
到考点跟 csp-s 一样, 调完机器后先打了一个链式前向星和并查集 (我也不知道为什么我要打并查集) , 而且一样并没有用上.
有点紧张
T1
看到T1第一反应是打表. 花不少时间然后才暴力打了个表, 写到一半暴力不知道为什么调不对, 想起来埃氏筛, 然后又改成了埃氏筛. 我最开始还是输出的下一个不能输出的数字, 打完表才发现不能输出的数字比能输出的多(
看着若干 MB 的 .out 文件突然意识到, 是不是源代码有多少kb的要求来着...
然后看了两遍卷子, 都没有找到 100kb 要求, 因为监考员的话不可信所以没问, 我决定再想想别的办法(
(还好我曾经看到过这个要求, 不然我现在得担心半天我的T1代码超过大小要求会不会给分)
我除了埃氏筛和打表以外想不到别的做法, 但是用埃氏筛打表的程序却用时超过了 1s , 不能用来预处理. 我又思索了一会怎么办, 直到我注释掉了 printf 然后发现用时不到 400ms...
然后我就把数组的 bool 换成了 int , 用 -1 表示需要跳过这个数 (原来是用的 true ) , 然后直接 在处理到下一个可以报出的数字时把数组中上一个的值设为这个数字, 即:
if(table[i] != -1) {
table[pre] = i;
pre = i;
}
考场4个样例都过了, 感谢良心CCF的样例4, 不然我肯定忘了处理1e7+1
后来仔细一想, 我写的应该不会比埃氏筛 \(O(n\log\log n)\) 的时间复杂度差太多, 1e7 的数据显然很稳 (
用了不到一个半小时才写完T1, 我菜死了
T2
吸取了 csp-s 的经验, 等T1打表 (这时候还没写埃氏筛, 而且还写错了, 打的很慢) 的时候把 T2 T3 一起看了, 然后并没有什么卵用
T2照样没思路, 考虑了是不是DP, 但是发现我不会
于是决定按照样例1说明里的思路爆搜. 按递增顺序枚举 $ a_i $, 然后判断满不满足条件, 求组合数再乘以贡献, 最后加起来. 这堆代码调了好久, 调这题调了两个小时, 中间实现过程改来改去的, 看这堆乱七八糟的东西把我看吐了 (
玄学复杂度, 不知道怎么分析(
没想出来该怎么剪枝, 感觉会 TLE
T3
做T2之前先试着推了推贪心式子, 结果失败了 (
做完T2再看T3的时候只有半小时收卷了, 先研究了一下怎么求 $ D\times n^2 $ , 反正我大概就是把 \(n^2\) 乘进去然后再乘一个 $ n $ , 变成这样: (其中sum为所有数的和)
\[\frac{\sum_{i-1}^{n}(n\cdot a_i-sum)^2}{n} \]然后就只有几分钟交卷, 没时间写爆搜了, 干脆自暴自弃枚举不替换和所有只换一次的情况取一个最小值, 估计拿不到几分(
T4
扫了一眼感觉好复杂, 而且还是T4 就直接放弃了, 所以根本没写(
赛后
考试时一点也不困, 考后还有回家路上也不困, 一到家就困了(?), 而且因为其他事情心情还是一如既往的差, 于是打开电脑开始玩 osu! mania
洛谷民间数据 $ 100+30+0+0=130pts $, 人没了(
T2只有 \(n=5\) 和 \(n=8\) 的测试点拿到了分,剩下的全都 TLE , 开 \(O2\) 也一样. 本来考后以为T2能拿 50pts , 看来是我太乐观了, 不过我也没认真思考过数据范围, 这 50pts 是瞎估的, 不准很正常.
没想到T3竟然在洛谷连4分都没拿到, 希望CCF数据水一点(x)
不过在另外一个民间数据拿到了 4pts
看网上感觉大家都觉得T1很水(虽说埃氏筛确实是很基础的东西), 大家都200+, wsl
估分最高 134pts , 无缘1=, 我菜死了(
通过这两次考试我发现我每次都会在T2写暴力浪费大量时间还没拿到多少分(
而且两次T2都是动态规划, 果然动态规划一生之敌
果然是因为学的时间比较短, 也没有停课, 写的代码太少了吗(?)
听说T3的操作相当于差分数组中交换两个数, 好神奇, 感觉整个人都升华了(?)
然而听说了之后还是不知道怎么做