CSP2020-S 游记

# day 0 因为只休息一天，所以留校了，晚上在机房看了一堆东西，比如铃酱的全局平衡二叉树qwq 下午的时候教练发了一套初赛模拟题，第12题居然考EGF、贝尔数和第二类斯特林数。。。我似乎是整个机房里唯一会做的（（（ 晚上回寝室之后在玩真心话大冒险，让一个平时十分“猛男”的同学说了一下牢饭的某个梗（“喵内噶，多洗哒，喵内”），形象全无（（（ # day 1 进考场之后面基了一堆常春藤的dalao。 题都还行，阅读程序的第三题虽然看懂了，但是还是蒙了一些。。。 CCF牛逼，暴力配对字符串+开一个会CE的队列牛逼。 希望不会退役吧qaq # week 1 tuesday 讲分块。。。 一节简简单单的分块讲了一节课，还只做了LOJ数列分块的 1 和 4，服都服了。 ### upd:没有人身攻击的意思 # week 1 wednesday 考了一套自闭 TG 模拟赛，牛客的。 A题一看博弈论，赛后发现结论十分简单。。。赛时爆零 B题换根 DP，打了好久被毒瘤了，3个小时全在调这道题。。。最后发现是一个 trick，从上往下 DFS ，然后减去/加上该节点对子节点的贡献，变向枚举每个节点当根节点。 C题是图论，没看出来，爆零。 模拟赛rk21，全班倒数第一/cy # week 1 friday blw 昨天给我的题 CF1392F 在机房 AC 了，他说是“神仙结论题”，感觉也不咋样啊。。。 # week 1 saturday 上午自闭 PJ 模拟赛，爆零，原因：没加`freopen`/cy A 题 sb 结论题，B 题双指针随便维护，赛后重测蜜汁 RE。 C 题恶心计数 DP，没做。 D 题看上去像点分治，但是因为有位运算，所以跳了。 晚上 CF，和兔一个房间，打出来了 ABCF，加了 200rating。 A 题是 sb 题。 B 题找环用了 Tarjan，但是好像有更简单的做法，写了篇[题解](https://www.luogu.com.cn/blog/160839/solution-cf1428b)。 C 题是 sb 贪心。  CF 结束后，在 U 群被兔假了：  找到感觉了，以后多打 CF（ # week 2 tuesday 打了一场模拟赛，T1 二分用的`std::lower_bound`，莫名其妙全 WA，T2 和 T4 因为过于阴间所以没做，T3 DP 方程推错了 40pts，大草。 # week 2 wednesday 我恨我自己.jpg T1 不难是一道挺 sb 的 LCA，赛后测出来 60pts RE，T2 赛后大骂 sb 题，教练说：“你 A 了再说。” 赛后： 当场 AC，打了教练的脸，还跑了个全站 rk2（ ### upd:教练的题解说因为是随机生成的排列，所以单调栈每次暴力统计答案是 $ O(nlogn) $ 的，然而我搞了一个在线维护答案，所以就 $ O(n) $ 了（（（ T3，恨死自己了。 题面看上去很恶心，思考片刻后决定使用`DSU on tree`，虽然超纲了但是是对的嘛（ 于是调完了剩下的整场比赛。 赛后，教练发题解，发现 T3 正解就是`DSU on tree`，我打错了。。。 10 分钟后，整个二机房充满了我的`f**k`。 # week 2 friday 今天打了一下某著名套路题`CF666E`，全 WA # week 2 saturday 又考试了。。。 A 题是快速幂板子。 B 题是 智力大冲浪，本来想卡个 rank1 就写了一个 基数排序+并查集 优化，然后并查集合并错了，爆0。。。 C 题结论，不过结论背错了，20pts 滚粗。 D 题据说是某省省选原题，树形DP，因为把一个`>=`写成了`>`而暴毙。。。 ### upd:改后重测还是 WA，就是我 tcl，别管上面的。。。 看看其他人，好几个 200 和 300 的，自愧不如/kk 然后某群出现了[这样](https://www.luogu.com.cn/paste/2bzrcw32)的情况（（（ 唯一的好消息是`CF666E`过了。。。 # week 3 咕咕咕 # week 4 monday 没做啥，一直在刷一些很 sb 的 DP 题，希望能够在 11 月 7 日前做完[这个](https://www.luogu.com.cn/training/1323)题单 qaq # week 4 tuesday 模拟赛 rk1 210pts /cy/cy/cy 附张图：  A 的数据范围 $ 1 \leq n \leq 9 , 1 \leq m \leq 9 $，看似状压/搜索，实则打表（ 贴一下代码（ ```cpp #include<cstdio> int n,m; const int table[10][10]={ 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,1, 2, 3, 4, 5, 6, 7, 8, 9, 0,2, 2, 4, 4, 6, 6, 8, 8,10, 0,3, 4, 4, 6, 7, 8, 9,10,11, 0,4, 4, 6, 6, 8, 8,10,10,12, 0,5, 6, 7, 8, 8,10,11,11,13, 0,6, 6, 8, 8,10,10,12,12,14, 0,7, 8, 9,10,11,12,13,14,15, 0,8, 8,10,10,12,12,14,14,16, 0,9,10,11,12,13,14,15,16,17 }; signed main(){ scanf("%d%d",&n,&m); printf("%d",table[n][m]); } ``` B 题题面很像 `P2466` Sue 的小球，于是按照那道题的 DP 方法去做了。 结果都没对拍就 AC 了。。。 后来才知道那道题其实是 `P1220` 关路灯，顺手上了第一页（ C 题以前听 blw 讲过，似乎是某省省选原题，然而不会（ 据说是毒瘤构造 + LCA，然后没做（ 就输出了一个`NO`骗分，10pts 然后拿到了 rk1 /cy/cy/cy # week 4 wednesday 模拟赛 A 是道递推。。。 然后 C 居然是臭名昭著的卡 SPFA 的`P4768 [NOI2018]归程`。。。 打了好半天，最后出来一个 5pts TLE。。。 死循环了，我直接【数据删除】 # CSP-S A 题毒瘤！！！细节巨多，骗了 10pts 爬了/kk B 题细节可能会死，90pts 吧。。。 C 题不会，输出了样例走人（ 出来后和学长交流了一下，发现这个方法很多题都用过。。。 ### upd:这位学长是 15min 爆切 T3 的金钩神仙 [b2019dy](https://www.luogu.com.cn/user/78488)，让我们一起来%他吧！OrzOrzOrz 可能是因为题面让我认为是 DS 吧（ D 题骗了 20pts 滚粗。 不过赛前和 SH 聊了一下，CSP 是骗钱的，或许自己还有戏（ CCF 为什么不考 DP 呢？小编也很疑惑，可事实就是这样。 有什么想法可以在评论区和小编讨论哦。 ### upd:d s g 当 着 我 的 面 给 我 拍 了 一 张 照 片 ， 我 还 不 知 道 那 是 他 ### upd: ### It's beautiful day outside. ### OIers are getting zero,gods are AKing. ### On days like these CCF like you... ### S H O U L D B O R N I N G I N T H E H E L L # 第二天  看看同学，235pts，直接滚粗。 # week 5 thursday 周一的时候教练生成了民间数据，把全 CQ 的代码都测了一遍（ 我 125pts，全 CQ rk134。。。省二，爬了爬了/kk