首页 > > 程序设计 > C/C++ >

时间复杂度

2019-08-26 05:36:18来源：博客园阅读 ()

时间复杂度

题目

【题目描述】

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！

下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

F i x y
    循环体
E

其中F i x y表示新建变量

“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“Θ”的概念。

【输入格式】

输入文件第一行一个正整数

接下来每个程序的第一行包含一个正整数 $代表程序行数，字符串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w)表示复杂度为n^w，其中w是一个小于100的正整数（输入中不包含引号），输入保证复杂度只有O(1)和O(n^w) 两种类型。$

接下来

程序行若以E开头，则表示循环体结束。

【输出格式】

输出文件共

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

【输入样例】

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

【输出样例】

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

【样例解释】

第一个程序

第二个程序

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环，

第五个程序两个一重循环，

第六个程序第一重循环正常，但第二重循环开始即终止（因为

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 x 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模】

对于

解析

很恶心有意思的一道模拟题。

首先，如何计算时间复杂度呢？

根据题意以及样例，可以发现，在当前循环有效的情况下，当且仅当x为数字y为n时w才会+1（仅循环嵌套时w才会+1，两个不嵌套的循环的w是不相关的）。

知道如何计算时间复杂度后，便可以开始模拟了。

用work()函数来处理每行：

先读入一个字符，如果是'F'，

则令n[++f]=true(n代表第f个循环是否运行)。
然后读入i x y(同题意)，并用name数组记录字母i，如果当前字母出现过且没被销毁，则令ok=false，标记错误。
在读入y时，
如果y='n'，则
1、如果x='n'：ans--(ans表示w)，因为如果x、y均为'n'，循环就只运行1次，所以ans是不会增加的(后面ans++，这里ans--就可以让ans不变)。
2、如果n[f-1](上一个循环可以运行，则这个循环也可以运行)：ans++，bj[f]=true(bj[f]表示第f层循环时ans自加了，后面在销毁循环时可以找到该循环令ans--，以免影响其他循环)。
如果y为数字，则判断x与y的大小，如果y大，那么循环不会进行，就令n[f]=false。
在'F'指令的最后，要记得判断如果n[f-1]=false(即上一个循环不进行)，则令n[f]=false(当前循环也不会进行)。

如果是'E'，

令maxn=max(maxn,ans)，记录最大值。
如果bj[f](意义见'F'指令)，令bj[f]=false，ans--。
最后记得f--。

不要忘了在每个work()函数开头加上n[0]=true，不然会出现玄学错误。

所有work()处理完后，如果f不为0('F'指令与'E'指令数量不同)或!ok，直接输出ERR。

最后只需要判断w与maxn是否相等就可以了。

结束了？并没有，这题为什么恶心有趣？就在于输入处理，

在读入字符(串)时，读完后还得多读一遍来读入空格和换行（害本蒟蒻改了一下午！）。

所以在代码中会看到很多莫名其妙的读入，这个就自行理解吧（本蒟蒻也没办法QAQ）。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <stack>
using namespace std;
int t,l,f,temp,ans,maxn;
char ch,x,y,name[101];
bool bj[101],ok,n[101];
string O;
void work()
{
    n[0]=true;
    ch=getchar();getchar();
    if(ch=='F')
    {
        int numx=0,numy=0;
        n[++f]=true;
        ch=getchar();
        getchar();
        for(int i=1;i<f;i++)
            if(name[i]==ch) ok=false;
        name[f]=ch;
        x=getchar();
        if(x!='n') while(x>='0'&&x<='9')
        {
            numx=(numx<<1)+(numx<<3)+x-'0';
            x=getchar();
        }
        else getchar();
        y=getchar();
        if(y=='n')
        {
            if(x=='n') ans--;
            if(n[f-1])
            {
                ans++;
                bj[f]=true;
            }
            else n[f]=false;
            getchar();
        }
        else while(y>='0'&&y<='9')
        {
            numy=(numy<<1)+(numy<<3)+y-'0';
            y=getchar();
        }
        if(numy!=0&&(numy<numx||x=='n')) n[f]=false;
        if(!n[f-1]) n[f]=false;
    }
    else
    {
        maxn=max(ans,maxn);
        if(bj[f])
        {
            bj[f]=false;
            ans--;
        }
        f--;
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(bj,false,sizeof(bj));
        f=0,ans=0,maxn=0,ok=true;
        cin>>l>>O;scanf("\n");
        for(int i=1;i<=l;i++) work();
        if(f==0&&ok)
        {
            if(maxn==0)
            {
                if(O[2]=='1') cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
            else if(maxn<=9)
            {
                if(O.size()==6&&O[4]-'0'==maxn) cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
            else if(O.size()==7)
            {
                if(maxn/10==O[4]-'0'&&maxn%10==O[5]-'0') cout<<"Yes"<<endl;
                else cout<<"No"<<endl;    
            }
        }
        else cout<<"ERR"<<endl;
    }
    return 0;
}