题解 P2104 【二进制】
Insouciant21
·
·
题解
看完题面可以发现这题难点主要是 加减法的进退位
下面我们来找规律：
一个二进制数 10111111111
对其进行 +1 操作
即得到 11000000000
再来一个 10110101111
+1$ 后得到 $10110110000
可以发现当需要进位时将从后往前的第一个 0 变成了 1，其后的所有 1 都变成 0
再看减法
1101000101001000-1=1101000101000111
111101010100-1=111101010011
即需要退位时将从后往前的第一个 1 变成了 0，其后的所有 0 都变成 1
\times 2$ 在二进制中就像十进制中的 $\times 10$ 所以直接在后面添加一位 $0
在这里将每一位数字存储在 `vector` 中，通过递归来进行进退位
```
#include <bits/stdc++.h>
using namespace std;
vector<int> num;
long long n, m;
// 进位加
void add(int place) {
num[place]++;
if (num[place] == 2) { // 一直向前直到无需再进位
num[place] = 0;
add(place - 1);
}
return;
}
// 进位减
void reduce(int place) {
num[place]--;
if (num[place] == -1) {
num[place] = 1;
reduce(place - 1);
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
char a;
cin >> a; // 一位一位输入
num.push_back(a - '0');
}
for (int i = 0; i < m; i++) {
char oper;
cin >> oper;
switch (oper) {
case '+':
add(num.size() - 1);
break;
case '-':
reduce(num.size() - 1);
break;
case '*':
num.push_back(0);
break;
case '/':
num.pop_back();
break;
default:
break;
}
}
for_each(num.begin(), num.end(), [](int x) { cout << x; }); // for_each 输出 （）
cout << endl;
return 0;
}
```