Hello 2025

· · 题解

## CF2057E1/E2.Another Exercise on Graphs (Easy Version) 场上有点唐。这个题做了还挺久。 E1 二分答案后转化为经典的 0/1 最短路，随便做。 E2 其实只需要转一个弯，注意到边权为 $0$ 的边相当于缩点，只有当会缩点的时候图的形态才会改变，才需要重新跑最短路，并查集模拟即可，重新跑最短路也不需要写 bitset+bfs 写一个类似于 floyd 的 dp 就是严格 $\mathcal{O}(n^3)$ 的。 ## CF2057F.Formation 感觉也不难啊，怎么场上就是脑子不好使。 显然枚举一个点作为答案只会影响前 $\mathcal{O}(\log V)$ 个位置。 显然答案具有单调性，考虑二分答案，设计一个 check 是容易的。注意到两个 comfortable 的序列对位取 $\max$ 仍然是 comfortable 的。假设二分的答案为 $X$，考虑令 $c_0=X,c_1=\lceil\frac{X}{2}\rceil$，$c_i=\lceil\frac{c_{i-1}}{2}\rceil$，那么对于位置 $i$ 答案 $X$ 可行，当前仅当 $\sum_{j=0}\max(0,c_j-a_{i-j})\le K$。另外一个关键的点在于一旦有一个最小的 $j$ 满足 $c_j\le a_{i-j}$，那么后面一定有 $c_k\le a_{i-k}(k>j)$。知道这个就很好做了，枚举这个最小的 $j$，得到 $n\log V$ 个决策，每个决策适用的 $X$ 是一段区间，这是容易求出的。 然后考虑直接解决询问，一个粗暴且常数非常大的做法是把决策直接塞到线段树里，然后直接二分答案 check 即可，这个做法是 3log 的，而且空间要求也大。 考虑另外一种比较优美的做法，将询问离线，按照 $K$ 从小到大排序，显然答案具有单调性，于是可以扫描线并用一个可删堆保存当前的决策即可。复杂度是优美的 2log。 ## CF2057G.Secret Message 很牛的题啊，场上确实想不到。 考虑给每个点 $(x,y)$ 赋一个编号 $x+2y$，注意到一个点与周围的 $4$ 个点共 $5$ 个点的编号对 $5$ 取模后不同余，所以可以考虑只对 $x+2y\equiv i\pmod{5}$ 的点染色（$i=0\sim 4$）。但是有一个问题是，这个点可能在边界上导致其邻居不全或者其邻居上的字符不是 `#`。实际上，将这样的点直接染，然后取最小的染色个数的 $i$ 即可。考虑如何量化这个周长 $p$，是不是就是一个点周围的邻居不存在或者其字符不是 `#` 就会加上 $1$。那么根据抽屉原理，必有一个 $i$ 满足染色个数小于等于 $\dfrac{s+p}{5}$，所以做法正确。