首页 > 其他 > 详细

NOIp2017时间复杂度

时间:2019-10-15 01:23:35      阅读:91      评论:0      收藏:0      [点我收藏+]

比较复杂,调了好长时间不过以后再遇到这类题就好多了.

注意:

  1.栈里面存储时间复杂度,当循环不进去时赋值为-1000000(很小的数);

  2.即使已经判断为err也不能退出,要接着把数据读完,否则会影响到下一组读入的数据

  3.使用了 sscanf将字符转换为数字,不能写成x=sscanf();  sscanf(字符,"%d",&x);  

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
inline bool isnum(char x){ 
    return x>=0&&x<=9;
}
int main(){
    int testcase; scanf("%d",&testcase);
    while(testcase--){
        int L,top=0,ans=0,sta[105][3]; 
        char tm[10];
        bool flag=1,vis[200];
        memset(vis,0,sizeof(vis)); 
        sta[0][0]=sta[0][1]=0;
        scanf("%d%s",&L,tm);
        while(L--){
            char a[10],b[10],c[10],d[10];
            scanf("%s",a);
            if(a[0]==F){
                scanf("%s%s%s",b,c,d);
                sta[++top][0]=b[0];
                if(vis[b[0]]) flag=0;
                vis[b[0]]=1;
                if(isnum(c[0])&&isnum(d[0])){
                    int x,y;
                    sscanf(c,"%d",&x);
                    sscanf(d,"%d",&y);
                    if(x>y) sta[top][1]=-1000000;
                    else sta[top][1]=sta[top-1][1];
                }else if(isnum(c[0])){
                    sta[top][1]=sta[top-1][1]+1;
                }else if(isnum(d[0])){
                    sta[top][1]=-1000000;
                }else sta[top][1]=sta[top-1][1];
                ans=max(ans,sta[top][1]);
            }else if(a[0]==E){
                if(!top) flag=0; 
                vis[sta[top][0]]=0;
                top--;
            }
        }
        if(top) flag=0;
        if(!flag){
            printf("ERR\n"); continue;
        }
        flag=1;
        if(isnum(tm[2])){
            if(ans!=0) flag=0;
        }else{
            int i=4,t=0;
            while(isnum(tm[i])){
                t=t*10+tm[i]-0;
                i++;
            }
            if(ans!=t) flag=0;
        }
        if(!flag) printf("No\n");
        else printf("Yes\n");
    }
} 

 

NOIp2017时间复杂度

原文:https://www.cnblogs.com/huihao/p/11674900.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!