USACO Roundabount Rounding 题解

· · 题解

~哇噢，第一次打 USACO 就能写题解。~

思路

观察题目我们可以发现：对于一个整数数 x=\theta\times10^n(1\le\theta\lt10,n\in\mathbb{N})，如果 \theta\lt5，Bessie 就把它约成 0；如果 \theta\ge5，Bessie 就把它约成 10^{n+1}。

对于 Elsie 的“链式舍入”而我们可以把 x 分成两部分：x=a\times10^n+b\times10^{n-1}(a\in\mathbb{N},1\le a\lt10,1\le b\lt10)，当 a\neq4 时，情况是很简单的：

当 a=4 时我们来重点考虑：Elsie 约到第二高的数位时，b 已经发生了改变，如果此时 b\ge5，Elsie 就把 x 约成 10^{n+1}；如果此时 b\lt5，Elsie 还是把它约成 0。那接下来我们只要考虑 Elsie 会把 b\times10^{n-1} 约成几就行了。

Bessie 和 Elsie 舍入的方法我们都知道了，问题就迎刃而解了。

我们用一个布尔数组 \text{arr} 来表示 Elsie 与 Bessie 是否一致，那算 x 时只要把 \text{arr}_{b\times10^{n-1}} 取出就行了。

代码

注意点

  3. 注意数组越界。
#include <bits/stdc++.h>
using namespace std;

int t, cnt, ln=44; // ln 指最长的 N 从 44 开始因为这之前都没有不一致的

bitset<1000000009> arr;

pair<int, pair<int, int> > n[114514]; // 离线操作用来存 N 的数组 第一个是 N 第二个是读入时的编号 第三个是答案

int ans[114514]; // 离线操作用来存答案的数组

int main() {
    for(int xi=10; xi<=pow(10, 9)/5; xi*=10) { // 计算是否一致
        for(int i=xi*4+5; i<xi*5; i++) {
            if(i-xi*4>=xi/2 || (arr.test(i-xi*4) && i-xi*4>=xi/10)) { // 用上面的方法
                arr.set(i, true);
            }
        }
    }

    cin>>t;

    for(int i=0; i<t; i++) { // 看，离线操作是不是很烦
        cin>>n[i].first;
        n[i].second.first=i;
    }

    sort(n, n+t);

    for(int i=0; i<t; i++) {
        for(int j=ln+1; j<=n[i].first; j++) cnt+=arr.test(j);
        n[i].second.second=cnt;
        ln=n[i].first;
    }

    for(int i=0; i<t; i++) {
        ans[n[i].second.first]=n[i].second.second;
    }
    for(int i=0; i<t; i++) { // 输出
        cout<<ans[i]<<endl;
    }
    return 0;
}