THUSC2022 游记
Day -?
过审了。今年的 THUSC 线上举行。
希望不要像去年一样打铁。
依稀记得，去年 day1 非常爆炸，就算 day2 力挽狂澜翻回了一些分，也没能上初二可怜的良好线。
希望今年能好一点。
Day 1
上午
上午开幕式，然后试机。
被监考老师表扬了双机位放的很好是我没想到的…
但是这都不重要！准备好下午的考试状态！
于是复习了一下 KMP、SA 以及一些 DS。
下午
13:15
进入会议室，拍身份证进行身份核验。
核验完身份后又被移至了等候室。
13:30
被重新移入了会议，开启 OBS 录屏。
14:00
本来要开始考试的，但是因为有的会议室没有进行完身份核验，所以延迟了十分钟。
14:10
又延迟了 10 分钟。
14:20
开始考试！
看题！
- T1 看起来像个暴力 dp 题（题目明示做法），估计按题意去做然后优化就行了。
- T2 不太会，也许可以暴力一下。
- T3 通信题，第一眼一点思路都没有。
- T4 感觉有一些暴力分比较好拿。
于是我先开始写 T1 了。
15:30
不错不错，T1 写完了个大记搜，刚调出来。
感谢 T1 的良心出题人（比后面的题不知高到哪里去了），在提示那里教了我们条件概率的知识，如果没有这个的话我估计就写不出来了。
交了一发，50 分，毕竟感觉这个很暴力还有很多可以优化的地方，继续加油吧。
15:33
发现可以预处理某个时间段有哪些可能下雨的点，这样能省一些复杂度，写了一下。
15:43
发现可以最短路优化，写了一下。
15:46
交了一发。50pts 变成了 65pts。
不太会优化了，先去做后面的题。
16:17
研究了一会 T2，发现有一个 的由暴力优化而来的二分 + 主席树做法。
果断开始写。
16:39
写完了 T2。交了一发。
16:41
刚刚交的 T2 终于测了出来，怎么感觉评测队列开始变长了？
T2 怎么 WA 掉了？？？我不是很理解。
16:45
发现自己的 T2 中一个小错。
果断提交。
16:47
现在队列可能已经长得不可接受了，于是我决定先去看看第四题。
16:54
现在 16:45 的提交还没测出来。我决定开始写第四题的暴力 KMP。
17:02
又看了眼 T2，还没测出来，继续写 T4。
17:14
T4 暴力写挂了，还没调。去看了眼 T2 发现 T2 测出来了还是 wa？？？
于是又去看了几眼 T2，没查出什么问题。。。
17:17
决定对 T2 写一个对拍。
先写个暴力。
暴力还没开始写，就发现自己的 T2 中一个 打成了 。
果断又交了一次 T2，然后没有继续写对拍，去调 T4 了。
17:27
T4 暴力调出来了。交一发。
然后发现上一发 T2 还没测出来，估计要等一段时间了。
于是决定把 T2 拍上。
17:32
T2 测出来了，还是 wa。继续写 T2 的暴力。
17:38
T2 暴力写完了。去写 T2 的 gen 了。顺手交了一发暴力看看写没写对。
17:42
拍上了。同时继续检查 T2。
17:50
查不出来错。。。然后发现 T4 的暴力过了 30 分。
17:58
去看 T4 的别的部分分了。
想写一下 的部分分。
18:05
写完了，这时候 T2 暴力终于 running 了。
然后发现 T2 暴力 wa 了。崩溃了。怀疑是不是读错了题。
18:12
完全不知道自己 T2 哪里错了。而且评测队列超长，估计赛后都测不出来。
把 #define int long long 的 int 全改成了 long long 又交了一发。但是肯定没用啊。
T4 还没测出来。去看看通信题。
18:25
想了十几分钟还没有想出一个比较好的可以拿的部分分。没办法了，先去把这题的 4 分做法写了吧。
18:34
4 分做法写完了。交了一发。
这时候 T4 还没有测出来。T2 的也没有（不过我确信一定会 wa）。
继续看看 T2 吧。。。
19:00
我！终！于！知！道！了！
T2 子段必须非空！！！！！！
初始化 ans 应该为 -inf！！！
提交！！！不过这个点交可能看不到结果了。。
19:14
发现了一个 T4 时的错误，改掉了，交了一发。
19:18
弃疗了，看了会 cppreference。
19:20
比赛结束！
估分 。目前能确定的是 T1 65 分和 T4 30 分。
突然感觉好悬啊…尤其是这个 T2，要是还是 wa 的话我就死了。
19:30
交流了一下。
发现 T1 就是直接 dp，但是好像要多预处理一点东西？不过我预处理了这个啊，复杂度我感觉也是对的。
T2 有个超短的 50 分 dp 做法。。。果然我 dp 不行。
T3 rui_er 用随机拿到了 36 分，orz。
T4 没啥交流出的东西。
20:12
终于，pretest 测完了。
。最后那 4 分和 10 分还是挂了。
不过好在 T2 的 50 分拿到了…我的 T2 当时是我最害怕 wa 的。
明天工程题加油！想翻盘…
Day 2
上午
今天是工程题。想到了去年被 T4 依赖 T3 给害惨了的经历，决定这次要稳扎稳打，不要再被出题人坑了（伏笔）。
能翻盘吗？？
复习了一下二进制文件读写，就匆匆开考了。
9:00
延时 10min 开始考试。传统艺能了属于是。
9:10
开始考试！
9:12
发现这次工程题和去年有很大不同。去年是让你实现一个大项目，填补其中的空缺。而今天是五个小项目，每个项目分别涉及一种知识。
- T1 是写一个简单 HTML 解析器，应该是比联合省选 D1T1 还好写的小模拟。
- T2 好像是模拟一个爬虫的过程。
- T3 是实现判断查询词与文档相关性的一个算法。
- T4 是实现一个网页权重算法 PageRank。
- T5 是实现一棵决策树用来文本分类，好像是机器学习啥的，很吓人。
肯定先写 T1。
9:17
研究完了 T1 的题面。
关于 T1 这样的类似标签嵌套状物的模拟题的实现套路我已经很熟练了，多亏了同学的一道丧心病狂的阴间模拟题对我的磨练。
我的模拟思路大概就是将输入全都读入进来之后维护一个字符指针，在这个读入的字符串上做递归，时刻传字符指针的引用就行了。
开写！
首先开局读入全文…想到了刚复习的 fread！虽然不是二进制文件读写，但是能一次读全文件的性质也很有用！
9:41
写完了！稍微调了几秒钟就过了样例。交了一发。
为啥没 pretest？？？
发现了个小错，改掉了再交一发。
但是没 pretest 真的太虚了…
9:45
提了个问题，“老师请问这场比赛是没有 pretest 吗”。
然后又感到了关于 T1 输出格式的问题…如果一段非空但是前后是空的的话要删掉前后吗…
于是又问了个问题。
9:51
手造了几组样例，感觉没啥问题了。
去看 T2。
10:04
将 T2 的题意彻底理解清楚了。直接模拟就可以了，挺水的。
不过这个逗号分隔字符串真的恶心人…我写了个用 getline，然后找到 , 的位置后用 substr 拆开逗号前后的部分。对于后边的字符串，开一个 stringstream，从这个 stringstream 中读入每个用空格隔开的字符串。
10:35
T2 很快写完了，而且还是在中间时不时回头看看 T1（因为觉得不稳）的情况下。
10:38
发现现在有 pretest 了，T2 wa 了。同时交了一发 T1，RE on pretest 3。决定先调 T2。
10:40
发现了 T2 的错误。写完之后交了一发，过了。
然后又想了想 T1 为什么错。
10:47
T1 还是改不对，怀疑 pretest 3 是假的，因为我对我的做法抱有自信。
问了出题人一个问题，“T1 pretest 3 是否错误”。
出题人：“很抱歉不能理解您的意思”。
。。。
10:56
这时候发现了果然 T1 要删掉前后的空白字符，改了一下又交了一发，果然还是 RE on pretest 3。
10:57
决定先放手，去写 T3 了，不敢在 T1 这个坑里浪费太多时间，重蹈去年的覆辙。
T3 我决定先看中文文档，实在不行再看英文的。
然后发现那个中文文档是保姆级的，直接代入式子就完事了…
只不过式子里有些地方有点歧义（比如 没有写底数、文章长度没有定义是单词个数还是字符个数等等），但是我觉得多试几次就能出来。
11:00
开始写 T3 了。
写 T3 中间还穿插着一些对 T1 的试探…但是估计没啥希望…
11:21
T3 的文档非常好理解，现在就写完了。
交了一下，wa 了。尝试改了改各种地方的不明确定义，最后发现是文章长度我写的字符个数，改成了单词个数试试。然后就过了。
11:25
开始看 T4。
11:34
看完了其中一个中文文档，感觉也是挺容易实现的一个算法。只是还是有点不明确的地方。
然后看了看另一个中文文档，发现那个文档比这个写的详细多了，许多细节的问题在这里得到了解答。
在草稿纸上整理了一下式子，准备开写！
11:43
写完了。不得不说，这道题真的是今天的工程题中输入最最容易的题了…
样例一发过。交了一发，也一发过了。真不错。
下面就是一个至关重要的决策了。
- 去尝试调 T1 的 4 分。
- 去做看起来根本看不懂而且量很大感觉做不完的 T5。
我选择了后者。理由如下：
- T1 的 4 分我脑子中没有任何头绪。现在去调，也不知道能不能调出来，调出来了也只能多 4 分，性价比极低。
- T5 足足有 26 分，而且说不定不一定看不懂呢。总是要尝试一下，虽然一个多小时的样子真的不知道写不写的完。但这肯定比去写 T1 更加值当。
于是我做了一个本场比赛最正确的决定，放弃 T1 的 4 分。赛后也证明了 pretest 3 确实假了。而我浪费在上面的时间只有前前后后加起来半小时左右，相比之下很多人两个小时耗在上面最后没有去写 T5 痛失 AK 机会。
于是我开始看 T5 了。
11:46
我先看的是那个博客文档。里面对决策树给出了一个不错的定义，配上女生找对象的实例促进了我的理解。（？）
但是那个博客文档的伪代码非常难懂，让人完全摸不着头脑。
于是我去看了看别的文档。
英文文档先不管了，发现有一个中文书。
11:55
那本书里的伪代码真不错！一下就看懂了！
还有信息熵的式子！解释的比那个博客文档不知高到哪里去了，可以直接扒下来用！
但是这个伪代码看着简单，实现想必是十分复杂…
尤其是伪代码中一行带过的一步，这一步实际上十分重要也比较难写…
但是不能犹豫，我先简单规划了一下建树的实现。
12:00
规划完了。大概是这么个想法：
- 训练集合使用一个数组存下标的方式维护。dfs 在这个数组上进行。dfs 中传参数传数组中的一段区间 。然后使用类似归并排序的方式，开一个临时数组，将需要划到左子树的训练文档下标放在临时数组的左侧，划到右子树的放到右侧，然后 copy 到原数组里，用 和 递归下去。
- 当前的决策集合不是特别大（最多只有 6），可以在 dfs 参数中开一个
set，反正开的下。 - 此外就是需要无比细心的实现就是了…讲真我想到这一步我都感觉我写不完了，但总还是要尝试一下的…
开写！
12:46
居然写完了！感觉做题的时候把思路放清晰真的是一个很好的做法。
测测样例…果然挂了，中间 RE 了。
没关系，现在还有 24 分钟调试时间。
不过我对我调试 200 行的代码不太有信心就是了…
12:50
发现自己对当前节点的处理出现了问题。果断改掉。
然后呢，还是没有输出。
12:53
又发现自己对信息熵的计算出现了一些问题。
在计算信息熵时，我没有循环到类别总数，而是错误地循环到了决策总数。
改了改，发现有输出了，但是是错的。
13:02
发现自己在计算使用每个决策后分别的信息熵时算了个寂寞…
于是改了改。
怎么又 RE 了？
13:05
我发现自己得出的一些信息熵是 nan。
然后发现了出现某一类别的概率可能为 …然后对着 求 ，必死无疑。
把这个 判了一下。
过样例了！
13:06
提交。
过了！！！nice！！！！
然后去搞了搞 T1 的 pretest 3 作为娱乐。最后显然没有搞出来就是了。
13:10
考试结束。
出考场，交流了一下，发现 T1 pretest 3 确实是假的。那我是不是 AK 了？
反正翻盘了是肯定的。
Day ?
优秀。