题解：P3952 [NOIP 2017 提高组] 时间复杂度

yyycj · 2025-02-05 13:08:51 · 题解

题目简述

A++ 语言的循环语句格式如下：

F i x y
  ...
E

其与 C++ 中的 for (int i = x; i <= y; i++) {...} 等价。

给定 t 个 L 条只有循环语句的程序，判断其中是否出现了语法错误，如果没出现则判断这个程序的时间复杂度是否与给定的时间复杂度相等。

宏定义与变量（具体含义后文给出）

#define endl '\n'
typedef long long ll;
const int L = 100 + 10;
typedef pair<int, int> pii;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
// ----------------------------
struct node {
    int depth;
    string start, _end;
    char val_name, type;
};
// ----------------------------
int l, w;
node code[L]; 
char is_use[30];
stack<pii> last_w;
// ----------------------------
int to_int(string s) {
    int ans = 0;
    rep(i, 0, (int)s.length() - 1) ans = ans * 10 + s[i] - '0';
    return ans;
}

题目分析

没有什么算法，但让人一看题目是依托，一写憋半天——

大模拟（打磨你）

输入处理

整个输入中唯一需要稍微处理一下的只有时间复杂度了，string 是个好东西（STL 大法好），可以用 string 读入。时间复杂度只有两种情况：O(1) 和 O(n^w)，用 w 来记录 O(n^{w})，第一种情况设为 0；而第二种为了方便，可以先调用 .pop_back() 函数，弹掉右括号，接着调用 .substr(4)，表示从字符串的第 4 + 1 个字符开始一直截取到最后，将这个函数返回的字符串转成数字即可。

在输入语句时，由于可能出现语法错误，但后面的输入还要继续，后续的处理比较麻烦，所以这里采用了全部读入再处理的方法，就有了宏定义中的结构体 node。除 depth 以外的变量含义较为清晰，depth 的含义为这个循环在第几层循环内，最外层则为 0。

void input() {
    cin >> l;
    w = 0;
    string s;
    int depth = -1;
    cin >> s; s.pop_back();
    if (s != "O(1") w = to_int(s.substr(4));
    rep(i, 1, l) {
        cin >> code[i].type;
        if (code[i].type == 'F') {
            depth++;
            cin >> code[i].val_name >> code[i].start >> code[i]._end;
        }
        else depth--;
        code[i].depth = depth;
    }
}

错误判断

1. F 与 E 不匹配：这个问题与括号匹配几乎相同，可以用栈或者两个计数变量都可以，此代码中使用栈因为可以同时记录另一种数据。（栈 stack<pii> last_w）

2. 变量名重复：这就更简单了，只需要一个 bool 数组即可。（数组 is_use[30]）

时间复杂度计算

void solve() {
  // do!
}

使用的变量及含义：

int now_w = 0;
/*
如果第 i 条语句的类型为 F,那么 now_w 表示只看当前语句所在的一整个大代码块里,运行它前面的未结束循环和自己所用的时间复杂度为 O(n^now_w)。
如果为 E，则 now_w 的值与计算到该语句对应的 F 语句的上一层时的 now_w 的值相同，如果对应的层已是最外层，则为 0。
例如代码为
F i 1 n
F j 1 n
F k 1 n
E
F k 1 n
E
E
E
那么在结束 i=2,4,6 的循环时 now_w=2;在结束 i=3,5 时 now_w=3。
*/
int max_w = 0;
// 最大的记录过的时间复杂度中 n 的指数，也可以说这个程序的时间复杂度就是 O(n^max_w)。
int now_depth = 0;
// 表示当前处于第几层循环，如果有循环不会执行，则计算到此循环内时 now_depth 不会改变。
bool is_use[30];
// 表示现在每个小写字母（变量名）是否存在且未被销毁。(a 的下标为 0)
stack<pii> last_w;
/*
first 表示第 second 条语句的时间复杂度为多少，只计算这一个语句。（第 second 条语句类型必定是 F）
并且这个栈还正好可以判断 F 与 E 不匹配的错误，当这个语句的类型为 E 但栈已空则为错误，代码全部运行完后栈不为空也为错误。
*/

伪代码（主体部分）

• 初始化：输入，初始 is_use 全为 false，将栈清空。

• 遍历每条语句