CF852A Digits
23 July 2019 |
duanyll | Tags:
OI
题解
思维题
分类讨论
好久都没写过题解了…
题意
给定一个大整数$A$, 你需要对$A$执行$3$次操作, 一次操作为在$A$这个数中间添加若干加号, 让这个数变成若干个数的和, 举个例子$123450089$可以变成 $123+450+089$, 要求执行这$3$次操作之后$A$为$1$位数, 输出操作方案.
分析
$A$最多有$200000$位, 令$f(A)$表示$A$的各数位之和.
- 显然当$f(A)\leq198$时, 直接三次加满加号就行
- 当$f(A)=199$时, 加三次加号不行了, 第一步加成$199$, 第二步$1+99=100$, 第三步$1+00=1$
- 当$200\leq f(A)\leq288$时, 也是三次加满加号
-
对于$289\leq f(A)\leq999$的情况:
令
\[A = \overline{a_0a_1a_2\cdots a_n}, f(A)=\sum{a_i}\]以两位为间隔划分$A$, 假设$n$是奇数($A$有偶数位, 奇数位的情况同理), 令
\[X = \overline{a_0a_1} + \overline{a_2a_3} + \cdots + \overline{a_{n-1}a_n}\]错开一位, 令
\[Y = a_0 + \overline{a_1a_2} + \overline{a_3a_4} + \cdots + a_n\]两式相加并整理得
\[X+Y = 11f(A)-9a_n > 10f(A)\]令$X>Y$,
\[X>5f(A)\]考虑以下划分情况:
\[a_0+a_1+a_2+\cdots+a_n (f(A))\] \[\overline{a_0a_1} + a_2 + a_3 + \cdots + a_n\] \[\overline{a_0a_1} + \overline{a_2a_3} + \cdots + a_n\] \[\cdots\] \[\overline{a_0a_1} + \overline{a_2a_3} + \cdots + \overline{a_{n-1}a_n}(X)\]第一项是$f(A)$, 是三位数, 最后一项是$X>5f(A)$, 一定是四位数, 易知以上两项之间不会相差$81$, 那么以上划分情况中一定存在一种满足$1000\leq S\leq 1080$,这样的$S$可以在剩下的两次操作中变成一位数
-
再推广到$f(A)\geq1000$的情况
令
\[X = \overline{a_0a_1a_2} + \cdots + \overline{a_{n-2}a_{n-1}a_n}\] \[Y = a_0 + \overline{a_1a_2a_3} + \cdots + a_{n-1} + a_n\] \[Z = a_0 + a_1 + \overline{a_2a_3a_4} + \cdots + a_{n}\](假设$n$凑的出来以上序列, 凑不出来的类推), 有
\[X + Y + Z > 98f(A)\]令$X$最大(放缩一下,够用了)
\[x > 30f(A)\]再考虑刚才那样的依次合并连续两项的过程, 最开始是$f(A)$, 每次增加不超过$81$, 最后大于$30f(A)$, 位数多了一位, 一定存在一种情况满足$100\cdots000\leq S \leq 100\cdots080$, 可以两步解决.
代码
据说随机化第一步乱分很容易过(代码也短), 不过我没有写.
#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;
}