P3952 时间复杂度 （模拟）

P3952 时间复杂度

分析：

第一眼，诶这道题不是弱智吗？直接模拟不就好了。

胡乱分析了一下，就开始盲敲，重构了好多次代码，发现F与E的关系用栈维护比较方便，然后又打了一长串。

读入是真的麻烦，先读第一行，再读后面的几行。还要注意要读入数字不仅仅有一位。。。

解决完读入后，再通过栈与map判断是否有ERR的情况。

然后再用一次栈，模拟循环进出的过程，统计答案。

（思想简单，代码麻烦。。。）

以后遇到这种题，一定要构思好了再下手，否则会浪费很多时间，消磨了自己的耐心。

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define ri register int
int g[N][5],pre[N],cnt[N],op[N],num,flagg,n;
char bl[N];
void read()
{
    char ch=getchar();
    while(1){
        if(ch=='\n') break;
        if(ch=='^') flagg=1;
        while(ch<='9' && ch>='0'){
            num=num*10+ch-'0';
            ch=getchar();
        }
        ch=getchar();
    }
    for(ri i=1;i<=n;++i){
        int ge=0;
        for(ri j=1;j<=20;++j){
            char ch=getchar();
            if(ch=='\n') break;
            if(ch=='E') { op[i]=-1; ch=getchar(); break; }
            else if(ch=='F') op[i]=1;
            if(j==3) bl[i]=ch;
            int x=0,fll=0;
            while(ch<='9' && ch>='0'){
                x=x*10+ch-'0'; ch=getchar(); fll=1;
            }
            if(fll) g[i][ge++]=x;
            else if(ch=='n') g[i][ge++]=-1;
            if(ch=='\n') break;
        }
    }
}
int stk[N];
map<char,int> mp;
bool check()
{
    int fl=0,top=0;
    mp.clear();
    for(ri i=1;i<=n;++i){
        fl+=op[i];
        if(fl<0) return true;
        if(op[i]==-1) mp[bl[stk[top]]]=0,top--;
        else{
            if(mp[bl[i]]) return true;
            mp[bl[i]]=1,stk[++top]=i;
        }
    }
    if(top) return true;
    return false;
}
int solve(int i)
{
    if(g[i][0]!=-1 && g[i][1]==-1) return 1;
    if(g[i][0]!=-1 && g[i][1]!=-1 && g[i][0]<g[i][1] || g[i][0]==-1 && g[i][1]==-1) return 2;
    return 3;
}
int nex[N],opp[N];
int work()
{
    memset(stk,0,sizeof(stk));
    int top=0,now=0,ans=0;
    for(ri i=1;i<=n;++i){
        ans=max(ans,now);
        if(op[i]==-1) { if(opp[top]==1 && nex[top]==true) now--; top--;  continue; }
        int opt=solve(i);
        top++;
        if(opt==1){
            if(nex[top-1]==true || top==1) now++,nex[top]=true;
            else nex[top]=false;
        }
        else if(opt==2){
            if(top==1) nex[top]=true;
            else nex[top]=nex[top-1];
        }
        else nex[top]=false;
        stk[top]=i; ans=max(ans,now); opp[top]=opt;
    }
    if(ans==0){
        if(flagg) return false; return true;
    }
    if(ans==num) return true; return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(bl,0,sizeof(bl)); memset(stk,0,sizeof(stk)); memset(nex,0,sizeof(nex));
        scanf("%d",&n);
        num=0,flagg=0; read();
        if(check()) { printf("ERR\n"); continue; }
        if(work()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

View Code