「NOIP2017」时间复杂度 - 模拟

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

本题定义了一个新语言名为 A++，语言的循环定义如下：

1
2
3
F i x y
    循环体
E

本循环相当于

1
for (int i = x; i <= y; i++)

输入一个程序和时间复杂度，判断时间复杂度是否和程序相符。 其中满足 x，y 必为常数或 n，n 远大于 x，y。

具体信息可详见洛谷，链接见上

解题思路

显然本题为一道模拟题。

模型建立

解题思路为通过 A++ 循环分析该代码的时间复杂度。 时间复杂度可通过存储 \(O(n^k)\) 的指数达到目的。 通过新建 depth 变量存储有效增加代码时间复杂度的个数，使用 maxn 变量存储 depth 的最大值即可记录该 A++ 代码的时间复杂度。

1
2
3
4
5
6
7
8
std::cin >> l >> tmp;
if (tmp[2] == '1') o = 0;
else {
    o = 0;
    for (int each = 4; tmp[each] >= '0' && tmp[each] <= '9'; each++) {
        o = o * 10 + tmp[each] - '0';
    }
}

本题由于有嵌套循环的可能，所以可以写一个栈来模拟。 又由于 A++ 中变量不可重名，故有遍历栈的需求。 故可以写一个手工栈，栈中存有 A++ 变量名。

1
2
int top = 0;
std::string stack[100];

此时输入 F 则入栈，输入 E 则出栈，注意当 F 与 E 没有一一对应时需要处理为 ERR。

1
2
3
4
5
6
7
8
9
10
std::cin >> tmp;
if (tmp == "F") {
    std::cin >> stack[top] >> x >> y;
    // 处理后续
    top++;
} else {
    if (top == 0) {
        // A++语法错误，输出ERR及处理后续
    } else top--;
}

循环处理

首先处理 A++ 循环中申明的变量，若变量重复，则处理为 ERR。

1
2
3
for (int j = 0; j < top; j++)
    if(stack[j] == stack[top])
        err = true;

循环可分 4 种情况讨论：

  1. x，y 均为 n；
  2. x 为 n，y 为常数；
  3. x 为常数，y 为 n；
  4. x，y 均为常数。

第一种情况显然时间复杂度为 \(O(1)\)。 第二种情况由于 n 远大于 x，故这个循环和循环内部的任何语句都不会被执行，此时需要新建变量 unknown 来记录该层层数，在这个层数之上则不记录时间复杂度。 第三种情况由于 n 远大于 y，时间复杂度为 \(O(n)\)，所以需要 depth++。 第四种情况则需要分两种情况讨论。

  1. \(x \leq y\)
  2. \(x > y\) 其中第一种情况显然时间复杂度为 \(O(1)\)。 第二种情况得循环及其内部也不会被执行，等同 x 为 n，y 为常数的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if (x == "n" && y == "n") f[top] = false;
if (x == "n" && y != "n") {
    f[top] = false;
    if (top < unshown)
        unshown = top;
}
if (x != "n" && y == "n") {
    if (top < unshown) {
        f[top] = true;
        depth++;
    } else f[top] = false;
}
if (x != "n" && y != "n") {
    nx = ny = 0;
    for (int j = 0; j < x.length(); j++) nx = nx * 10 + x[j] - '0';
    for (int j = 0; j < y.length(); j++) ny = ny * 10 + y[j] - '0';
    if (nx > ny && top < unshown) unshown = top;
    f[top] = false;
}
top++;
if (depth > maxn) maxn = depth;

最后在收到 E 的时候结束循环，弹出栈。 若栈已空，则说明 F 与 E 不匹配，处理为 ERR。 此时则需检测这层循环中 depth 有无变化，若有变化则 depth-- 表明这层循环已退出时间复杂度的统计，以便处理其他循环。 同时需注意处理 unknown 变量。

1
2
3
4
5
6
if (top == 0) err = true;
else {
    if (top - 1 == unshown) unshown = 100;
    else if (f[top - 1]) depth--;
    top--;
}

代码演示

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
#include <iostream>
#include <cstring>

int main() {
    int t, l, o, nx, ny, unshown;
    std::string tmp, stack[100], x, y;
    int depth, top, maxn;
    bool err, f[100];
    memset(f, 0, sizeof(f));

    std::cin >> t;

    while (t > 0) {
        top = depth = maxn = 0;
        unshown = 100;
        err = false;

        std::cin >> l >> tmp;

        if (tmp[2] == '1') o = 0;
        else {
            o = 0;

            for (int each = 4; tmp[each] >= '0' && tmp[each] <= '9'; each++) {
                o = o * 10 + tmp[each] - '0';
            }
        }

        for (int each = 0; each < l; each++) {
            std::cin >> tmp;

            if (tmp == "F") {
                std::cin >> stack[top] >> x >> y;

                for (int j = 0; j < top; j++)
                    if (stack[j] == stack[top])
                        err = true;

                if (x == "n" && y == "n") f[top] = false;

                if (x == "n" && y != "n") {
                    f[top] = false;
                    if (top < unshown) unshown = top;
                }

                if (x != "n" && y == "n") {
                    if (top < unshown) {
                        f[top] = true;
                        depth++;
                    } else f[top] = false;
                }

                if (x != "n" && y != "n") {
                    nx = ny = 0;

                    for (int j = 0; j < x.length(); j++) nx = nx * 10 + x[j] - '0';
                    for (int j = 0; j < y.length(); j++) ny = ny * 10 + y[j] - '0';
                    if (nx > ny && top < unshown) unshown = top;

                    f[top] = false;
                }

                top++;

                if (depth > maxn) maxn = depth;
            } else {
                if (top == 0) err = true;
                else {
                    if (top - 1 == unshown)
                        unshown = 100;
                    else if (f[top - 1])
                        depth--;

                    top--;
                }
            }
        }

        if (err || top != 0) std::cout << "ERR" << std::endl;
        else if (maxn == o) std::cout << "Yes" << std::endl;
        else std::cout << "No" << std::endl;

        t--;
    }

    return 0;
}