赛题：「COCI 2023.3」Slastičarnica 「COCI 2023.2」Bojanje [COCI 2024/2025 #5] 树树 2 / Stablo II 「COCI 2015.10」RELATIVNOST

今天是 Day 2，吃早饭时没有食欲，预感要炸，先来机房听了会歌。

三道青一道蓝，这个有点意思。

赛时

$7:30$ 开题，看了 $5$ 分钟 T1 没有什么思路，遂跳过去看 T2。

（这将成为我比赛中最为严重的决策失误）

看 T2，看到 $t=10^{18}$ 想到应该是矩阵加速，但是不同颜色应该不是很好存储，决定思考一种二进制压位方法。

（其实我想过哈希但是担心状态过多就放弃了，事实证明哈希才是正确的）

过了一会发现其实这题跟颜色与顺序都无关，所以每种状态直接按照颜色排序然后离散，根据相邻两位是否相同就可以得到一个长度为 $n-1$ 的二进制数（这是一个非常好的思路，其他人基本没有想到也就没有拿到第二档部分分。但可惜因为太好导致我死磕 T2 浪费了很多时间，不过这个方法也不是完全没有意义）

写完转移矩阵和矩阵快速幂时是 $8:10$，交上去 T 了，我以为根据我的计算复杂度卡卡常是能过的，于是卡了几分钟。

但是还是没有卡过，这时我的决策相对正常，直接跳到 T3。裸的树剖？我怎么没有早点去看这道题？

但是事实证明这么新的题目出板子是不可能的，树剖被卡了。卡了一会没卡过，我觉得 T2 的 $100$ 分比 T3 的 $20$ 分更有性价比，于是回去看 T2 了。此时 $8:45$。

但是我又看了一会，尝试了很多办法都没有想到正解，期间我甚至调了转移矩阵，看到了非常多的 $0$，尝试对这些 $0$ 剪枝，但是发现矩阵快速幂面前这些剪枝是错的，一想到连续两道题都被卡掉了，我有一点点红温。

$9:05$ 红透了就去看 T1。真奇怪，为什么我现在一眼就想到可以二分加倒序处理？中间的部分可以用区间 DP 做。但是区间 DP 的复杂度是 $O(N^3)$ 的，我就又想了一会，采用向外扩展，每次只对相邻项或者区间长度对应的元素进行处理，证明了一下没有问题，就开写。

约 $9:30$ 写完，交上去发现：不是怎么老被卡常啊？此时已经彻底红温了，真的脑子里一片混乱，但是情绪居然没有崩溃。

仔细想一想复杂度瓶颈只会在 ST 表的 log2 函数了。很幸运我一开始就用的 ST 表而不是线段树。处理了这个问题就过了。此时 $9:45$。

继续看 T2，我觉得我可以做出来。我在这期间想到把 $k$ 个数单独拎出来再对剩下的数压位。并将不属于这 $k$ 个数的其他数统一变成 $0$ 号色。但是发现这样对 $0$ 号色没有区分度，还需要加上一位，这不就等于没压吗？放弃。

此时 $10:10$，得分 $200pts$，排名第 $4$，想放弃。

但是我强撑着打完了 T2 的第一档部分分，然后突然发现第二档部分分好像卡卡就能过。想了一会不知道怎么卡，但是我想起来我在之前想正解时对 $0$ 的部分有一种剪枝方法，所以就用了，花了 $20$ 分钟写完调完拿到了第二档部分分，然后发现不剪枝也能过。

其他人怎么没有想到第二档部分分？太好了我到第二名了。

就在这时 tjh 让我看了看 T4，我看了一眼，我的天哪能用我最喜欢的动态 DP！但是我已经没有时间了！！！我在 T2 足足费了 $2$ 个小时都没有过，为什么不去看看 T4 呢？这应该是我今天比赛的一个重大失误。我的情绪终于崩溃了，提前结束了比赛并回到座位上红温了。

最终得分：$100+64+100+0=264$ 分，打成区了。这个 $rk2$ 感觉名不正言不顺的。

赛后

我觉得我有足够的 RP 面对明天的比赛。

不我没有 RP 了，我语文考的贼好，感觉明天得掉。

好了开始复盘：这场比赛我的时间分配极为不均匀，由于我分配在 T2 的时间过长（约 $2$ 小时）导致我最后看到 T4 时已没有足够的时间，这是最为重大的决策失误。

对于 T1，我依旧是非常满意，一开始没有思路就跳过应该是正确的，不然可能会卡住一会时间，最后也是非常容易就想到了思路并且很快完成。

对于 T2，我在补题的时候才发现，原来正解就是像我一开始处理的哈希，因为他的有用状态只有 $42$ 个！我的天哪我怎么就没有去打个代码算一下这个呢？而且这个题浪费了我足够多的时间。幸运的是这些时间并非完全没用，也帮助我完成了第二档部分分。这个题可以说是这场比赛的一个败笔。

对于 T3，有一点遗憾。rxr 居然只用了 $19$ 分钟就做完了，我没有想到合并一次处理的点，最重要的是我居然没有去想动态树，这是非常难受的。不过裸树剖都有 $100$ 分，而且我也没在这题上花费太多时间，中规中矩吧。

最后就是我们的 T4 了，很遗憾我没有足够的时间去做你。不过我发现其实这题不用 DDP，只需要维护一个背包就行了（类似矩阵）。这个题还是相对简单的。

唉，依旧差亿步美满。不过好在我的心理素质让我撑过了部分分，这是值得肯定的。

明天继续！