比赛链接

Solved by Potassium & nikkukun.

给一个不超过 $10^5$ 位的十进制数，拆成不超过 $25$ 个回文正数（不含前导零）的和。

例如 $2020 = 2002 + 11 + 7$。

每次取 $n$ 的前 $\left\lceil \dfrac n2 \right\rceil$ 位 $a$ 出来，并反过来接在后面变成 $aa^r$ 作为本次减的数。如果 $n < aa^r$，则将 $a$ 减去 $1$ 变为 $b$ 后，以 $bb^r$ 作为本次减的数。

观察发现这样操作每次会减少一半的位数，只要 $O(\log \log n)$ 次操作就能分解完毕。

Solved by nikkukun.

有 $n$ 个箱子，每个箱子用金钥匙或银钥匙都可以开，开启时间为 $t_i$。金钥匙只有一个，不能同时开几个箱子；银钥匙有 $k$ 个，可以同时开多个箱子。求打开所有箱子的最短时间。

排序后贪心用金钥匙开时间最小的 $n-k$ 个箱子即可。