CF2204 (Edu. R. 188) 赛后笔记

Locklink

2026-03-19

E

Statement

对于正整数 $x$ ， $S(x)$ 通过如下过程生成：设 $f(x)$ 为 $x$ 的各位数字之和，迭代地：将 $x$ 附加到 $S(x)$ 的末尾，如果 $x>9$ 则令 $x:=f(x)$ ，反之结束迭代。

给定 $s$ $(|s| \le 10^5)$ ，重新排列 $s$ 中的数字使得存在 $x$ 使得 $s=S(x)$ 。输出任意的重新排列后的 $s$ 。

Solution

$f(x)<10^6$ ，枚举 $f(x)$ 即可。
submission

F

Statement

给定一个整数数组 $a$ 和多次询问 $k_i$ ，每次操作可以将任意一个分数的分子加 $1$ 或分母减 $1$ （分母需大于 $1$ ），求数组 $a$ 的所有连续子数组以各项倒数（即 $\frac{1}{a_l}, \dots, \frac{1}{a_r}$ ）作为初始分数序列时，在恰好进行 $k_i$ 次操作后能得到的最大分数和的总和，结果对 $998244353$ 取模。 $n,m \le 5 \times 10^5$ 。

Solution

显然对于某个区间，一切操作都要在分母最小的数上做才更优。

那么这种有关最大最小值的区间计数类问题显然要对每一个位置求出它能产生贡献的区间，这个过程可以用单调队列 $O(n)$ 地实现，注意为了规避相同的的数值产生区间重复要把一侧的等号去掉。

那么具体应该减分母还是加分子？结论是：优先减分母，分母减到 $1$ 之后然后全部加到分子上。那么对于不同的 $k$ ，以 $a_i$ 为分界，贡献的计算就有了两种计算公式。 $k$ 是升序给出就更提示我们，要用前缀和维护对于每个 $k$ 的答案。