Luogu-P3952-时间复杂度

Posted on Edited on Word count in article: 1.1k

题目 P3952 [NOIP2017 提高组] 时间复杂度

思路：栈stack

注：所有“编译错误”的字样都并非真正的编译错误，而是题目描述中输出ERR的情况。

定义一个栈 ss，利用栈的位置：

  • 进入循环时，压栈。
  • 跳出循环时，弹栈。

问题转化

循环

因为时间复杂度忽略次要项，只保留最高次项，所以本题可转化为最深的循环有几层。

对于每个循环：

  • 如果循环无法进入，则这层和它内部的循环均不计数，但要检查是否会出现编译错误。
  • 如果循环执行常数次，则这层循环不计数。
  • 如果循环执行 nn 次，则正常计数。

对于循环的起始值 startstart 和终止值 endend，考虑以下情况（x,yx,y 为常数，$ 1 \leq x \leq y \lt 100$）：

  • x,nx,n
  • n,xn,x
  • n,nn,n
  • x,yx,y
  • y,xy,x
  • x,xx,x

如果规定一个状态值 statestate：

循环状态 statestate
无法进入 −1-1
常数次 00
nn 次 11

那么就有以下的对应：

循环起点和终点 statestate
x,nx,n 11
n,xn,x −1-1
n,nn,n 00
x,yx,y 00
y,xy,x −1-1
x,xx,x 00

所以，只需要根据 startstart 和 endend 的关系，计算出 statestate 即可。

变量记录

用 visvis 数组记录变量（字母）的使用情况，在进入循环时，对它的循环变量 letterletter 进行 vis[letter]=truevis[letter] = true 的赋值。

F-E合法判定

题目要求一个F必须和一个E配对。

遇到F时压栈，遇到E时弹栈。

如果弹栈时栈为空，不合法。

如果到最后栈中有残余，不合法。

数字比较

定义 cmp(s1,s2)cmp(s_1,s_2) 函数进行比较，以下是返回值列表。

关系 返回值
s1>s2s_1>s_2 −1-1
s1<s2s_1<s_2 11
s1=s2s_1=s_2 00

朴素的字符串数字比较如下：

  • 不同长度时，较长的数字为较大值。
  • 相同长度时，从左往右找，先找到较大数位的是较大值。
  • 否则，两数相等。
1
2
3
4
5
6
7
8
9
int cmp(string s1, string s2) {
    if(s1.length() > s2.length()) return -1;
    if(s1.length() < s2.length()) return 1;
    for(int i = 0; i < s1.length(); i++) {
        if(s1[i] > s2[i]) return -1;
        if(s1[i] < s2[i]) return 1;
    }
    return 0;
}

由于本题的特殊性，需要额外判断数字为 nn 的情况。

并且，s1<s2s_1<s_2 和 s1=s2s_1=s_2 对应的 statestate 都为 00，所以将小于的情况当作等于处理。

所以，以下是适用本题的 cmp()cmp() 函数。

1
2
3
4
5
6
7
8
9
10
11
12
int cmp(string s1, string s2) {
    if(s1 == s2) return 0;
    if(s1 == "n") return -1;
    if(s2 == "n") return 1;
    if(s1.length() > s2.length()) return -1;
    if(s1.length() < s2.length()) return 0;
    for(int i = 0; i < s1.length(); i++) {
        if(s1[i] > s2[i]) return -1;
        if(s1[i] < s2[i]) return 0;
    }
    return 0;
}

所以，这个函数的返回值就是上述对应的 statestate。

循环的处理

使用node类型保存循环的信息，depthdepth 表示当前的循环深度。

1
2
3
4
5
struct node {
    int state;
    char letter;
    int depth;
};

使用 curr_depthcurr\_depth 记录当前的深度，如果 statestate 不为 −1-1，就让 curr_depthcurr\_depth 加上 statestate。

否则，为了便于处理问题，认为：当外层循环的 statestate 为 −1-1 时，内层循环的 statestate 也为 −1-1。

1
2
3
4
5
6
7
8
if(x == -1) {
    s.push({-1, letter, curr_depth});
} else if(s.size() && s.top().state == -1) {
    s.push({-1, letter, curr_depth});
} else {
    curr_depth += x;
    s.push({x, letter, curr_depth});
}

在遇到E，弹出一个循环时，让 max_depthmax\_depth 为 原来的 max_depthmax\_depth 和 curr_depthcurr\_depth 中的较大值，同时取消标记 letterletter。

同样，如果会产生编译错误，让 max_depthmax\_depth 的值为 −1-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool vis['z' + 10];

int my_max(int x, int y){
    if(x == -1) return -1;
    return max(x, y);
}

int main(){
    // ...
    node n = s.top();
    s.pop();
    vis[n.letter] = false;
    max_depth = my_max(max_depth, n.depth);
    if(n.state == 1) curr_depth -= 1;
    // ...
}

由于可能产生编译错误，所以无论遇到F还是E，一旦 max_depthmax\_depth 为 −1-1，只输入不计算，立刻跳出循环。

1
if(max_depth == -1) continue;

注意：此处我使用的是边输入边计算，所以不能在检测到 −1-1 后直接使用goto等方式跳出循环，否则一组数据就不能全部输入（但玄学的是能得63分）。

如果使用getline等方式提前输入数据，则可以放心使用goto直接跳出。

输出

本题输出的判断分为以下几步：

  • 如果编译错误，直接输出ERR。
  • 否则，检查 max_depthmax\_depth 是否和给定表达式中的指数相同。

表达式也有两种形式：

  • O(1)
  • O(n^xxx)

当 max_depth=0max\_depth=0 时，检查表达式是否为O(1)即可。

否则，进行字符串处理：

  • 将 max_depthmax\_depth 转换成字符串。
  • 提取表达式中的指数部分：前四位舍去，后一位舍去。
  • 检查是否相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void prn(string res, int depth){
    if(depth == -1){
        cout << "ERR" << endl;
        return;
    }
    if(depth == 0){
        if(res == "O(1)") cout << "Yes" << endl;
        else cout << "No" << endl;
        return;
    }
    if(to_string(depth) == res.substr(4, res.length() - 5)){
        cout << "Yes" << endl;
        return;
    }else cout << "No" << endl;
}

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// template v12
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 110;

bool vis['z' + 10];

struct node {
    int state;
    char letter;
    int depth;
};

stack<node> s;

void init() {
    set(vis, 0);
    s = stack<node>();
}

int cmp(string s1, string s2) {
    if(s1 == s2) return 0;
    if(s1 == "n") return -1;
    if(s2 == "n") return 1;
    if(s1.length() > s2.length()) return -1;
    if(s1.length() < s2.length()) return 0;
    for(int i = 0; i < s1.length(); i++) {
        if(s1[i] > s2[i]) return -1;
        if(s1[i] < s2[i]) return 0;
    }
    return 0;
}

void prn(string res, int depth){
    if(depth == -1){
        cout << "ERR" << endl;
        return;
    }
    if(depth == 0){
        if(res == "O(1)") cout << "Yes" << endl;
        else cout << "No" << endl;
        return;
    }
    if(to_string(depth) == res.substr(4, res.length() - 5)){
        cout << "Yes" << endl;
        return;
    }else cout << "No" << endl;
}

int my_max(int x, int y){
    if(x == -1) return -1;
    return max(x, y);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("complexity.in", "r", stdin);
    freopen("complexity.out", "w", stdout);
#endif
    int T;
    cin >> T;
    int n;
    string cplx;
    while(T-- > 0) {
        init();
        cin >> n >> cplx;
        char tag, letter;
        string start, end;
        int max_depth = 0, curr_depth = 0;
        int x = 0;
        for(int i = 1; i <= n; i++) {
            cin >> tag;
            switch(tag) {
                case 'F':
                    cin >> letter;
                    cin >> start >> end;
                    if(max_depth == -1) continue;
                    x = cmp(start, end);
                    if(vis[letter]) {
                        max_depth = -1;
                    }
                    if(x == -1) {
                        s.push({-1, letter, curr_depth});
                    } else if(s.size() && s.top().state == -1) {
                        s.push({-1, letter, curr_depth});
                    } else {
                        curr_depth += x;
                        s.push({x, letter, curr_depth});
                    }
                    vis[letter] = true;
                    break;
                case 'E':
                    if(s.empty()) {
                        max_depth = -1;
                        continue;
                    }
                    node n = s.top();
                    s.pop();
                    if(max_depth == -1) continue;
                    vis[n.letter] = false;
                    max_depth = my_max(max_depth, n.depth);
                    if(n.state == 1) curr_depth -= 1;
                    break;
            }
        }
        if(s.size()) max_depth = -1;
        prn(cplx, max_depth);
    }
    return 0;
}

补充

数组大小中的z

注意到以下语句：

1
bool vis['z' + 10];

'z' + 10是什么意思呢？

因为本题需要标记小写字母的使用情况，所以使用ASCII码最大的z再加上 1010 作为数组的大小，这样就可以直接使用char字符作为下标，而不用进行额外操作。