CSP-S2021爆炸记
蒟蒻第一次参加CSP-S，不必说，自然是炸了，机房还有 $A$ 了第一二题的巨佬 @mydcwfy，便更让蒟蒻瑟瑟发抖。
此刻，夜色已深，机房里的取得好成绩的巨佬们正在玩 generals，只留下蒟蒻一个人在默默地写下这篇记录蒟蒻在 $CSP-S2021$ 赛场上自闭的游记。
$Day -inf$
蒟蒻在弱省弱校，自然并没有很好的教育资源，教练将视频发给大家，大家便开始卷。蒟蒻自然没法赶上巨佬，在学习进度上一直落后于巨佬们。最后一周晚上停课，从星期三下午开始全天停课，连着之前国庆节 $7$ 天，一直在考试，蒟蒻一次比一次考得差，在考试的前两天，一次考试中只得了 $35$ 分，直接自闭了，但是巨佬们依然稳定在两百多分，下一届是从小学开始学的，参加提高组的初三同学都过了初赛，而蒟蒻昨年连初赛都没过，我觉得我要被单调队列了。
$Day 0$
上午还在考试，考到中午食堂都没饭了，便去学校对面的商场里吃烤肉自助餐，导致今天上午肚子很痛，还好考试的时候没有发作。
下午去现场试机，三道图论题，一道很多巨佬都想出来的题，蒟蒻没有想到，只打了暴力。还好试机没有成绩，不然蒟蒻又要考前自闭了。
吃完饭到九点钟，在机房里听了一场 $Beyond$ 的演唱会。
晚上和托管的同学玩大富翁，玩了两局，都是第一个破产的，心情跌落到了谷底。他们聊天聊到了两点钟，蒟蒻没有睡好。
$Day 1$
早上边听歌边复习，感觉什么都没复习到，尝试把扫描线打出来，$WA$ 了，只有二十分，心想就摆烂了。
下午早早地到了考场，学校的门前放了宣传海报，所有人等着两点钟进考试，便只能看这个。机子和键盘还是蛮熟悉的，所以没有太紧张或好奇。
拿到题了之后，便开始看。虚拟机里面如所料的没有完整的 $vscode$ $c++$ 拓展，所以没法用，连基本的补全功能都没有，所以虚拟机的唯一用处便成了编译。
看到第一题，首先想到的是贪心 + 动态规划，但是想不出来怎么做，便先放一放，n <= 5000 只有 $40$ 分，这个暴力分实在是给的太少了，磨磨蹭蹭终于横下心来放弃了想正解，就去看第二题了。
结果第二题更毒瘤，事实上，如果由符号 * 的题目，我们是之前练习过的，动态规划／记忆化搜索是完全线性时间可以做的，但是有了 * 之后，合法规则立刻变得十分复杂，最暴力的做法 $ 3 ^ n$ 的复杂度，只有 15 分，便再放一放，去看第三题。
第三题，感觉应该是有一些规律可以寻，因为一共只有 n 种数，每种数出现两次，当一个数的位置确定了，另一个一定是可以确定的，我的思路大概到此结束了，于是先把这个题放一放，去看第四题。
至此大概用了半小时。
我耐心地读完了第四题（后来才知道一些巨佬根本没有看这个题），想到的大概是类似于 P2598 的模型，要计算所有黑点和白点交界的边的权值和的最小值，可以想象到，这些边一定将黑色和白色分割成若干部分，但其中一些权值是可以避免的，如果只分成为两部分，那么一些边可以节省，依然是合法的（即将一些颜色令为相同），那么我们就想到了将黑色和白色两种点切开，中间的边就是答案。便自然而然的想到了最小割（正在写的此刻完全不知道正解是什么，巨佬们不要嘲笑蒟蒻），将黑点和超级源点连边，白点和超级汇点连边，中间就是矩阵中的边，跑最小割（最大流）即可。大概在考试前几天，在完成随机绿题 $100$ 道，里面一道树形 $DP$ 的题我用了最小割，就恰巧复习道了网络流，于是我在考场两分钟就打出了正确的 $Dinic$ ，最开始用的 $vector$ 存边，因为有多组数据， $vector$ 可以方便地 $pop_back$ 但后面打网络流的时候想起了双向边编号 ^1 的性质，vector.pop_back 就没法用了，所有最后的解决方案是存两张图。几个稍大的样例都可以过了，最后一个在 $Windows$ 下我自己数了要跑五六秒，心里有点悬（忘记可以开 $O2$），于是就在虚拟机又跑，想起开 $O2$ ，使用系统里的 time 命令，得到时间大概 2.7 秒左右，觉得可以接受了，就走了。
离考试开始过了一个半小时了。
回头看第三题，不想再想正解，就打了搜索。有一个优化，当一个数的位置确定了，与它相同的那个数的位置也可以确定了，如果搜索到结果不合法，直接结束，可以过“大样例”，觉得 40pts 可以水到。做了近一个小时。
第二题就直接放了，再看第一题，我猛然发现暴力的复杂度是 $n^3$ ，连 40pts 都拿不到了，枚举两种各分配多少个，枚举每个飞机，枚举所有可用的（那个东西叫什么记不到了），最后的枚举可以用堆优化，选择上个结束时间最小的，复杂度是 $n ^ 2 \log n$ 。半个小时打完就走了。
第二题太毒瘤了，即使是指数级的暴力我都不知道怎么判读一个串是否合法，就索性直接打表样例，如果不是样例输出 $3 ^ {num(?)} $ ，即随便填的方案。
估分
$ 20 - 40 + 0 + 20 - 40 + 80 - 100 = 120- 180$，这是在第四题是正确的情况下，虽然所有样例过了，但我依然觉得很悬。
各个网站的成绩
| A | B | C | D | Total | |
|---|---|---|---|---|---|
| LuoGu | 40 | 0 | 40 | 100 | 180 |
| INF | 50 | 5 | 52 | 60 | 167 |
| Hydro | 60 | 0 | 40 | 100 | 200 |
| YouDao | 40 | 0 | 50 | 75 | 165 |
| JiSuanKe | 40 | 5 | 40 | 100 | 185 |
| Min | 40 | 0 | 40 | 60 | 140 |
| Ave | 46 | 2 | 44.4 | 87 | 179.4 |
实际成绩：45 + 0 + 44 + 60 = 149