题目大意
题目描述
对于一个严格大于 0 的正整数 x，按以下过程构造字符串 S(x)：
-
初始字符串为空。
-
将 x 的十进制表示（无前导零）追加到字符串右侧。
-
如果 x≤9，过程结束；否则，将 x 替换为其各位数字之和，并返回步骤 2 继续执行。
例如：
现在给定一个由数字组成的字符串 s，要求重新排列该字符串中的所有字符，使其能够构成某个正整数 x 对应的生成字符串 S(x)。不允许添加或删除字符。如果给定的 s 已经是合法的 S(x)，可以保持不变。数据保证一定存在至少一种合法的排列方式。
输入格式
第一行包含一个整数 t（1≤t≤104），表示测试用例的数量。
每个测试用例包含一行数字字符串 s（1≤∣s∣≤105）。
所有测试用例中 ∣s∣ 的总和不超过 105。
输出格式
对于每个测试用例，输出重排后的字符串。如果有多个合法答案，输出其中任意一个即可。
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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 写法比较好）
1
2
3
4
5
6
| 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
源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
#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;
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;
}
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);
}
ans+=to_string(d);
cout<<ans<<"\n";
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;
}
|
心路历程（WA，TLE，MLE……）