Codeforces Round 1043 (Div. 3)

发表于 2025-08-22 分类于比赛 Waline：

Codeforces Round 1043 (Div. 3) A~F 题解

~~这还是 CF 吗？这场有思维题吗？~~

A. Homework

按题意模拟即可。

所有 $\dfrac{n}{10^k+1}$ 即为答案。

化成三进制，按题目给出的公式计算即可。

首先还是化为三进制。第 $x$ 位上的数字 $a_x$ ，表示取 $3^x$ 个西瓜的次数。

一次操作后，总购买次数增加了 $2$ 。

注意到进行操作后，总花费会变小，且 $x$ 越大，总花费减小得越多。所以我们从高位向低位枚举，每次都贪心地，对当前位做尽可能多的操作。

通过枚举位数，判断最终在哪个数字处截断。然后问题就变成了：求 $0\sim x$ 的所有数字的每一位的和。

枚举每一位 $i$ （定义最右边为第 $0$ 位），求出第 $i$ 位上所有数字的和。将数字拆成三部分：第 $i$ 位左边的部分 $l$ 、第 $i$ 位 $p$ 、第 $i$ 位右边的部分 $r$ 。

那么我们将 $0\sim x$ 划分成以下几段：（用 $[x~~~~y~~~~z]$ 表示 $x,y,z$ 三个整数拼接起来的结果。 $x,y,z$ 的位数分别与 $l,p,r$ 相等）

$[0~~~~0~~~~0] \sim [l-1~~~~9~~~~999\dots999]$ ：和为 $45\times l\times10^i$ 。
$[l~~~~0~~~~0] \sim [l~~~~p-1~~~~999\dots999]$ ：和为 $\dfrac{p(p-1)}{2}\times 10^i$ 。
$[l~~~~p~~~~0] \sim [l~~~~p~~~~r]$ ：和为 $p\times(r+1)$ 。

把每一位的和都算出来，再加起来即可。

将 $a,b$ 从大到小排序，并对它们做前缀和。前缀和的结果记为 $SA_i$ 、 $SB_i$ 。

那么题意可以转化为：已知 $l,r,z$ ，记 $F(i)=SA_i+SB_{z-i}$ ，求 $\max_{l\le i \le r} F(i)$ 。

我们考虑 $F(i)$ 到 $F(i+1)$ 的增量：

\begin{aligned} \Delta_i &= F(i+1)-F(i)\\ &=SA_{i+1}+SB_{z-i-1}-SA_i-SB_{z-i}\\ &=a_{i+1}-b_{z-i} \end{aligned}

因为 $a_i,b_i$ 都是递减的，所以容易得到 $\Delta_i$ 是递减的。所以 $F(i)$ 是凸的。

三分即可。

边双联通缩点后，找到 $1\to n$ 的路径上的所有边，也就找到了原图上的必经边。

把所有必经边的两个端点都放在一个队列里，记录一下这条边的编号。然后 BFS 就做完了。