CSP-S 2024 游记

· · 生活·游记

Day 0

直接开始试寄。

桌子是非常奇怪的六边形桌子？

最开始以为电脑后面贴的数字就是考号，结果一直找不到坐？问了一下才知道桌子上放的才是。

发现只有一个 devcpp 可用，vscode user 表示不满。

测了一下发现指令集能用（但实际上似乎是不能用的？），然后随便写了点啥就走了。

晚上玩 florr 出 umag 了！

Day 1

直接进入考场。

发现密码非常奇怪，还有 *# 这种字符。然后开始看题。

T1 签到题。你直接 sort 然后从前往后贪心推一遍就做完了。

T2 感觉像大模拟啊。直接二分出每个车对应的区间，然后贪心做区间覆盖。

具体的你可以把每个 r 存到 l 的 vector 里面，然后从前往后扫一遍，把扫到的 l 对应的 r 存起来，直到扫到一个之前的 r，此时答案 +1 并且清空 r。场上我拿一个 map 来写但其实没必要，记录一个时间戳就可以做到线性。

T3 好像是原题（？）。设 f_{i, j} 表示当前在位置 i 并且最近的非同色数的值为 j。然后你拿数据结构优化，或者直接记录一个全局的 tag 可以做到线性。

T4 我场上写了个 n^3 暴力，就是你直接 solve(l, r, n) 表示当前区间是 l, r 且只有前 n 个确定时，可以赢的编号集合。具体实现就是直接返回一个 vector，然后对于左右两边直接暴力合并，但是最后也没调出来，遗憾离场。

Day 2

回来后又考虑了一下 T4，注意到每个区间肯定有一半是全确定或全不定的，这些可以 n \log n 预处理，询问时你再随便维护一下，单次 solve 应该就是 \log^2 的，但场上没想出来啊啊啊！！！

估分应该是 100 + 100 + 100 + 0 = 300。回来之后发现人均 300+，我还是太蒻了。