自动搬运

查看原文

来自洛谷，原作者为

	Stay_Hungry 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:34:02，当前版本为作者最后更新于2020-07-27 15:14:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我是做了$HHHOI$上的一道极为相似的题才来此拿双倍经验的

$O(nm)$暴力想必大家都会，而问题的瓶颈在于$+-$操作的进位，如果有组数据是$n = 5e7, m = 5e7$
$11111111......1111$
$+-+-+-+-.......+-+-$
绝对原地爆炸，我在模拟赛中即使是判了相邻$+-$操作消除部分操作还是只有$73pts$

题意明了，直接上$O(m)$做法（其实我也很好奇上限$O(nm)$的暴力是咋过的）

不难发现，每次操作针对的，都只是最后一位，所以只需在最后一位打延迟标记，$\times$的时候向后推一位$0$，$/$的时候把延迟标记向前推，$+-$时就直接在最后一位上加减即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int f[N * 2], n, m, r; char c;
signed main() {
	ios :: sync_with_stdio(false);
	cin >> n >> m; r = n;
	for(int i = 1; i <= n; ++i) cin >> c, f[i] = c - '0';
	while(m --) {
		cin >> c;
		if(c == '*') f[++ r] = 0;  //向后拓展一位
		else if(c == '+') ++ f[r];  //直接累加
		else if(c == '-') -- f[r];
		else f[r - 1] += f[r] >> 1, --r;  //考虑二进制下进位
        // 这里没必要修改f[r]
	}
	for(int i = r; i > 1; --i) {
		f[i - 1] += f[i] >> 1;
		f[i] = f[i] & 1;
	}  // 一次把延迟标记向前推完
	for(int i = 1; i <= r; ++i) cout << f[i]; cout << "\n";
	return 0;
}