csp-s 游寄

· · 个人记录

14:30 - 18:30

14:24 发解压密码：belief2022，相信 noip 不挂分，相信 noip 能翻盘。

开场先看 T1 holiday，没啥思路。

思考十分钟无果后去看 T2，显然一个贪心，要维护区间最值，分类几种情况，果断线段树维护，1h 后过了 T2 的大样例。（可是没有进行自己手测样例，埋下伏笔。最后发现没有考虑到 b 横跨正负且 a 全正/负的情况。。。想当然的以为只用选 a 绝对值最小的情况即可。）100 -> [60,70]

继续想 T1，陷入一个怪圈，想到了枚举 B,C 并看满足条件的 A,D 点做到 n^2，但是一直无法处理两点间的距离，一直以为必须两点间最短路必须 floyd 做到 O(n^3)，没有想到做 n 次 dfs 即可。继续思考半小时多无果， 决定先写 70，大概两个半小时过了大样例。[70,85] 的部分分觉得一眼没想出来，看了看不多的时间，决定先看 T3,T4

想 T3，发现等价于询问是否每个点的出度均为 1，40pts 纯枚举送分，20min 写完，40-60pts 一眼没想出来，但肯定可做，具体要想想如何进行删边，可以构造一个边编号的映射，但细节还需思考，看了看只有 40min 了，决定先看 T4。

T4 52pts 好像是暴力 dfs，还有 k=1 送的 8pts ,但当时第一眼是个链上 dp，以为有 76，就直接写了，写完后发现 k=3 的情况是假的，只有 36pts，写完后还有 5min，就直接检查了检查文件直接放弃。

最后预估得分 70+[60-70]+40+[36-40] = [204,220]

觉得实现完全没有跟上思维。思维也陷入的思维定式想当然以为什么两两最短路最快 n^3 的荒诞思路，并且还少分类了。

首先一些简单送的暴力分并没有拿全，即便 T1 只写了 70，但是 70-85 的 15 分应该是极为简单的，还有 T3 的 40-60 的 20 分，还有 T4 的 52分，和 k=1 的 8 分。这些都和时间分配还有实现速度有关系。最后都是简单的暴力分没时间写了。

导致他的原因呢，策略方面做的其实还可，T1 放弃了 100 迅速 rush 了 70 分并且开 T3T4，多拿了 40-80 分。

但是实现速度上还需要继续加强，比如说 T2 的线段树，写了40-50min，其实可以更快。像简单题的实现，比如裸的两点间距离，T1 的 15分，T3 的20分，T4的爆搜，都不应该放弃，也不应该有思考的时间，应该做到10-20分钟全部打完。而在考场上，其实害怕想不出来耽误后面的题，就直接放弃了送的分。

所以第一，简单题的思路和实现，基础代码能力应该提高。

第二，不要相信大样例，自己写对拍或手测，分类的时候一定慎重想好。

T2 本来想自己造两组，一看大样例 20w 组询问都没错就放弃了。事实上民间数据甚至还过了 70分，但其实卡到 0 都不过分。分类少种情况！敲代码前应该都想好再做，写完也应该自己手测各种情况进行调试。

T3 以为一定走链，k = 3的时候假了，如果事先想好我就会先 52pts 的暴力而不去写把链拿出来的 dp 了，最后只能遗憾比爆搜还少得 16 分。

第三，不要陷入思维定式，以为两两最短路就是 n^3，多么愚蠢。自己的潜意识一定要进行再思考，看看对于这道题来说有没有更好地办法，或者说对于一种特例，它的复杂度就是假的。

改进措施：

  1. 追求代码速度，大量写代码，限时进行刷题。
  2. 每次思考结束后再写程序，争取平时做题提交一次 AC
  3. 进行大量基础程序训练，从而积累自信，考场上心态不要畏手畏脚不敢写，害怕时间不够。暴力程序可以快速打出。
  4. 建立错题本，以前犯过的问题不要再犯

排除那些原本就不会的和思维并未想到的。如果发挥到最好，改正了上面说的所有问题，应该得到： 100+100+60+76=324 的分数。

希望 noip 不挂分吧。