CF1907B YetnotherrokenKeoard 题解

· · 题解

CF1907B YetnotherrokenKeoard 题解

My Blog!

模拟题，题面还是挺清晰的。

Ideas

暴力：依次输入字符，遇到 b 或 B 就向前遍历是否有对应的小写字母或大写字母，有则删去。时间复杂度应该为 \mathcal{O}(Tn^2)。能过前两个点，但是个人感觉代码（闲着无聊可以进剪贴板看一看）比正解还难写。

正解：用两个栈分别存储小写字母和大写字母（这里我个人认为存其对应在字符串中的序号比较方便一些，因为接下来有关栈的操作并不用涉及到入栈的字符），若遇到字符 b 或 B 则将栈顶元素出栈，并将 b 或 B 标记为已删去，出栈元素标记为已删去（这时存序号的优势就体现出来了）。最后遍历一遍字符串，未标记为删除的输出即可。时间复杂度应该为 \mathcal{O}(Tn)。

Code

#include <bits/stdc++.h>
using namespace std;

bool is_pop[1000005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--){
        string str; cin>>str;
        for(int i=0; i<str.length(); i++) is_pop[i] = false; // 多测清空
        stack<int> S1, S2;
        for(int i=0; i<str.length(); i++){
            if(str[i]=='b'){
                if(!S1.empty()) is_pop[S1.top()] = true, S1.pop(); // 栈不为空则弹出栈顶，并标记为已删除
                is_pop[i] = true; // 标记字符 b 为已删除
            }
            else if(str[i]=='B'){
                if(!S2.empty()) is_pop[S2.top()] = true, S2.pop(); // 同理
                is_pop[i] = true;
            }
            else if(str[i]>='a' && str[i]<='z')
                S1.push(i); // 直接存其对应在字符串中的序号
            else if(str[i]>='A' && str[i]<='Z')
                S2.push(i);
        }
        for(int i=0; i<str.length(); i++)
            if(!is_pop[i]) cout<<str[i]; // 未被删除则输出
        cout<<"\n";
    }
    return 0;
}

Continue

你以为这就完了？

其实，这道题还有一种更短的做法：反序遍历输入的字符串，若遇到 b 或 B ，将其出现次数加 1。再在前面遇到可删去的对应字母就就将其出现次数减 1。如果无出现次数就将当前字符存入答案字符串中，最后将答案字符串反序并输出即可（目前最优解）。

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--){
        string str, ans; cin>>str;
        int b = 0, B = 0;
        for(int i=str.length()-1; i>=0; i--){
            if(str[i]=='b') b++; 
            else if(str[i]=='B') B++;
            else if(str[i]>='a' && str[i]<='z' && b) b--;
            else if(str[i]>='A' && str[i]<='Z' && B) B--;
            else ans += str[i];
        }
        reverse(ans.begin(), ans.end());
        cout<<ans<<"\n";
    }
    return 0;
}