题解 P2104 【二进制】

· · 题解

我是做了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;
}