自动搬运

查看原文

来自洛谷，原作者为

	寄风 现实中的你，是否很成功？

搬运于2025-08-24 22:45:52，当前版本为作者最后更新于2023-03-18 22:27:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

有一个数 $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;
}