省选前考试总结

2.28-3.6

本周进行了 \(4\) 场模拟赛（\(1\) 场是自己出题未参考），出现了非常多的失误，在距离省选不到一个月的情况下是非常不应该的，因此在此进行总结以吸取教训。

3.1

• T1：正常通过
• T2：猜到了答案与环长的 \(lcm/gcd\) 有关，但不会求所有环长的 \(gcd\)，是没有见过的套路，需要多多积累。
• T3：一道较为难写的数据结构题目，由于在T2上花费了太多时间没能写完，还是代码能力不够，并且开写的时候有点心急，许多细节没想清楚，写得一半发现又要再加一棵线段树。但及时止损拿到了大量部分分还是可以接受的。

3.4

• T1：一道构造题，想了一个贪心但证明证错了，误以为是正确的，实则还需要再对特殊情况是用另一种方法处理，还是没有想清楚。
• T2：较简单的数学题，但是因为自己的 \(SB\) ：本来开了 \(2000*2000\) 的数组，再加入多项式后多项式的数组要开到 \(8000\)，于是就将全局变量直接改成了 \(8000\)，于是开出了 \(8000*8000\) 的数组喜提 \(MLE\)。这一问题非常低级，以后在模拟赛/正式比赛考试交卷一定要腾出 \(5\) 分钟时间检查自己程序的空间、是否输出了调试信息、是否开了文件等等。
• T3：较难的字符串题目，没有想到关键转化，只能暴力跑路。

3.5

• T1：又是构造题，花费了很长时间在 T1 上想出了一个分数较高的构造，但因为非常自信，没有写 \(checker\)，自己看了看输出就觉得没问题，实际上写个 \(checker\) 就会发现输出的答案有一小部分是错误的。事实证明不要贪写 \(checker\)/对拍的时间，它其实不需要多少时间，却可能让分数提高许多。
• T2：没有及时意识到可以判断答案是否合法（主要原因还是 T1 花费时间过长），意识到之后写了暴力也花了不少时间，在考试策略上出了较大的问题。
• T3：正解极其难写，暴力跑路。

3.7-3.13

3.7

• T1：想到了多项式的思路，但没能够进一步做下去，对于多项式的线性递推、插值等技巧比较不熟练。最终还因为特殊情况判错掉了一些分，以后在交题前一定要检查自己的特判有没有写挂，会不会输出多余的数。
• T2：非常妙的贪心题，只想到一个假做法。还是没能抓住这题的关键性质，在思考的时候有些急躁，想了一个做法后没有仔细想证明就开写，写完了过不了拍，然后发现做法假掉了，浪费了不少时间，心态也被搞崩了。
• T3：一直到最后都没有看对题意，题面本身写得很奇怪，自己也没有想过去问出题人问清楚题意。

3.8

• T2：发现了关键性质，没有找到最后一步优化的关键。对于这种关于子集的问题，\(meet\ in\ middle\) 是一个非常常用的方法，一定要首先想到。
• T3：对于线性基等线性代数的技巧掌握得很不透彻，对于可撤销并查集等较深内容不太理解，对于高斯消元、方程解的判断等较基础内容不太熟练，本周重新总结了一番。

3.10

• T2：非常巧妙的数据结构题，抓住了重心的关键性质：子树大小严格大于总数的一半，而自己则完全被带偏想着分析修改对重心偏移的影响。由此看见待修改的数据结构题，可能是对 \(\mathcal O(n)\) 的静态问题出发，分析修改对答案的影响；也可能是静态问题就可以做到 \(poly\ log\) 的较优复杂度。

3.11

• T2：想到了 \(\mathcal O(n^3)\) 的 DP，没有想到由于最优解满足特殊性质可以直接干掉一维状态。事实上对于 DP 状态的优化，我几乎都着眼于转移过程中的优化，实际上抓住答案的性质进行优化也是一条可行之路。
• T3：再一次被自己带偏，误以为操作数非常多，只能分析答案的性质，一心想着从判断答案能否取到的方向出发，却没有想到暴力模拟过程。信息学竞赛中，走偏路是很正常的，但关键是要及时发现这条路走不通，然后赶紧换路，快速试错的能力是非常重要的，这需要自己对各种解题方向都了如指掌，并且在做题过程中保持清醒才行。

3.14-3.20

3.14

• T3：非常玄妙的树形 \(dp\) 方法，分别记录点 \(u\) 可选可不选时的答案，以及强制要求 \(u\) 被选对答案造成的变化。这一思路比较新奇，以前都没有想过。

3.15

• T3：想到了二分+点分治+主席树进行判断，但在超大的值域面前只会直接二分，没有想到还可以进行随机二分，利用值域很大但合法点只有 \(\mathcal O(n^2)\) 的性质，随机二分复杂度依然是正确的。

3.17

• T2：一开始找到了正确的估价函数，但是因为判断方法写错而误认为这一估价函数不优，自己去想复杂得多的奇怪的拟合后的值作为估价函数，把问题想复杂了。明明理论分析得挺好的，实现时却实现的与理论不匹配，反过来认为理论分析是错的，主要问题还是写题的时候没有注意细节，出现问题时也要保持冷静，仔细核对究竟是算法的错误还是实现的错误。
• T3：大数据结构题，由于在 T2 上花费时间太多而没时间写了。

3.18

• T3：想到了 \(\mathcal O(n^2)\) DP，但没有想到分治这一选项，直接规避了特殊的转移，进而用卷积实现转移。优化 DP 的方法有很多种，当出现特殊转移无法直接优化时，尤其是在特殊转移只发生正在某一维为 \(0\) 时，可以考虑分治直接规避这一转移。

3.19

• T2：较为复杂的数据结构题，最后因为将一处 \(x\) 打成 \(y\) 而失去 \(20\) 分。写了对拍程序但没有拍出这一小错误，解决方法也只有写题时仔细仔细再仔细，以及对拍刻意造一些两类数据差异较大，可以应对打反字母情况的数据。
• T3：考场上思考时间较少，实际上至少 \(m=1\) 时使用单调栈维护应该是比较容易想到的，但个人对此不太熟悉。接下来就是维护一个类似单调栈但维护的是前 \(m\) 大的数的结构，比较有启发性。