发布于  更新于 

CF852A Digits

分类讨论 思维题 题解 OI

好久都没写过题解了...

题意

给定一个大整数, 你需要对执行次操作, 一次操作为在这个数中间添加若干加号, 让这个数变成若干个数的和, 举个例子可以变成 , 要求执行这次操作之后位数, 输出操作方案.

分析

最多有位, 令表示的各数位之和.

  • 显然当时, 直接三次加满加号就行

  • 时, 加三次加号不行了, 第一步加成, 第二步, 第三步

  • 时, 也是三次加满加号

  • 对于的情况:

    以两位为间隔划分, 假设是奇数(有偶数位, 奇数位的情况同理), 令

    错开一位, 令

    两式相加并整理得

    ,

    考虑以下划分情况:

    第一项是, 是三位数, 最后一项是, 一定是四位数, 易知以上两项之间不会相差, 那么以上划分情况中一定存在一种满足,这样的可以在剩下的两次操作中变成一位数

  • 再推广到的情况

    (假设凑的出来以上序列, 凑不出来的类推), 有

    最大(放缩一下,够用了)

    再考虑刚才那样的依次合并连续两项的过程, 最开始是, 每次增加不超过, 最后大于, 位数多了一位, 一定存在一种情况满足, 可以两步解决.

代码

据说随机化第一步乱分很容易过(代码也短), 不过我没有写.

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
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 200010;

char A[MAXN];
char buffer[MAXN];
int n;

void final_step(int fA) {
if (fA != 199) {
sprintf(buffer, "%d", fA);
putchar(buffer[0]);
int tot = buffer[0] - '0', bufs = strlen(buffer);
for (int i = 1; i < bufs; i++) {
putchar('+');
putchar(buffer[i]);
tot += buffer[i] - '0';
}
putchar('\n');

sprintf(buffer, "%d", tot);
putchar(buffer[0]);
bufs = strlen(buffer);
for (int i = 1; i < bufs; i++) {
putchar('+');
putchar(buffer[i]);
}
putchar('\n');
} else {
puts("1+99");
puts("1+0+0");
}
}

void solve_by_split_2(int fA, int offset = 0, int find_line = 1000,
bool need_plus = false) {
int dfA = 0;
for (int i = offset; i < n; i += 2) {
dfA += A[i] - '0';
}
// 第一位要错开
if (dfA * 9 + fA < find_line) {
if (need_plus) putchar('+');
need_plus = true;
putchar(A[offset++]);
}

int i;
for (i = offset; i + 1 < n; i += 2) {
if (need_plus) putchar('+');
need_plus = true;
putchar(A[i]);
putchar(A[i + 1]);
fA += (A[i] - '0') * 9;
// 刚好凑出1000...00xx
if (fA > find_line) break;
}
for (i += 2; i < n; i++) {
putchar('+');
putchar(A[i]);
}
putchar('\n');
final_step(fA);
}

bool try_solve_3(int offset, int fA, int find_line) {
int dfA = 0;
for (int i = offset; i + 2 < n; i += 3) {
dfA += (A[i] - '0') * 99 + (A[i + 1] - '0') * 9;
}
if (dfA + fA >= find_line) {
bool need_add = false;
if (offset == 1) {
putchar(A[0]);
need_add = true;
} else if (offset == 2) {
putchar(A[0]);
putchar(A[1]);
need_add = true;
}
for (int i = offset; i + 2 < n; i += 3) {
if (fA + 999 > find_line) {
solve_by_split_2(fA, i, find_line, need_add);
return true;
}
fA += (A[i] - '0') * 99 + (A[i + 1] - '0') * 9;
if (need_add) putchar('+');
need_add = true;
putchar(A[i]);
putchar(A[i + 1]);
putchar(A[i + 2]);
}
}
return false;
}

int main() {
cin >> n;
cin >> A;
int fA = 0;
for (int i = 0; i < n; i++) {
fA += A[i] - '0';
}
if (fA <= 288) {
putchar(A[0]);
for (int i = 1; i < n; i++) {
putchar('+');
putchar(A[i]);
}
putchar('\n');
final_step(fA);
} else if (fA < 1000) {
solve_by_split_2(fA);
} else {
int line = 1;
while (line < fA) line *= 10;
if (!try_solve_3(0, fA, line)) {
if (!try_solve_3(1, fA, line)) {
try_solve_3(2, fA + (A[0] - '0') * 9, line);
}
}
}
return 0;
}