题解 P2104 【二进制】

redegg · 2018-11-07 10:49:49 · 题解

我们可以统一最后算出答案（而且不麻烦，因为保证了加减不进位）。

如果一个二进制数的下一位进了两位，那么我这一位一定进一位。

如果上一个二进制退了两位，我，这里一定也退了一位。

于是，此题的核心就是，我们可以像线段树的懒操作（区间加法用的那个），延迟更新答案。这样比较快。

我们存两个数组，应该是a数组，就是字符串，还有一个是b数组，b_i表示以i为最低位的串，一共加了多少个1。

我们加的话，直接在最低位上加就好了，如果我们要除的话，我们就要把最低位的“懒操作”标记数组b往更高位更新，也就是开头说的逢2进1的规则，但是会有一些细节和特殊情况：

设b_{i-1}是b_i的更高位。（最高位是b_1）

1.如果b_i+a_i \ge 0，那么b_{i-1} +=(b_i+a_i)/2就好了。

2.如果b_i+a_i \lt 0，那么b_{i-1} +=(b_i+a_i-1)/2。

为什么呢？因为大于0时，两数相加满足我为偶数时向前进1。而小于0时，我为奇数的时候前面就需要退位。

做完后开始计算真正的01串

最后从n到1（从低位到高位），每次就把这一位的懒操作向前传递，并且计算这一位的值（直接加上然后\%2就好了，当然要转换成正数）。

#include <bits/stdc++.h>
using namespace std;

int n,m;

int p0,p1;

int a[10000005];
int b[10000005];
char in[6000005];

int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",in+1);
    int op=0;
    for(int i=1;i<=n;i++)
        a[i]=in[i]-'0';
    scanf("%s",in+1);
    for(int i=1;i<=m;i++)
    {
        if(in[i]=='+')
        {
            b[n]+=1;
        }
        if(in[i]=='-')
        {
            b[n]-=1;
        }
        if(in[i]=='*')
        {
            n++;
            a[n]=0;
            b[n]=0;
        }
        if(in[i]=='/')
        {
            int an=a[n]+b[n];
            if(an<0)
                an-=1;
            b[n-1]+=(an)/2;
            n--;
        }
    }

    for(int i=n;i>=1;i--)
    {
        int an=a[i]+b[i];
        a[i]=((a[i]+b[i])%2+2)%2;
        if(an<0)
            an-=1;
        b[i-1]+=an/2;
    }

    for(int i=1;i<=n;i++)
        printf("%d",a[i]);
    printf("\n");
    return 0;
}