¶ 2020 CCSP 分区赛
¶ 物资准备
能自带电子设备是什么神奇规则啊……
-
-
- bison 和 flex (用于生成 lexer 和 parser)
- 从自动生成的代码删除注释：
g++ -E -fpreprocessed -dD(不删的话代码太大交不了
) - 带上 2019 熊猫杯 A 题做例子
- Python 文档
- 从自动生成的代码删除注释：
- man-pages
- bison 和 flex (用于生成 lexer 和 parser)
其他 (看一下 CSP Linux 里面缺什么，准备一下……)好像并不缺什么
-
¶ 预期成绩
铁牌
¶ 比赛记录
首先一上来主办方就把题面传错了，过了几分钟才改对。
¶ T1 - 办签证
我只能想到拆点 (拆成 个)，然后强行跑堆优化 Dijkstra。这样做复杂度应该是 还带个 ，我第一发提交样例都过不去 (测的时候没仔细看)，结果 分。第二次 T 了 个点， 分，这是因为我天真地以为自己的算法能 分，所以循环直接写到了 的上界。改成读入的 以后过了 分。
然后想着把 STL 堆换成 pb_ds 堆能不能快一点，结果用 Python 随了一组极限数据，发现不管用啥堆都跑到了 秒，肯定卡不下去的，就放弃了 分。据场上的 dalao 们说这题要用什么分层图的优化，完了再补吧。其实所谓分层图就是，拆点以后如果 到 有边，一定有 ，所以就是个 DAG，直接 DP 求最短路就比 Dijkstra 少个 。这题是第一次双周训练原题，不过双周训练那场的出题人把数据出水了，导致 分算法可以直接过……
(我校赛网络赛讲题还说了句 “DAG 就应该把 Dijkstra 卡掉”，现在自己却不会这题，应该写检讨。)
不过我很好奇这题为啥有人最后都是 分啊，就算拆点都不会，贴个 Dijkstra 板子就能 分啊……
¶ T2 - 给他文件系统
前 分就是个裸的可持久化 trie，然后我就写了半天，结果一交上去 分。开编译警告一看，有个地方数组越界了，改了以后变成了 分，甚至连第一个点都过不去。对着代码看了半天发现，我把 write 操作的输入写成了
scanf("%s%d%d\n", filename, &offset, &len);
for (int i = 0; i < len; i++)
op[i] = getchar_unlocked();
这看上去很合理，但根据 C 标准对于 scanf 的规定 (C99, 7.21.6.2 p5) ：
A directive composed of white-space character(s) is executed by reading input up to the first non-white-space character (which remains unread), or until no more characters can be read. The directive never fails.
那个 scanf 会把下一行开头的空白字符都读掉，而题目说了数据可能包含空白字符，只好改成
scanf("%s%d%d", filename, &offset, &len);
getchar_unlocked();
for (int i = 0; i < len; i++)
op[i] = getchar_unlocked();
交上去变成了 分。看了一下数据描述，发现有 ls 操作的大数据就挂了，于是怀疑 ls 写挂了。最后发现写寻找字典序最大的文件名时，直接复制了找字典序最小文件名的代码改了一下循环顺序，但“碰到一个文件就不再递归”的逻辑没改，结果如果同时存在 114514 和 1145141919810 这两个文件就会输出 114514，这是错误的。改了以后就拿到了 分。
(中间还不小心交上去一个空文件 QAQ。)
然后脑补了一个合并可持久化 trie 的两个状态的算法，想拿剩下的分，大概思路是从两个根开始一起递归，如果递归到实质相同的点就不再递归，否则就递归地强行合并，结果最后只多拿了带 merge 的小规模数据的 分。后来感觉那个算法是假的，大规模就点数爆炸了，可能加个启发式合并会好一点？到时候再看题解有什么高论吧。
¶ T3 - GC
目测不可做
虽然我平时写代码一般都用没有 GC 的语言 (C++ 和 Rust)，但说实话 GC 的原理我还知道一些 (之前用 Go 被 GC 坑死过，然后放弃了)，还是能做个几十分的。然而前两题把时间都耗完了，看来代码能力还是有待提高。
这题封榜前全场第一就得了 3 分，但是居然有两个 PKU 的得了好几十分，tql！
¶ 总结
最后获得西北赛区金牌 (第三名)，全国金牌 (好像二三十名的样子 qaq)，被西交吊着打。西交居然打到全国第一了 orz。
这次感觉自己打得非常不好，本来想完整地过一道题 (其实 T1 也就是个很传统的算法竞赛题……正常应该会做的 qaq)，结果最后没有实现，看来我还是太菜了 QAQ。而且耗费了大量时间想把 T2 拿满，最后写了个假算法，拿这个时间去仔细思考一下 T1 或者写写 T3 都能拿到更多的分。
另外一开场打模拟真的自闭 (T1 虽然是比较传统的算法题，但是要输出路径…… 也跟模拟差不多了)，明年应该自带一道 div2 题用热身时间写一下。
¶ 吐槽
CCF 的人居然在颁奖会说计算机科学与技术专业的人系统能力会比别的专业强，我觉得这是胡说八道，显然是航天类专业的更强 (但是我是拖后腿的)。
¶ 补题
T1 写了一下双周训练的那个题，T2 和 T3 等主办方挂出来再说……