NOIP2017 时间复杂度

很久以前就写了这题，又想起来这题练码力，重新写一下，但是挂了很多次，加起来写加调用了快3h，考场上我已经死翘翘了，第一份代码50,真是菜啊。这题其实就是一个模拟，不管用栈模拟还是用递归写都可以，我感觉递归更好操作一些，写了递归。思路其实很简单，代码挺多细节。数字的读入参考快读。

#include<iostream>
#include<cstring>
#include<map>
#include<cstdio>
using namespace std;
const int N=1e4+5;
char c[N];
map<char,int> id;
int flag,tot,n;
int work(int x);
struct node{
    int x,y,pd;
};
node solve(int x,int s1,int s2){
    int w=work(x-1),dono,ans=0;if(s1==-1&&s2==-1) dono=0;
    else if(s1==-1) dono=1;
    else if(s2==-1) ans++;
    else if(s1<=s2) dono=0;
    else if(s1>s2) dono=1;
    node t;t.x=w;t.y=w;t.pd=ans;if(dono==1) t.y=0;
    return t;
}
int work(int x){
    if(tot==24){
        int x=1;
    }
    if(tot==n+1){flag=1;return -1;}
    tot++;int s1=0,s2=0,all=0,now,ans=0;
    if(n==x){
        while(tot!=n+1){
            int t=work(x-1);if(t==-1) flag=1;
            ans=max(ans,t);
        }return ans;
    }
    char pd,s;cin>>pd;if(pd==‘E‘) return -1;cin>>s;
    if(id[s]) flag=1;else id[s]=1;
    if(pd==‘F‘){
        char c=getchar();for(;(c>‘9‘||c<‘0‘)&&c!=‘n‘;c=getchar());
        if(c==‘n‘) s1=-1;else while(c>=‘0‘&&c<=‘9‘) all=all*10+c-‘0‘,c=getchar();
        if(!s1)s1=all;all=0;
        c=getchar();for(;(c>‘9‘||c<‘0‘)&&c!=‘n‘;c=getchar());
        if(c==‘n‘) s2=-1;else while(c>=‘0‘&&c<=‘9‘) all=all*10+c-‘0‘,c=getchar();
        if(!s2)s2=all;all=0;
        
        node w=solve(x,s1,s2);now=w.y;int xianzai=w.pd;
        
        while(w.x>=0){w=solve(x,s1,s2);now=max(now,w.y);}
        if(w.x==-1){id[s]=0;if(now==-1) return 0+xianzai;return now+xianzai;}
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        id.clear();flag=0;tot=0;
        scanf("%d",&n);scanf("%s",c);
        int fazadu=1;if(c[2]==‘1‘) fazadu=0;else{
            int i=4,all=0;while(c[i]>=‘0‘&&c[i]<=‘9‘) all=all*10+c[i]-‘0‘,i++;
            fazadu=all;
        }int t=work(n);
        if(flag) printf("ERR\n");
        else if(t==fazadu) printf("Yes\n");
        else printf("No\n");
    }
}

NOIP2017 时间复杂度

原文：https://www.cnblogs.com/BLUE-EYE/p/9574389.html