2132A. Homework
题意
有 Vlad 和 Dima 两个人，他们需要依次将字符串 $b$ 中的每个字母放到字符串 $a$ 的头或尾。其中 Vlad 会将字母放到 $a$ 的开头，Dima 会将字母放到 $a$ 的末尾。
已知三个字符串，$a, b, c$，其中 $c$ 代表两人操作顺序。若 $c_i$ 为 V，则第 $i$ 个字母由 Vlad 放置；若 $c_i$ 为 D，则由 Dima 放置。
输出 $a$ 的最终状态。
题解
模拟即可。
考虑简单的实现方式，由于添加到开头（左侧）不太方便，所以我们将添加到左侧的字符保存到另一字符串中，在所有操作结束后逆序输出。
参考代码
2132B. The Secret Number
题意
对于数字 $x$，可以进行一次操作：
- 在 $x$ 的末尾添加至少 $1$ 个数字 $0$，赋值给 $y$。
- 操作后的数 $n = x + y$。
给定 $n$，求所有可能的 $x$，从小至大排序输出。
题解
发现
$$y = x \cdot 10^k$$
其中 $k$ 是添加的 $0$ 的个数，满足 $k \in \mathbb{N}^+$。
因此：
$$n = x + x \cdot 10^k = x \cdot (10^k + 1)$$
即对于给定的 $n$，所有可能的 $x$ 的值为：
$$\frac{n}{10^k + 1} 当 k \in \mathbb{N}^+ 且 (10^k + 1) | n$$
参考代码
Tricks: 从大到小枚举 $k$，结果的 $x$ 必定是从小到大的，省一步排序。
2132C1. The Cunning Seller (easy version)
题意
西瓜卖家在他的每次交易中只能卖掉 $3^x$ 个西瓜，价格为 $3^{x + 1} + x \cdot 3^{x - 1}$，其中 $x$ 为非负整数。
买家希望通过最少的交易次数买到 $n$ 个西瓜（不能多也不能少），输出在此情况下西瓜的总价。
题解
容易发现，卖掉 $3^x$ 个西瓜，相当于在三进制下使 $n$ 的从右至左第 $x + 1$ 位减少 $1$。
那么，为了获得最小的次数，对于三进制下从右至左第 $x + 1$ 位，它的值为 $y$ 时，我们需要进行 $y$ 次卖掉 $3^x$ 个西瓜的操作。
代入原式，加和即可。
预处理 $3^x$ 的值即可，没必要推价格的递推公式。
参考代码
2132C2. The Cunning Seller (hard version)
题意
西瓜卖家在他的每次交易中只能卖掉 $3^x$ 个西瓜，价格为 $3^{x + 1} + x \cdot 3^{x - 1}$，其中 $x$ 为非负整数。
买家希望通过不多于 $k$ 次交易，以最小的价格购买 $n$ 个西瓜，输出此时的总价，若不能满足题目要求则输出 $-1$。
题解
首先把 C1 的代码抄过来，并记录交易次数、每次交易的（西瓜数的）指数。
发现 $3 \times 3^{x-1}$ 的交易总是比 $3^x$ 的交易要便宜。设当西瓜数为 $x$ 时的西瓜价格为 $f(x)$，列式计算替换 $3^x$ 的交易为 $3 \times 3^{x-1}$ 的交易所降低的总价：
$$f(3^x) - 3 \cdot f(3^{x-1}) = 3^{x + 1} + x \cdot 3^{x - 1} - 3 \cdot 3^x - 3 \cdot (x - 1) \cdot 3^{x - 2}$$
合并同底数幂：
$$= 3^{x + 1} + x \cdot 3^{x - 1} - 3^{x + 1} - (x - 1) \cdot 3^{x - 1}$$
合并同类项：
$$= 3^{x - 1}$$
所以当有至少 $2$ 个剩余的交易次数时，应将指数最大的交易替换掉，因为这样可以降低最多的总价。注意，当剩余的交易的指数都为 $0$ 时，就不能替换了。
这样做复杂度还是太高了，怎么优化？可以考虑只记录每个指数的出现次数，然后直接批量替换交易。
参考代码
易错点：
- 替换次数不能是负数
- 多组数据不要忘记
memset
2132D. From 1 to Infinity
题意
12345678910111213... 的前 $k$ 个数字之和是多少？
$k \leq 10^{15}$。
题解
Codeforces 官方题解没读懂，于是花了一晚上自己钻研出了一个方法。
观察发现，一位数在数字串中占据 $1 \times 9$ 个位置，二位数占据 $2 \times 90$ 个位置，以此类推。总结可得 $l$ 位数在数字串中占据 $9l \times 10^{l - 1}$ 个位置。
那么，我们通过循环地从 $k$ 中减去 $9l \times 10^{l - 1}$ 直到 $k$ 小于 $9l \times 10^{l - 1}$ ，就可以得到 $k$ 所对应的数 $n$ 的位数。
接着，我们使用 $k \div l$ 来获得 $n$ 在 $l$ 位数中是第几个，再加上 $10^{l - 1}$，即为 $n$ 的值。
我们已经知道了第 $k$ 位数字所对应的数 $n$，那么 $1$ 到 $n-1$ 的数字之和可以通过以下方式来求出：
- 把求和区间中加入一个 $0$，变为求 $[0, n-1]$ 的数字之和，这一步不影响最终结果。
- 我们可以给所有数字加上前导零，使其与 $n-1$ 一样长（设长度为 $l$），这一步不影响最终结果。
- 拆分求和区间：（该步骤递归进行，$x$ 代表当前求和区间右端点）
- $x$ 的第一位为 $d_1$，第一位小于 $d_1$ 的构成一组（该部分可以直接求数字和，具体方法见 用数学期望计算区间内整数各数位的和的和）；
- 第一位等于 $d_1$ 的分成两部分：
- 第一部分为第一位等于 $d_1$ 的数，其中每个数的第一位被直接删除（该部分进入递归循环）；
- 第二部分为 $d_1$ 乘上第一部分包括的数的个数。
- 当 $x$ 为 $k \cdot 10^{m} - 1$ 的形式或一位数时，直接求和，结束递归。
以 $n = 345$ 为例：
- 求 $[0, 345]$ 的数字和：
- 求 $[0, 299]$ 的数字和：
- 共有 $300$ 个数，可得后两位数字和为 $4.5 \times 300 \times 2 = 2700$；
- 首位在 $[0, 2]$，期望为 $1$，所以首位数字和为 $1 \times 300 = 300$；
- 因此 $[0, 299]$ 的数字和为 $2700 + 300 = 3000$。
- 求 $[0, 45]$ 的数字和：
- 求 $[0, 39]$ 的数字和，为 $240$。
- 求 $[0, 5]$ 的数字和，为 $15$。
- $4 \times 6 = 24$。
- 所以 $[0, 45]$ 的数字和为 $240 + 15 + 24 = 279$。
- $3 \times 46 = 138$。
- 求 $[0, 299]$ 的数字和：
所以 $[0, 345]$ 的数字和为 $3000 + 279 + 138 = 3417$。
参考代码
2132E. Arithmetics Competition
题意
有两个数组 $a$ 和 $b$，$a$ 的长度为 $n$，$b$ 的长度为 $m$。
给出 $q$ 次询问，每次询问包括三个数 $x, y, z$，表示在 $a$ 中至多选择 $x$ 个数，在 $b$ 中至多选择 $y$ 个数，总共选择 $z$ 个数，求选择的数字之和的最大值。
题解
首先，考虑暴力解法。排序两个数组，每次询问的每次选择都选择可以选择的最大数字。
显然，这样是无法通过问题的。那么，如何优化呢？
我们最终在同一个数组里选择的数一定是在一个连续区间内，如果我们能计算出这个区间，那么就可以通过 $O(n)$ 前缀和预处理解决问题。
设选择 $p$ 个 $a$ 中的数，总共选择 $z$ 个数（可以计算出选择 $b$ 中的元素数 $q$）时选择的数字之和的最大值为 $f(p, z)$，该值可以在 $O(1)$ 时间内计算出来。
发现当 $z$ 不变时 $f$ 是一个单峰函数，于是采用三分搜索求解。