P9155 「GLR-R4」小满 题解

· · 题解

题目传送门

题意

有一个数 now，初始为 0。

现在有 n 个操作，每个操作有两种类型：

  1. 把 now 变为 now \times 2。
  2. 把 now 加上 d。

注意，多组数据测试。

解法

考虑开一个数 now 去模拟，但我们惊喜的发现 long long 炸了。

于是考虑高精度。

如果你手写一个高精度去模拟的话，会发现能拿 70 分。

然后自然的想到去优化这个高精度。

优化第一步：

十进制转二进制太麻烦还耗时？那直接用二进制高精！

优化第二步：

乘 2 太耗时？别忘了我们现在是二进制。乘 2 直接在后面加个 0 就行了。

优化第三步：

把 d 一个一个加上去进位太慢？那直接把 d 一股脑加到最后一位上，最后处理完后在统一进位。

然后就可以过了。没错，就是这么简单。（但我为什么赛时没想到呢？呜呜呜）

实现细节：

最后一位在哪里可以用一个指针 pos 表示，pos 一开始记得放在中间，前面的位置预留出来方便进位。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s = 0 , xi = 1;
    char op = getchar();
    while(op < '0' || op > '9'){
        if(op == '-') xi = -1;
        op = getchar();
    }
    while(op >= '0' && op <= '9'){
        s = (s << 1) + (s << 3) + op - '0';
        op = getchar();
    }
    return s * xi;
}
inline void print(int x){
    if(x < 0) putchar('-') , x *= -1;
    if(x < 10){
        putchar(x + '0');
        return;
    }
    print(x / 10);
    putchar(x % 10 + '0');
}
int n , t;
struct Int{
    int a[100005] = {} , pos = 50000 , l = pos;
    void test1(){
        pos++;
    }
    void test2(int d){
        a[pos] += d;
    }
    void end(){
        for(int i = pos;i;i--){
            a[i - 1] += a[i] / 2;
            a[i] %= 2;
        }
        for(int i = 1;i <= l;i++){
            if(a[i]){
                l = i;
                break;
            }
        }
        if(a[l] == 0) l = pos;
    }
    void write(){
        for(int i = l;i <= pos;i++){
            print(a[i]);
        }
        putchar('\n');
    }
};
signed main(){
//    freopen(".in" , "r" , stdin);
//    freopen(".out" , "w" , stdout);
    t = read();
    while(t--){
        Int a;
        n = read();
        for(int i = 1;i <= n;i++){
            int op = read();
            if(op == 1){
                a.test1();
            }
            else{
                a.test2(read());
            }
        }
        a.end();
        a.write();
    }
    return 0;
}