Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-E. Sum of Digits (and Again)（什么时候不适合反向思考？）

题目大意

题目描述
对于一个严格大于 0 的正整数 $x$，按以下过程构造字符串 $S(x)$：

1. 初始字符串为空。

2. 将 $x$ 的十进制表示（无前导零）追加到字符串右侧。

3. 如果 $x \le 9$，过程结束；否则，将 $x$ 替换为其各位数字之和，并返回步骤 2 继续执行。

例如：

• $S(75)$ 为 “75123”（75 的数位和为 12，12 的数位和为 3，依次拼接为 75 + 12 + 3 = 75123）。

• $S(30)$ 为 “303”（30 的数位和为 3，拼接为 30 + 3 = 303）。

• $S(9)$ 为 “9”。

现在给定一个由数字组成的字符串 $s$，要求重新排列该字符串中的所有字符，使其能够构成某个正整数 $x$ 对应的生成字符串 $S(x)$。不允许添加或删除字符。如果给定的 $s$ 已经是合法的 $S(x)$，可以保持不变。数据保证一定存在至少一种合法的排列方式。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例包含一行数字字符串 $s$（$1 \le |s| \le 10^5$）。
所有测试用例中 $|s|$ 的总和不超过 $10^5$。

输出格式
对于每个测试用例，输出重排后的字符串。如果有多个合法答案，输出其中任意一个即可。

样例

Input:
5
12735
1
011
99999299999999299959999999999999
4621467

Output:
75123
1
101
99999999999999999999999999992529
6442167

样例解释

• 第一个样例 12735：重排为 75123，对应 $x = 75$ 的生成结果（75 -> 12 -> 3）。

• 第二个样例 1：重排为 1，对应 $x = 1$ 的生成结果。

• 第三个样例 011：重排为 101，对应 $x = 10$ 的生成结果（10 -> 1）。

思路讲解

首先，对于重排问题，原来的顺序是一点用都没有的，我们只考虑原来的个数！也就是 freq 统计一手频数。

说白了就是，字符串的最后一位数状态很少，但是光枚举那个东西想反推出来一整个答案，难如登天。

说白了，一个东西的状态少，不一定就是去枚举他，因为枚举的越少，难度一般来说越大。所以说，我们一般要枚举的是不多不少的东西。

因此，这个不多不少的东西，是什么呢？结合这个不太好反向思考的这个特性，我们发现，可以枚举第一部分的这个数位和。枚举了第一部分的数位和以后，你会发现，后面的东西全部都定下来了。那后面的东西都定下来了，确定是否能够取得第一部分的这个数位和，是不是也是非常 easy 的呢？

AC代码

源代码

心路历程（WA，TLE，MLE……）