2020 Petrozavodsk Winter Camp Day 5 I

Problem I. Sum of Palindromes

Statement

把给定的 $n$ 位数分解成不超过 $25$ 个回文数(不允许前导零)。有 $z$ 组测试数据。

$1 \leq z \leq 20000$

$1 \leq n \leq 10^5$

$\sum n \leq 3 \times 10^6$

Solution

跟国内比赛撞车了(2016 CCPC Changchun J),可能这些毛子出题人没怎么看国内比赛的题。

做法很简单,就是每次减掉小于当前数的最大的回文数。很显然每次可以减掉一半的长度,所以大概只需要 $\log n$ 次就够了。唯一的难点在于实现有点恶心,需要上高精度,不过我直接复制以前打 16 长春时候的代码了。(那个时候写得很丑不要骂我呜呜呜)

Code (By Nanako)

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 2e5;

char s[N];
int a[N], b[N], c[N];
int ans[55][N];
int cnt = 0;

int main () {
int T;
scanf("%d", &T);
for (int it = 1;it <= T;it++) {
cnt = 0;
scanf("%s", &s);
a[0] = strlen(s);
for (int i = 0;i < a[0];i++) {
a[a[0] - i] = s[i] - 48;
}
while (a[a[0]] == 0) a[0]--;

while (a[0] > 1) {
if ((a[0] == 2) && (a[2] == 1) && (a[1] == 0)) break;
for (int i = 1;i <= a[0];i++) b[i] = 0;
for (int i = a[0];i >= (a[0] + 1) / 2;i--) {
b[i] = a[i];
}
int p = (a[0] & 1) ? (a[0] + 1) / 2 : a[0] / 2 + 1;
b[p]--;
while (b[p] < 0) {
b[p] += 10;
b[++p]--;
}
//for (int i = a[0];i >= 1;i--) cout << b[i];cout << " b" << endl;
for (int i = 1;i <= a[0];i++) c[i] = 0;
c[0] = a[0];
for (int i = a[0];i >= (a[0] + 1) / 2;i--) {
c[i] = b[i];
}
for (int i = 1;i <= (a[0] + 1) / 2;i++) {
c[i] = b[a[0] - i + 1];
}
if (b[a[0]] == 0) c[1] = 9;
while (c[c[0]] == 0) c[0]--;
//for (int i = a[0];i >= 1;i--) cout << c[i];cout << " c" << endl;

ans[++cnt][0] = c[0];
for (int i = 1;i <= c[0];i++) {
ans[cnt][i] = c[i];
}

for (int i = 1;i <= a[0];i++) {
a[i] -= c[i];
if (a[i] < 0) {
a[i + 1]--;
a[i] += 10;
}
}
while (a[a[0]] == 0) a[0]--;
//for (int i = a[0];i >= 1;i--) cout << a[i];cout << a[0] << " a" << endl;
}
if (a[0] == 1) {
ans[++cnt][0] = 1;
ans[cnt][1] = a[1];
}
if (a[0] == 2) {
ans[++cnt][0] = 1;
ans[cnt][1] = 9;
ans[++cnt][0] = 1;
ans[cnt][1] = 1;
}

printf("%d\n",cnt);
for (int i = 1;i <= cnt;i++) {
for (int j = ans[i][0];j >= 1;j--) {
printf("%d", ans[i][j]);
}
printf("\n");
}
}
}