题解 | #[NOIP2017]时间复杂度#

#include<bits/stdc++.h> using namespace std; int n; string k; int str_to_int(string a) { int ans=0; for(int i=0;i<a.length();i++) ans=ans*10+a[i]-'0'; return ans; } struct oppo{ char na; int s; oppo(char na,int s):na(na),s(s){}; }; stack v; bool MAP[205]; void work() { int sj=0,ans=0,all=0,flag=0; while(v.size()) v.pop(); memset(MAP,0,sizeof(MAP));

cin>>n>>k;
if(k!="O(1)"){
    for(int i=0;i<k.length();i++)
        if('0'<=k[i]&&k[i]<='9')
            sj=sj*10+k[i]-'0';
}
char t,a;
string b,c;
for(int i=1;i<=n;i++)
{
    cin>>t;
    if(t=='F')
    {
        cin>>a>>b>>c;
        int bb,cc;
        if(b=="n") bb=2020;
        else bb=str_to_int(b);

        if(c=="n") cc=2020;
        else cc=str_to_int(c);

        if(MAP[a]) flag=1;
        MAP[a]=1;

        if(cc-bb>100){
            v.push(oppo(a,all));
            all++;
            ans=max(all,ans);
        }
        else{
            if(bb>cc){
                v.push(oppo(a,all));
                all=-10000;
            }else{
                v.push(oppo(a,all));
            }
        }
    }
    else
    {
        if(v.size()){
            all=v.top().s;
            MAP[v.top().na]=0;
            v.pop();
        }else
            flag=1;
    }
}
if(flag||v.size()) puts("ERR");
else if(ans==sj) puts("Yes");
else puts("No");
return ;

} int T; int main() { cin>>T; while(T--) work(); return 0; }