NOIP2020游记

· · 个人记录

读题

T1：一眼看出简单拓扑排序，只是分数计算稍微麻烦

T2：意料之外的字符串题，没什么思路

其实看到T2是道字符串，还没什么思路的时候，我就有种不祥的预感

T3：一看以为是道交互题，结果是一道神奇构造，依然没思路

T4：完全没思路的神仙题

做题顺序：顺序开题

T1 water

题意就是直接拓扑排序模拟即可

加上分数的计算，30min过大样例

想着开了long long，出题人都保证了度数和路径长度这些，况且作为一道T1爆long\ long未免太毒瘤，应该没问题，就走了

没想到真就这么毒瘤

反思一下数据的最大可能值：

考场出来：要写高精？高精GCD？ 期望得分：100pts 民间数据：90pts 实际得分：60pts（声讨造数据人~~NMSL~~） 用时：35min 再反思：一定要算清楚最大的可能答案（julian 的long long，zoo的$2^{64}$，这次爆挂40pts） # T2 string 先写了一个KMP板子 第一个48pts $O(n^2)$思路： 枚举C，再枚举A，判断一下$F(A)$是否$\le F(C)$。再找出$S-C$的最小循环节，和$S-C$最大循环次数，这样A的贡献就是 循环次数的因数中 大小大于$|A|$的因数的个数 然后优化一下得到第二个68pts？的$O(n\sqrt n)$做法： 枚举C，找出$S-C$的最小循环节，和$S-C$最大循环次数，枚举循环次数的因数，找到长度小于 因数$\times$循环节长度，且$F(A)\le F(C)$的$A$的数目即可 找到长度小于 因数$\times$循环节长度，且$F(A)\le F(C)$的$A$的数目用一个二维前缀和即可（但是我考场上偏偏脑抽要用二维树状数组多两个$log$？） 然后我就写完走了 其实可以再优化：枚举因数其实是可以调和级数$O(n\log n)$的 期望得分：56~68pts 民间数据：84pts 实际得分：84pts 用时：2h # T3 ball 随便瞎写了一个模拟思路乱模拟了一遍，然后各种细节没考虑到调了好久 但是不会用checker，试了好久 过了小样例就走人了 最后时刻检查手造了一组小数据发现了郭，所幸很快调了出来，但是没啥时间了就没有再造数据手模（鬼知道是不是的，天知道能拿多少分？） 期望得分：0~50pts 民间数据：0pts 实际得分：25pts 用时：1h # T4 walk 只剩一个小时了…… 打个暴力走人吧 本来还想在裸暴力的基础上算一下能走完整的几轮，最后一轮再一步一步跳，但是写挂了…… 然后我的-1还判断的有问题 期望得分：30pts 民间数据：30pts 实际得分：25pts 用时：40min # 最后的挣扎 放到虚拟机下编译了一波 然后T1 T3手造了几组小数据手算了一下，发现了T3有锅，赶紧补了 然后T2两个代码拍了一下，没啥问题 最后加上freopen，检查了好几遍 # 总分 期望得分：200pts 实际得分：194pts # 总结 计算极限数据是必须的 其实做到T2就有点急了，可能上个厕所冷静一下会好一点？ T2优化需要一步一步耐心慢慢来，已经接近高分写法但是就差一点就很难受 T2做的时间稍微长了点，没有给T3T4留出应有的思考时间 # 计划 还是要以不会的知识点的学习为主 ### DP 斜率优化、状压、数位DP均需要加强练习 决策单调性优化动态规划可以学习一下 ### 字符串 扩展KMP、AC自动机、回文自动机 之后可以简单了解一下 ### 数学 这里要补的知识点就很多了 多项式、高次同余方程、exCRT、01分数规划…… ### 数据结构 树套树、LCT、李超树 可以学一学 ### 图论 网络流建模需要多练题多见题 点分治、虚树、矩阵树定理 可以之后一点学 ### 计算几何 之后再了解 ### 其他东西 模拟退火等