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 = 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]--; 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]--; } 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"); } } }
|