游记 - WC 2023

上课

后悔。后悔为什么没有认真上课。

本来以为只有第二课堂的东西够简单，结果去看还是无聊。第一课堂有趣啊，至少我上的一个欧洲信息学竞赛选讲的课是好的。上的唯一一节课还发了言，哈哈。

考试

困。

会了暴力，但是总觉得 T1 快要推出来了，T2 快要推出来了。把 T1 做成平衡树，把 T2 想成一个无向完全图里找一条相邻边颜色不同的环路，其中每个颜色占且仅占一个完全图。

最后 1h，敲一下 T2 的 32pts，状压 + $m=1$。只测了小样例。

连讲题也能忘记听。

喜提爆零。

后来去测大样例，有这么一组输出：

1 2 3 4 6 6

反思

下面提供一点极其情绪化的反思。

感觉自己根本没有认真对待。本来也只以为 WC 就是随便考一场超出能力范围的，课也完全没价值。但是至少我上的那一节就很好，比起校内的死气沉沉好的多了。这一次的 32pts 明明可以有 Cu，好。

思维上不够灵活，代码能力也不够。

还是觉得都是堆题的问题。不够，更多。

另一个比较纠结的就是，暴力到底应不应该写？很多时候暴力和对拍写起来非常冗长，但是很多时候又十分有意义，至少能拿稳分。但是一些月赛又没有部分分。这涉及到考试策略。

没准平时写一写大 ds 未必不好，学一学思维题也很有必要。

学校的训练很大程度上停滞了。自己也开始学一些其他学科的了，但是还是要想办法，保持键盘感。

做题吧，动起来吧。无论是月赛，或是静态的模拟赛题。没事写写吧，写写吧。

复盘

啊，我指的是对题目的复盘。

只能说都还没想懂。T2 的构造已经基本有脉络，大概就是：判合不合法是简易的，只要看是否有集合超过 $\lfloor\frac{2}{3}n\rfloor$。

当这个最大集合的大小就是 $\lfloor\frac{2}{3}n\rfloor$，那么每三个放两个是基本策略。

其他的呢，可能也可以乱搞过，不过乱搞想的不明白，比如说可以在这个三个放两个里面夹住出现较多的集合里的，尽量使剩余合法。一个通俗的搞法就是直接随机。貌似贪心+随机可过来着。

其实不难啊，可是为什么我要想到环路呢。以及那个每两个集合的交集最大为 $1$ 依然不明白。

T1 的话好像是把边界横纵对应 $\pm 1$，然后变成找一对 $\pm 1$ 使得距离为 $q$，貌似是二分，但是不明白。

---

Updated on Jan. 30th.

LOJ 出数据了。破案了，为啥 T2 没分：全 MLE 了，导致编译错误。

可恶。连随机构造都有 40pts，下面给出两种 40pts 的可行做法：

• 限定前 $x$ 组数据的总次数不超过 $10000x$。
• 每次随机 $10^8\div t$ 次。

这不白送的铜牌？我还不清楚 T1 暴力多少分，没准银牌是白送的？