P8431 「WHOI-2」彗星蜜月 题解
JackMerryYoung
·
·
题解
前言
这题真的恶心，赛时写挂了就拿了 10 pts.
正文
Subtask # 1
考虑做 f_i 的前缀最大，则遇到第一个大于 N 的 f_i 即可知答案为 i - 1.
复杂度 \mathcal{O}(TN^2), 能拿个 10 分。
Subtask # 2
考虑到 f_i 的前缀最大序列具有单调性，可以二分查找，复杂度为 \mathcal{O}(TN \log_2 N), 能拿个 40 分。
Subtask # 3 - # 4
嘿嘿，既然直接暴力会死，不妨考虑找规律。
比如 9930843 对应 1000498, 40032 对应 10004, 99995 对应 69998.
如果你还看不出规律，那就再找找。
大量数据证明以下结论：
（第几位都是从左到右, len 为该数字的总位数, a_i 表示该数字的第 i 位上的数）
1. 对于以连续的 9 开头的
设 pos 为第一个非 9 的数字的位置，那么答案即为：
一个 1, len - pos - 1 个 0, 一个 a_{pos} + 1, pos - 2 个 9 和一个 8.
证明：
翻转后的第一位必为 1, 否则一定包括了不合法情况。
有一个 $a_{pos} + 1$ 是因为可以加上去，所以不加白不加就直接加。
$pos - 2$ 个 $9$ 是对应 $pos$ 之前的几个非首位 $9$.
注意：最后一个 $8$ 其实是 $9 - 1$.
这是因为前面在现在的高位（原来的低位）上大赚，这里（现在的低位，原来的高位）会小赔，不得不减去 $1$.
---
该死，还有一种情况：
注意有可能出现最后一位之前都是 $9$ 的情况，需要特判。
既然前面的 $0$ 都没了，自然首位可以取代一个 $a_{pos} + 1$.
于是答案就是一个 $a_{pos} + 1$, 一堆 $9$, 最后输出一个 $8$.
### 2. 对于不以连续的 $9$ 开头的
这个就简单了，还是按照第一种的相同的思路思考，可以发现答案为：
一个 $1$, 一堆 $0$, 末尾输出原数首位。
证明留给读者思考，这里不在赘述啦。
### 3. 以零结尾
这个更简单，只需要减一即可。
证明：
以零结尾的数字翻转过来就一定比别人小了，那么前缀最大自然是上一个数的，而不可能是他的。
所以可以等效成求上一个数的答案。
---
至此，分类讨论结束。题目解法出来了。
复杂度 $\mathcal{O}(\sum{\log_{10} N})$, 十分优秀可以通过。
# 代码
``` cpp
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull T, N;
signed main()
{
cin >> T;
for(ull i = 1; i <= T; ++ i)
{
cin >> N;
bool is_all_nine = true;
ull cnt = 0, tmp[25];
memset(tmp, 0, sizeof(tmp));
ull tmpN = N;
if(N <= 8)
{
cout << N << endl;
continue;
}
if(N % 10 == 0)
-- N, -- tmpN;
while(N)
{
tmp[++ cnt] = N % 10;
N /= 10;
if(tmp[cnt] != 9)
is_all_nine = false;
}
if(is_all_nine)
cout << tmpN + 1 << endl;
else
{
if(tmp[cnt] == 9)
{
ull T, pos = 0;
for(ull i = cnt; i >= 1; -- i)
{
if(tmp[i] != 9)
{
T = tmp[i];
pos = i;
break;
}
}
if(pos == 1)
{
printf("%d", T + 1);
for(ull i = 1; i <= cnt - 2; ++ i)
putchar('9');
puts("8");
continue;
}
putchar('1');
for(ull i = 1; i <= pos - 2; ++ i)
putchar('0');
putchar('0' + T + 1);
for(ull i = 1; i <= cnt - pos - 1; ++ i)
putchar('9');
puts("8");
}
else
{
cout << 1;
for(ull i = 1; i <= cnt - 2; ++ i)
cout << 0;
cout << tmp[cnt] << endl;
}
}
}
return 0;
}
```
# 后言
就离谱，绿题也这么难...