Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-E. Sum of Digits (and Again)（什么时候不适合反向思考？） · znzryb
## 题目大意
**题目描述**
对于一个严格大于 0 的正整数 $x$，按以下过程构造字符串 $S(x)$：
1. 初始字符串为空。
1. 将 $x$ 的十进制表示（无前导零）追加到字符串右侧。
1. 如果 $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 的呢？
实现上来说：（还是用这个 while condition 写法比较好）
```cpp
ll d=sum;
while (d>9) {
ans+=to_string(d);
d=count_digit(d);
}
ans+=to_string(d);
```
## AC代码
AC
[https://codeforces.com/contest/2204/submission/367073785](https://codeforces.com/contest/2204/submission/367073785)
::: 源代码
```cpp
/**
* Problem: E. Sum of Digits (and Again)
* Contest: Educational Codeforces Round 188 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2204/problem/E
* Created: 2026-03-17 12:30:35
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
string s;
cin>>s;
if (SZ(s)==1) {
cout<<s<<"\n";
return;
}
vector<ll> freq(12);
for (auto ch:s) {
freq[ch-'0']++;
}
ll sum_digit=0;
for (int i=1;i<=9;++i) {
sum_digit+=freq[i]*i;
}
for (ll sum=1;sum<=sum_digit;++sum) {
vector<ll> lfreq=freq;
auto count_digit_minus=[&](ll x) {
ll res=0;
while (true) {
if (x==0) {
break;
}
res+=x%10;
lfreq[x%10]--;
x/=10;
}
return res;
};
auto count_digit=[&](ll x) {
ll res=0;
while (true) {
if (x==0) {
break;
}
res+=x%10;
x/=10;
}
return res;
};
ll d=sum;
while (d>9) {
d=count_digit_minus(d);
}
count_digit_minus(d);
if (*min_element(all(lfreq))<0) {
continue;
}
ll lsum_digit=0;
for (int i=1;i<=9;++i) {
lsum_digit+=lfreq[i]*i;
}
// #ifdef LOCAL
// if (sum==1) {
// debug1d(freq);
// debug1d(lfreq);
// debug(lsum_digit);
// debug(sum);
// }
// #endif
if (lsum_digit==sum) {
string ans;
for (int i=9;i>=0;--i) {
for (int j=1;j<=lfreq[i];++j) {
ans.push_back('0'+i);
}
}
ll d=sum;
while (d>9) {
ans+=to_string(d);
d=count_digit(d);
// if (d<=9) {
// ans+=to_string(d);
// break;
// }
}
ans+=to_string(d);
cout<<ans<<"\n";
// #ifdef LOCAL
// debug1d(freq);
// debug1d(lfreq);
// #endif
return;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2204/submission/367073785
*/
```
:::
## 心路历程（WA，TLE，MLE……）