题解 P2104 【二进制】

luckydrawbox · 2021-02-10 20:07:27 · 题解

题意

模拟二进制加减乘数操作。

分析

先考虑数据存储：

我们可以用一个 int 数组 a 来存这个二进制数的每一位，用一个 string 字符串 s 来存最后的加减乘除运算，但一定一定要注意：有一种极限情况，即 n、m 都是 5* 10^6，且 s 中每个操作都是 * ，那么这个二进制数的位数就会达到 10^7！所以定义时千万不要少了，不然你就会看到两个紫色的RE。

接下来先解决简单的乘和除的操作：

• 如果是乘法，我们直接 ++n 就行了，因为这样就相当于在 a 数组的末尾加了一位，也就是二进制的左移（* 2），不过还要来一步 a[n]=0，不然你新加的 a_n 可能是上次运算留下的 1。

if(s[i]=='*')a[++n]=0;

• 如果是除法，我们只需 n-- 就OK了，相当于在 a 数组的末尾减了一位，也就是二进制的右移（/2）。

if(s[i]=='/')n--;

然后处理一下难亿点的加和减：

我们定义一个函数 void jia_jian(int x,int f)，进行加减运算，其中 x 代表当前在第 x 位，f 的值为 1 或 -1，即加或减，我们先把 a_x 加上 f，如果此时的 a_x 不是 0 或 1，那么我们就进行进位和借位，可以发现，进行进位时 a_x=2，进行借位时 a_x=-1，此时，我们就可以递归，把运算传到下一位去，即 jia_jian(x-1,f)，因为题目中说 数据保证+，-操作不会导致最高位的进位与退位 ，所以不用考虑边界。然后，我们需要把进位的 a_x 赋值为 0，把借位的 a_x 赋值为 1，找规律可得二者都可以表示为 a[x]-=2*f。这样我们就得到了加减运算的通用函数：

void jia_jian(int x,int f)
{
    a[x]+=f;
    if(a[x]>1||a[x]<0)
    {
        a[x]-=2*f;
        jia_jian(x-1,f);
    }
}

剩下的就不用说了，直接上代码：

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;//千万千万不要少定义
int n,m,a[N];
string s;
void jia_jian(int x,int f)
{
    a[x]+=f;
    if(a[x]>1||a[x]<0)//判断a[x]是否需要进位或借位
    {
        a[x]-=2*f;
        jia_jian(x-1,f);//向下一位进位或借位
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%1d",&a[i]);//每次读入一位
    }
    cin>>s;
    for(int i=0;i<m;i++)
    {
        if(s[i]=='*')a[++n]=0;
        if(s[i]=='/')n--;
        if(s[i]=='+')jia_jian(n,1);
        if(s[i]=='-')jia_jian(n,-1);
    }
    for(int i=1;i<=n;i++)printf("%d",a[i]);
    return 0;
}