题解 P2104 【二进制】
时律
·
·
题解
我看题解里有人用数组模拟栈……
为什么不用STL里实打实的栈呢？
恭喜你，TLE了
思路是这样的：
把二进制的每一位加入栈，最高位放在栈底，最高位放在栈顶
针对每个操作，如下：
**乘法**：
在栈顶加入一个$0$即可。
```
if(c=='*') q.push(0);
```
**除法**：
差不多，直接抛弃掉栈顶的数，因为是整除。
```
if(c=='/') q.pop();
```
加法：
所以此时用数组模拟栈的好处就来了。直接读取？
不！不要放弃$STL$！虽然说有点慢，但是还是能过此题的！~~本人亲自验证~~
考虑一下：如果最低位是$0$的话，就不用进位，直接弹出$0$加入$1$就好。
那如果是$1$怎么办？
先用一个变量$e$来记住弹出了多少个数。如果栈顶的数是$1$，就把它弹出，同时`e++`。
碰到$0$后，把这个$0$改为1，然后再加入$e$个$0$，因为前面全是$1$，然后都进了位变成$0$。
要是一直没碰到$0$怎么办？~~题目里没说，就不写了吧~~
```
if(c=='+')
{
int e=0;
while(q.top()==1)
e++,q.pop();
q.pop();q.push(1);
for(int i=1;i<=e;i++)
q.push(0);
}
```
**减法**：
类似加法，只不过是读到$1$时弹出，碰到$0$停止，并且加入的是$e$个$1$。
```
if(c=='-')
{
int e=0;
while(q.top()==0)
e++,q.pop();
q.pop();q.push(0);
for(int i=1;i<=e;i++)
q.push(1);
}
```
**完整代码**：
~~啊这道题好难啊用`cin`会TLE只好用字符数组了我要`string`啊~~
```
#include<bits/stdc++.h>
using namespace std;
stack<int> q;
char x[5000005];
int main()
{
int a,b;
char c;
scanf("%d%d",&a,&b);
getchar();
scanf("%s",x+1);
for(int i=1;i<=a;i++)
q.push(int(x[i]-'0'));
getchar();
scanf("%s",x+1);
for(int i=1;i<=b;i++)
{
c=x[i];
if(c=='*') q.push(0);
if(c=='/') q.pop();
if(c=='+')
{
int e=0;
while(q.top()==1)
e++,q.pop();
q.pop();q.push(1);
for(int i=1;i<=e;i++)
q.push(0);
}
if(c=='-')
{
int e=0;
while(q.top()==0)
e++,q.pop();
q.pop();q.push(0);
for(int i=1;i<=e;i++)
q.push(1);
}
}
string s;
while(!q.empty()) s+=char(q.top()+'0'),q.pop();
for(int i=s.size()-1;i>=0;i--)
putchar(s[i]);
}
```
**题外话**：
~~刚开始以为`n<=63`的我竟然用了`unsigned long long`，我是在干嘛，这可是黄题~~