T1：三倍数
本题难度较大，“三倍数”的位数一定是 \(3\) 的倍数。
若 \(M = 10^6\)，则答案为？
\[100 \big|00\big|00 \geqslant 99 \big|99 \big| 99
\]
答案为 \(99\) 。
若 \(M\) 的位数 \(|M|\) 满足 \(|M| = 3n+r, ~1 \leqslant r < 3\)，则
\[1\big| 1\big| 1,~2\big| 2\big| 2, ~\cdots~, ~\underbrace{99\cdots 9}_{n \times 9} \big| 99\cdots 9\big| 99\cdots 9
\]
都是不超过 \(M\) 的三倍数。答案为 \(\underbrace{99\cdots 9}_{n \times 9}\) 。
考虑 \(|M|\) 为 \(3\) 的倍数的情形
若 \(M\) 分别为 \(123789456\)，\(987654321\)，则答案为？
\[123 \big| 789 \big| 456 \geqslant 123 \big| 123 \big| 123
\]
\[986 \big| 986 \big| 986 \leqslant 987 \big| 654 \big| 321 \leqslant 987 \big| 987 \big| 987
\]
答案分别为 \(123\) 和 \(986\) 。
将 \(M\) 写成三等分的形式 \(M_1M_2M_3\)，若 \(M_1 < M_2\)，或 \(M_1 = M_2\)，\(M_2 \leqslant M_3\)，则答案即为 \(M_1\)。
否则，答案应为 \(M_1 - 1\) 。
不难看出，本题需要考察高精度减法。
由于减数仅仅为 \(1\)，所以无需实现真正意义上的高精度减法。
只需实现好退位、错位即可。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int a[400], cnt;
int main() {
string m;
cin >> m;
int n = m.size();
if (n%3) {
cout << string(n/3, '9') << '\n';
return 0;
}
n /= 3;
if (m.substr(0, n) < m.substr(n, n) or (m.substr(0, n) == m.substr(n, n) and m.substr(n, n) <= m.substr(2*n))) {
cout << m.substr(0, n) << '\n';
return 0;
}
for (int i = n-1; i >= 0; --i) {
a[++cnt] = m[i]-'0';
}
--a[1];
for (int i = 1; i <= cnt and a[i] < 0; ++i) {
a[i] += 10;
a[i+1]--;
}
while (cnt > 1 and !a[cnt]) --cnt;
for (int i = cnt; i >= 1; --i) {
cout << a[i];
}
return 0;
}