[洛谷P3652]时间复杂度lyh's blog

NOIP2017 D1 T2原题，难度较大的模拟

题目描述

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

F i x y
循环体
E

        其中F i x y表示新建变量 i（变量 i 不可与未被销毁的变量重名）并初始化为 x，然后判断 i 和 y 的大小关系，若 i 小于等于 y 则进入循环，否则不进入。每次循环结束后 i 都会被修改成 i +1，一旦 i 大于 y 终止循环。
        x 和 y 可以是正整数（x 和 y 的大小关系不定）或变量 n。n 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 100。
        “E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。
        注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“Θ”的概念。

输入输出格式

输入格式：

        输入文件第一行一个正整数 t，表示有 t（t≤10）个程序需要计算时间复杂度。每个程序只需抽取其中 F i x y和E即可计算时间复杂度。注意：循环结构允许嵌套。
        接下来每个程序的第一行包含一个正整数 L 和一个字符串，L 代表程序行数，字符串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w)表示复杂度为n^w，其中w是一个小于100的正整数（输入中不包含引号），输入保证复杂度只有O(1)和O(n^w) 两种类型。
        接下来 L 行代表程序中循环结构中的F i x y或者 E。程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y，其中 i 是一个小写字母（保证不为n），表示新建的变量名，x 和 y 可能是正整数或 n ，已知若为正整数则一定小于 100。
        程序行若以E开头，则表示循环体结束。

输出格式：

输出文件共 t 行，对应输入的 t 个程序，每行输出Yes或No或者ERR（输出中不包含引号），若程序实际复杂度与输入给出的复杂度一致则输出Yes，不一致则输出No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERR 。

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

输入输出样例

Sample input

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

Sample output

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明

【输入输出样例解释1】
        第一个程序 i 从 1 到 1 是常数复杂度。
        第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。
        第三个程序有一个 F 开启循环却没有 E 结束，语法错误。
        第四个程序二重循环，n 的平方的复杂度。
        第五个程序两个一重循环，n 的一次方的复杂度。
        第六个程序第一重循环正常，但第二重循环开始即终止（因为n远大于100，100大于4）。
        第七个程序第一重循环无法进入，故为常数复杂度。
        第八个程序第二重循环中的变量 x 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模与约定】
        对于 30%的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2 行一定为以 F 开头的语句，第 L/2+1行至第 L 行一定为以 E 开头的语句，L≤10，若 x、y 均为整数，x 一定小于 y，且只有 y 有可能为 n。
        对于50%的数据：不存在语法错误，L≤100，且若 x、y 均为整数，x 一定小于 y，且只有 y 有可能为 n。
        对于70%的数据：不存在语法错误，L≤100。
        对于100%的数据：L≤100。

题解

思路还是比较清晰的，用栈模拟循环嵌套过程，并不断记录已经存在的变量。详细过程见代码注释。

#include<iostream>
#include<string>
#include<cstring>
#include<stack>

using namespace std;
bool vis[26];
stack<int> sta;

inline int find(string x) {//字符串解析
    if (x[2] == '1')return 0;
    int s = 0;
    for (int i = 4; x[i] != ')'; i++)s = s * 10 + x[i] - '0';
    return s;
}

inline int solve(string x, string y) {//循环开始结束时间解析，0表示可执行的常数次数，1表示可执行的线性次数，-1表示不可执行
    if (x[0] == 'n' && y[0] == 'n')return 0;
    if (y[0] == 'n')return 1;//一定可以执行，与n成正比
    if (x[0] == 'n')return -1;//一定不能被执行
    if (x.length() > y.length())return -1;
    if (x.length() < y.length())return 0;//可以被执行，常数复杂度
    for (int i = 0; i < x.length(); i++)if (x[i] < y[i])return 0; else if (x[i] > y[i])return -1;
    return 0;//x=y，常数复杂度
}

int main() {
    int T, L, ans0, ans, depth;
    //T 样例数、L 行数、ans0 给定的时间复杂度答案(只存指数，O(1)存0)、ans 实际的答案(语法错误即为-1)，depth为有效深度
    //有效深度指可以被执行的并且与n有线性时间关系的循环嵌套层数，ans就是depth的最大值
    bool key;//是否会执行
    string op, n1, n2;
    char e;
    cin >> T;
    for (int ti = 0; ti < T; ti++) {
        cin >> L >> op;
        ans0 = find(op), memset(vis, 0, sizeof(vis)), ans = 0, key = true, depth = 0;//初始化
        while (!sta.empty())sta.pop();//清空栈
        for (int i = 0; i < L; i++) {//逐行读取
            cin >> e;//
            if (e == 'E') {//循环结束标志
                if (sta.empty())ans = -1;//栈已空，ERR
                else {
                    if (sta.top() / 100 == 1)key = true, vis[sta.top() - 100] = false;//找到不可执行开始符，标记又可以执行
                    else if (sta.top() / 100 == 2) {//找到有效深度标识符
                        if (key)depth--;//可以被执行的情况下深度减一
                        vis[sta.top() - 200] = false;
                    } else vis[sta.top()] = false;//直接去除重名标记
                    sta.pop();//出栈
                }
                if (ans == -1)continue;//语法错误跳过
            } else {//循环开始标志
                cin >> e >> n1 >> n2;
                if (vis[e - 'a'])ans = -1;//重名，ERR
                else vis[e - 'a'] = true;//加上重名限制
                if (ans == -1)continue;//已经有语法错误，后面跳过即可
                int temp = solve(n1, n2);//储存循环结果
                if (temp == 1) {//随n线性时间复杂度情况
                    if (key)depth++;//如果可以执行，更新有效深度
                    sta.push(200 + e - 'a');//入栈，打上有效深度标记
                } else if (temp == -1) {//不能执行
                    if (key)sta.push(100 + e - 'a'), key = false;//标记不可执行开始符，标记key，之后不可执行
                    else sta.push(e - 'a');
                } else sta.push(e - 'a');//常数复杂度不影响结果，不更新有效深度，直接入栈即可
            }
            ans = max(ans, depth);//ans在不为-1时记录最大有效深度
        }
        if (!sta.empty())ans = -1;//栈没空，说明少E，ERR
        if (ans == -1)cout << "ERR" << endl;
        else if (ans0 != ans)cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}