题解 P2104 【二进制】

不愿WA的蒟蒻 · 2019-08-18 14:58:25 · 题解

deque(双端队列)解法

科普一下deque，

deque 即双端队列。

(deque，全名double-ended queue)是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列(即一个端点允许插入和删除，另一个端点只允许插入的双端队列)和输入受限的双端队列(即一个端点允许插入和删除，另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。

详见deque

回归本题，

先全压入deque

处理方面

，* 就用push_back(0);

，/ 就用pop_back();

，+ 就扫到0为止，1全变0，最前面的0变1；

，- 就扫到1为止，0全变1，最前面的1变0；

code：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    deque <char> rjz;
    cin>>n>>m;
    string yyy;
    cin>>yyy;
    for(register int i=0;i<n;++i){
        rjz.push_back(yyy[i]);
    }
    cin>>yyy;
    for(register int i=0;i<m;++i){
        if(yyy[i]=='*'){
            rjz.push_back('0');
        }
        else if(yyy[i]=='/'){
            rjz.pop_back();
        }
        else if(yyy[i]=='-'){
            int data=0;
            while(rjz.back()=='0'){
                ++data;
                rjz.pop_back();
            }
            rjz.pop_back();
            rjz.push_back('0');
            while(data--){
                rjz.push_back('1');
            }
        }
        else if(yyy[i]=='+'){
            int data=0;
            while(rjz.back()=='1'){
                ++data;
                rjz.pop_back();
            }
            rjz.pop_back();
            rjz.push_back('1');
            while(data--){
                rjz.push_back('0');
            }
        }
    }
    while(!rjz.empty()){
        cout<<rjz.front();
        rjz.pop_front();
    }
    cout<<endl;
    return 0;
}