题解 P2104 【二进制】

· · 题解

本题我们可以模仿栈的原理，虽然代码量稍微大了一点，但加减乘除复制粘贴一下就可以了

首先将读入的数据存入栈

int l1,l2,t,sta[10000100];//二进制初始长度，操作次数，栈（存储二进制） 
char a[10000010],b[10000010];//读入二进制，操作
l1=read();//读入二进制初始长度
l2=read();//读入操作次数 
scanf("%s%s",a+1,b+1);//读入二进制，操作 
for(ri i=1;i<=l1;i++)//存储初始的二进制（char转成int） 
        sta[++t]=a[i]-'0';

加法运算：

我们可以从后往前加，我们自然可以用标准的二进制来处理，但是每次的时间复杂度都是O(m)的，n次操作，如果全是加法我们就gg了

我们可以优化成这样：

in void doplus(){//切记：函数名字叫plus会CE 
    bool flag=false;//设置一个标记 
    for(ri i=t;i>=1;i--){//从后往前枚举，假如栈内的数为10010，可以按照1<-0<-0<-1<-0进行枚举 
        if(flag) break;//如果已经碰到了0，那就无法继续进位了，break 
        if(!sta[i]){//如果碰到0，停止进位 
            sta[i]=1;
            flag=true; 
        }
        else sta[i]=0;//如果是1，就就进位，如10111，是1就进位，到11000为止 
    }
}

减法运算：

直接类比加法，略改一下即可：

in void dominus(){
    bool flag=false;//设置一个标记 
    for(ri i=t;i>=1;i--){//从后往前枚举，假如栈内的数为10010，可以按照1<-0<-0<-1<-0进行枚举 
        if(flag) break;//如果已经碰到了1，那就不必继续退位了，break
        if(sta[i]){//如果是1，就可以退位，如10变成02，减成01 
            sta[i]=0;
            flag=true; 
        }
        else sta[i]=1;//所有在最后的0都会变成1，如11000，变成10111 
    }
}

乘法运算：

乘法就比较简单了，直接在后边加一个0就可以了：

in void domultiplication(){
    t++;
}

除法运算：

类比乘法：

in void dodivision(){
    sta[t--]=0;//这里不同的是，不但尾指针减一还要把这个数清0，如11先除后乘是10，否则变11 
}

附上代码：

#include<map>
#include<list>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define in inline
#define ri register int
using namespace std;
in int read(){//快读 
    char c=' ';
    while((c<'0')||(c>'9'))
        c=getchar();
    int v=0;
    while((c>='0')&&(c<='9')){
        v=v*10+c-'0';
        c=getchar();
    }
    return v;
}
int l1,l2,t,sta[10000100];//二进制初始长度，操作次数，栈的长度，栈（存储二进制） 
char a[10000010],b[10000010];//读入二进制，操作 
in void doplus(){//切记：函数名字叫plus会CE 
    bool flag=false;//设置一个标记 
    for(ri i=t;i>=1;i--){//从后往前枚举，假如栈内的数为10010，可以按照1<-0<-0<-1<-0进行枚举 
        if(flag) break;//如果已经碰到了0，那就无法继续进位了，break 
        if(!sta[i]){//如果碰到0，停止进位 
            sta[i]=1;
            flag=true; 
        }
        else sta[i]=0;//如果是1，就就进位，如10111，是1就进位，到11000为止 
    }
}
in void dominus(){
    bool flag=false;//设置一个标记 
    for(ri i=t;i>=1;i--){//从后往前枚举，假如栈内的数为10010，可以按照1<-0<-0<-1<-0进行枚举 
        if(flag) break;//如果已经碰到了1，那就不必继续退位了，break
        if(sta[i]){//如果是1，就可以退位，如10变成02，减成01 
            sta[i]=0;
            flag=true; 
        }
        else sta[i]=1;//所有在最后的0都会变成1，如11000，变成10111 
    }
}
in void domultiplication(){
    t++;///类比栈 
}
in void dodivision(){
    sta[t--]=0;//这里不同的是，不但尾指针减一还要把这个数清0，如11先除后乘是10，否则变11 
}
int main(){
    l1=read();//读入二进制初始长度
    l2=read();//读入操作次数 
    scanf("%s%s",a+1,b+1);//读入二进制，操作 
    for(ri i=1;i<=l1;i++)//存储初始的二进制（char转成int） 
        sta[++t]=a[i]-'0'; 
    for(ri i=1;i<=l2;i++){//进行操作 
        if(b[i]=='+') doplus();
        if(b[i]=='-') dominus();
        if(b[i]=='*') domultiplication();
        if(b[i]=='/') dodivision();
    }
    for(ri i=1;i<=t;i++)
        printf("%d",sta[i]);
    return ~~(0-0);
}