NOIP/CSP-S 考前注意事项

实际操作与代码注意事项

基本内容

• 可以使用 #include <bits/stdc++.h>！！！从来都是可以的！！！不需要背诵一大串头文件，更不要从本地的库里去复制一大串头文件（有的头文件可能评测环境下没有）。

• 代码保存在哪，是否需要建文件夹之类的，以考场上的 README.pdf 为准。根据往年经验，江苏是不需要建子文件夹的，把四个 .cpp 文件放在根目录下即可。

• 用文件输入输出！！！具体来说就是：

freopen("problemname.in", "r", stdin);
freopen("problemname.out", "w", stdout);

​其中 problemname 是题面指定的文件名，每道题不一样。

• 测大样例时注意不要覆盖原本的 .ans 文件。可以把所有大样例提前复制一份，以防这种情况的发生。
• 不要用下划线开头的函数，如 __gcd 和 __builtin_popcount。自己定义的除外。
• 变量名避免完整的单词（hash, pipe, time, next），以及 x0, x1, y0, y1。如果要使用，可以简写（如 nxt），加前缀（如 mytime, _time），或者 \(\text{define}\) 掉（如 #define pipe guanzi）。
• 不要忘记删调试语句。
• for 循环两层循环尽量避免变量名重复。否则可能会出现奇怪的问题。
• 结构体里如果开数组（尤其是数组较大的时候），自己写一个空的构造函数。否则可能会出现奇怪的问题。
• 多测清空！！！！（请确认每一个 \(\text{subtask}\) 都清空了）。但是如果题目只保证了 \(\sum n\) 小于几，而没有保证数据组数，不要用 memset（否则可能复杂度变成 O(T * MAXN)，你就 \(\text{TLE}\) 了）。
• 对拍时一定要写 srand，不然可能就白拍了。
• 定时存一存代码。写新做法时，不要把原本的做法删了：可能有些部分还能用上，或者可以用来对拍，或者你新做法写不出来（或想错了）时，原来做法至少还能帮你拿到一些保底分。

算法相关

• 二分上下界都 \(\leq 2\times10^9\) 时，有可能 \(l+r\) 会爆 int。
• 线段树：
  • 空间要开 \(4\) 倍（但是千万不要写成 MAXN << 2 + 5）。
  • 莫忘 push_up 和 push_down。
  • 区间修改 / 查询时，应该是 if (ql <= mid)...; if (qr > mid)...;。不要把 if (qr > mid) 写成 else。
• 倍增（例如树上跳 \(\text{LCA}\)）时，因为 \(u\) 点本身在向前跳，所以如果之后的运算中，需要用到原本的 \(u\)，那么一定要提前复制一个替身变量。
• 与上一条类似。分解质因数时，被分解的数在不断被除。如果后面要用到原来的值，则要存一个替身变量。
• 分治中，分清 l 和 1。要 for(l~r)，千万不要写成 for(1~r)。我在写分治优化缺一背包时，犯过几次这个错误。
• 同一道题目里，有些量需要取模，而其它量不需要取模。一定要注意区分，千万不要看到乘法就取模。

其他状况

• 江苏省的电脑是 \(\text{windows}\) 系统，配了 \(\text{noi linux}\) 的虚拟机。我是只用 \(\text{windows}\) 的。初始时，你的虚拟机可能有两种状态：(1) 它自己就是一个小窗口，这是比较理想的状态，你直接把它最小化就可以了；(2) 另一种情况是虚拟机全屏了，此时你找不到 \(\text{windows}\)，千万不要慌，千万不要点右上角的退出（或关机）按钮（否则整个虚拟机就都没了，你收不到题目，也交不了代码）。正确做法是把鼠标移动到屏幕下方，会出现一个最小化的键，点这个键，就可以回到 \(\text{windows}\) 了，并且你的虚拟机也没有退，它变成了一个小窗口。

考场策略

比较主观，仅供参考。

• 先把所有题都看一遍。不要看到有的题面长 / 看起来向自己不会的算法就跳过。
• 不管简单题或难题，保证 \(20\) 分钟的有效思考。不要发呆，或者迷茫、抱怨、产生负面情绪，都是不好的。思考时，在草稿纸上写下每一个小思路。有时候思考的过程像是在图上搜索，如果一个分支想不通就回溯，换另一个分支。把这些分支都写下来，可以极大地帮助思考。NOIP / CSP-S 一定会有较多简单题（即使它们经过了伪装，不易被看出来），\(20\) 分钟左右的思考时间，就是要分析题目性质，拆掉所有这些伪装，发现核心的问题，然后套用我们学过的算法去解决它。
• 保持信心，猛刚正解。承接上一条的意思，因为题目不会太难，我尽可能往正解方向去想。去年我已经拿过一等奖了，所以今年光拿到一等奖对我没有意义，我要冲击高分，就必须猛刚正解（当然，这样有一定风险，最后暴力分都没拿到，连一等奖都没有。请没拿过一等奖的同学谨慎尝试）。我发现我在模拟赛时，常常自己陷入自闭，觉得好难的一道题，只要上 qq 听别人说了句“这题很简单”，往往一小会后就能想出来。说明我还是不够自信。考试时要多一些信心，确信题目不难，自己能想出正解。
• 时间分配上，前 \(30\) 分钟读题 + 思考 T1，前 \(50\) 分钟内一定要把 T1 做出来。然后 \(20+60\) 分钟想 + 做 T2。接下来 \(20+60\) 拿到 T3 高分（或满分？）。最后 \(20\sim 30\) 分钟把 T4 暴力打了。当然这只是一种理想情况，考场上要随机应变。但是务必保证至少做出 \(2\) 题。
• NOIP / CSP-S 中简单题（T1, T2）的代码，应该不会很长。写之前手玩一下样例，确保算法正确。先写比较核心的部分，再写比较板子的部分。例如：线段树这种又长又套路的东西，就放到最后写（以免写完后才发现做法假了）。
• 对拍。一定要对拍！！！\(60\) 分钟的代码时间里是留足了对拍时间的。不对拍就是在裸奔！！！不要只和暴力拍小数据，自己造几组大的极限数据测一下。
• 没事上个厕所，有助于放松心情。

思考题目的技巧/套路/有用的联想

OI 题目千变万化，思考方法也是很多很多。这里只列举一些比较重要的。

序列相关：

• 序列问题，考虑是否可以先将序列排个序。例如很多选子序列的题，其本质是选子集，那不妨先把原序列排个序；但如果是真的选子序列（要依赖原序列的顺序），那就不好排序了。
• 序列问题，遇事不决差分一下（或者对 \(01\) 序列做 \(\operatorname{xor}\) 前缀和），说不定有奇妙性质。（或者前缀和一下？）
• 普通序列变 \(01\) 序列。例如：对一个值 \(x\)，把序列中 \(> x\) 的置为 \(1\)，\(< x\) 的置为 \(0\)。
• 一类字典序最小/最大化问题可以转化为：按顺序枚举 + \(\text{check}\) 问题。
• 要求字典序小于/大于某个东西，考虑一段前缀都是相等的，第一个不同的位置在哪里？（数位 DP 常用到）。
• DP 技巧：把代价均摊到每次新加入的数产生的增量上（差分）
• 设计 DP 状态时，不一定要把序列里的位置固定死。可以只考虑已加入的元素的相对位置关系。或者考虑每次操作为插入一段东西（尤其是序列里只有“包含”或“并列”关系时）。

计数相关：

• 期望问题，有时每种方案出现的概率一样，那么此时 期望 = 总和 / 方案数，由此可以转化为求和问题。
• 求和问题，经常用到拆贡献的方法。即分别考虑每个元素对总和的贡献。
• 总方案数 - 不合法方案数（容斥的思想）。

数据结构相关：

• 考虑枚举一些什么：如枚举位置？枚举值？枚举答案？（能不能换成二分答案？）。枚举了一个东西，看能不能用数据结构快速维护出另一个东西。
• 从边界入手考虑问题，如：第一次操作会做什么？。有的构造题，我们可以从数据规模最小的情况出发，然后归纳地构造。
• 把问题离线，预处理一些东西？
• 如果有非常奥妙的操作，啥数据结构都维护不了，那试试分块吧。
• 删边的处理方法：(1) 分块。(2) 时光倒流（可能可以用 \(\text{kruskal}\) 重构树记录时光倒流的过程）。(3) 线段树分治（不常用）。

其他：

• 二进制，拆位考虑。有些问题可以按每一位是 \(0/1\) 分治。
• 给出一堆点对：在点对之间连边，尝试建图。
• 求 \(\gcd\) 为 \(x\) 的答案 \(\to\) 求 \(\gcd\) 为 \(x\) 的倍数的答案，然后容斥。
• 贪心配对：(1) 最大配最小。(2) 最大怼次大 / 最大怼所有。例如有些树上问题，可以确定一个根，然后让所有儿子配。
• 矩阵快速幂中间，多了一些奇怪的点：把两点之间的每一段分别拿出来做快速幂，可以预处理转移矩阵。复杂度 \(O(C^3\log n + mC^2\log n)\)，\(C\) 是矩阵大小，\(m\) 是奇怪点的数量。
• 抓住操作中，不变的东西（如总和的奇偶性不变？）
• 树上问题，直径 / 重心有没有妙妙的性质。
• 博弈题：二分答案（或者考虑二分答案，可以帮助你思考）。

最后，祝大家考出好成绩！