题解 P3952 【时间复杂度 】

2019-06-30 11:03:29


这道题很显然是一道模拟

在我历经2个小时的调试中

终于写完了这篇AC代码

讲下具体做法吧

就是用一个栈来维护你的字符和你要算出来的时间复杂度

判断一些可能出现的情况

再打标记并且处理掉就OK啦!

模拟是一个noip常考考点

希望大家能多练习

谢谢观看!

#include<bits/stdc++.h>

using namespace std;

int t,n,flag,top,duan,tong[1004],fz[105],biaoji,ans,tot,shangdibiaoji;
char s[3000005];

inline void bian(int &flag,string a){
    if(isdigit(a[4])&&isdigit(a[5])) flag=(a[4]-'0')*10+(a[5]-'0');
    else flag=a[4]-'0';
}

inline void init(string a){
    if(a[2]=='n'){
        bian(flag,a);
    }
    else flag=0;
}

void zhuanhua(int &aa,string a){
    int len=a.length();
    if(len==1){
        aa=(a[0]-'0');
        return;
    }
    if(len==2){
        aa=(a[0]-'0')*10+(a[1]-'0');
        return;
    }
}

inline void check(){
    top=0;tot=0;ans=0;duan=0;shangdibiaoji=0;
    while(n--){
        char opt;
        cin>>opt;
        if(opt=='F'){
            char buf;
            cin>>buf;
            if(tong[buf]){
                shangdibiaoji=1;
                top+=10000;
            }
            tong[buf]=1;
            s[++top]=buf;
            string a,b;
            int aa,bb;
            cin>>a>>b;
            if(duan){
                fz[top]=fz[top-1];
                continue;
            }
            if(a=="n"&&b=="n"){
                fz[top]=fz[top-1];
                continue;
            }
            if(a=="n"){
                fz[top]=fz[top-1];
                duan=1;
                biaoji=top-1;
                continue;
            }
            if(b=="n"){
                fz[top]=fz[top-1]+1;
                continue;
            }
            if(a!="n"&&b!="n"){
                zhuanhua(aa,a);zhuanhua(bb,b);
                if(aa>bb){
                    duan=1;
                    biaoji=top-1;
                    continue;
                }
                fz[top]=fz[top-1];
                continue;
            }
        }
        else{
            if(top==0){
                shangdibiaoji=1;
                top+=10000;
            }
            ans=max(ans,fz[top]);
            if(!duan) fz[top]=0;
            tong[s[top--]]=0;
            if(biaoji==top) duan=0;
        }
    }
    if(shangdibiaoji){
        cout<<"ERR\n";
        return;
    }
    if(top){
        cout<<"ERR\n";
        return;
    }
    if(ans==flag){
        cout<<"Yes\n";
        return;
    }
    else cout<<"No\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--){
        memset(tong,0,sizeof(tong));
        cin>>n;string a;
        cin>>a;
        init(a);
        check();
    }
    return 0;
}