首页 > 其他 > 详细

[NOIP2017] 时间复杂度

时间:2019-06-15 10:33:22      阅读:112      评论:0      收藏:0      [点我收藏+]

按题意模拟即可

关于题意

语法的检查是在整个程序执行前先进行的,因此即使在无法进入的循环中(x>y),变量名也不能重名

输入的数据要读完,不要中途 break(如果一边检查语法一边判断复杂度)

代码实现

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
int t,l;
char o[10];
char p[10],x[10],y[10];

void solve(){
    char c[1000]={0};// 栈 - 变量名
    int s[1000]={0},top=0;// 栈 - 每个循环复杂度的累加值
    int vis[30]={0},err=0,w=0;//n^w
    scanf("%d%s",&l,o);
    for(int i=1;i<=l;i++){
        scanf("%s",p);// 第一个字符
        if(p[0]=='F'){
            scanf("%s%s%s",p,x,y);// 全部当成字符串处理
            if(err)continue;
            // 计算 ix,iy
            int ix=0,iy=0;
            if(x[0]=='n')ix=0x3f3f3f3f;
            else for(int j=0;x[j];j++)ix=ix*10+x[j]-'0';
            if(y[0]=='n')iy=0x3f3f3f3f;
            else for(int j=0;y[j];j++)iy=iy*10+y[j]-'0';
            
            if(vis[p[0]-'a']){err=1;continue;}// 变量重名
            ++top,vis[p[0]-'a']=1,c[top]=p[0];// 入栈,标记变量名已用
            if(ix>iy)s[top]=-1;// 循环初始条件不满足,不会进入循环,记为 -1
            else if(ix==iy||iy<0x3f3f3f3f)s[top]=s[top-1];//O(1) 的循环复杂度
            else s[top]=s[top-1]==-1?-1:s[top-1]+1;
                // 如果上一个循环就已经被包含在某一个 ix>iy 的循环内,说明这个循环的复杂度也是不计的,则记为 -1
        }
        else {//p[0]=='E'
            if(!top){err=1;continue;}// 栈内没有'F'
            w=max(w,s[top]);// 更新答案
            s[top]=0,vis[c[top]-'a']=0,top--;// 出栈
        }
    }
    if(err||top)puts("ERR");// 如果语法错误或者栈非空
    else if(o[2]=='1')w==0?puts("Yes"):puts("No");
    else {
        int io=0;
        for(int i=4;isdigit(o[i]);i++)io=io*10+o[i]-'0';
        io==w?puts("Yes"):puts("No");
    }
}

int main(){
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}

[NOIP2017] 时间复杂度

原文:https://www.cnblogs.com/sshwy/p/11026354.html

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