题解：P11449 [USACO24DEC] Roundabount Rounding B

1. 大致题意

现在有两种对数进行操作的方法：

1. “直接四舍五入”，即看这个数的首位（最高位）。令这个数的位数为 $p$，若首位 $\ge 5$，则最终答案为 $10^p$；否则，最终答案为 $0$。
2. “链式四舍五入”，即从最低位开始到最高位结束，每位都依次进行四舍五入的操作并且有进位。

我们举一个例子，将 $48$ 分别进行两种四舍五入：

1. “直接四舍五入”，因为 $4 < 5$ 所以答案为 $0$。
2. “链式四舍五入”，答案为 $100$。

现在给你 $t$ 组测试数据，每组数据给你一个数 $n$，求从 $2$ 到 $n$ 的数中两种四舍五入的结果不一样的数的个数。

2. 解题思路

我们稍微分析一下就会发现，“链式四舍五入”得到的结果一定大于等于“直接四舍五入”的结果。

还是令 $n$ 的位数是 $p$，则得到的两个答案一定是 $0$ 和 $10^{p+1}$ 中的。两种四舍五入唯一不同的地方其实就是“链式四舍五入”可以进位，即操作的数 $\ge 5$ 时会给下一位进位。

稍加思考就会发现，答案一定是 $444\dots45$ 到 $4999\dots9$ 之间的。我在代码里采用了稍加打表的方法。

3. 代码实现

我掉了数不胜数的坑，一点要避开啊！

(1) 坑点一

注意比它位数少的也要算上，建议预处理。
我是这么做的：

1. const int a[] = {0, 0, 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555};
2. for (int i = 1; i <= 11; i++) pre[i] = pre[i - 1] + a[i];

(2) 坑点二

注意要判断 $n$ 与 $4999\dots9$ 的大小。
我是这么做的：

1. const int maxx[] = {0, 0, 49, 499, 4999, 49999, 499999, 4999999, 49999999, 499999999, 4999999999, 49999999999};
2. min(maxx[digit], n);

(3) 坑点三

注意要判断 $n$ 与 $444\dots45$ 的大小。
我是这么做的：

1. const int minn[] = {0, 0, 45, 445, 4445, 44445, 444445, 4444445, 44444445, 444444445, 4444444445, 44444444445};
2. if (n < mn) cout << pre[digit-1] << "\n";

我们回到代码，有点冗余，但懒得改了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int a[] = {0, 0, 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555};
const int minn[] = {0, 0, 45, 445, 4445, 44445, 444445, 4444445, 44444445, 444444445, 4444444445, 44444444445};
const int maxx[] = {0, 0, 49, 499, 4999, 49999, 499999, 4999999, 49999999, 499999999, 4999999999, 49999999999};
int pre[15];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for (int i = 1; i <= 11; i++) pre[i] = pre[i - 1] + a[i];
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        if (n < 10) {
            cout << "0\n";
            continue;
        }
        int digit = log10(n) + 1;
        int mn = minn[digit];
        if (n < mn) cout << pre[digit-1] << "\n";
        else {
            int x = 0;
            for (int i = 1; i <= digit; i++) x *= 10, x += 4;
            x += 1;
            cout << min(maxx[digit], n) - x + 1 + pre[digit-1] << "\n";
        }
    }
    return 0;
}