复赛二：时间复杂度(complexity)

  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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

/**************************************************************** 
 * Description: 2017年提高组 时间复杂度
 * Author: Alex Li
 * Date: 2024-10-01 15:43:16
 * LastEditTime: 2024-10-01 19:28:11
****************************************************************/
#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_LINES = 105;

int test_case_count, line_count, claimed_exponent;
string complexity_str;
string program_code[MAX_LINES];

/*从字符串中读取数字或识别 'n', index 当前读取的位置索引（引用传递，会被修改）
code_line 输入的字符串,  return int 返回读取到的数字，如果遇到 'n' 则返回一个较大的数表示 'n'
 */
int read_value(int &index, string code_line) {
    int number = 0;
    int len = code_line.size();
    // 跳过非数字字符，优先判断 'n'
    while ((code_line[index] < '0' || code_line[index] > '9') && index < len) {
        if (code_line[index] == 'n') {
            ++index;
            return 1000000; // 使用大数表示 'n'
        }
        ++index;
    }
    // 读取数字
    while (index < len && code_line[index] >= '0' && code_line[index] <= '9') {
        number = number * 10 + (code_line[index] - '0');
        ++index;
    }
    return number;
}

/*解析声明的时间复杂度，提取指数部分 @return int 如果是 O(1) 返回 0，如果是 O(n^w) 返回 w，
格式错误返回 -1*/
int get_claimed_exponent() {
    int exponent = 0, index = 3;
    int len = complexity_str.size();
    if (complexity_str[2] == 'n') {
        exponent = read_value(index, complexity_str);
    }
    else {
        exponent = 0;
    }
    return exponent;
}

/**
 * @brief 检查程序的实际时间复杂度是否与声明一致
 * 
 * @return int 如果有语法错误返回 -1，否则返回实际的指数
 */
int check_time_complexity() {
    int max_exponent = 0, current_exponent = 0;
    int value_a, value_b, index;
    stack<int> loop_stack;
    int active_flag = -1;
    bool is_active[26] = {false};        // 标记变量是否被使用
    bool has_incremented[26] = {false};  // 标记变量是否增加了指数

    for(int i = 1; i <= line_count; i++) {
        if(program_code[i][0] == 'F') {
            int var_index = program_code[i][2] - 'a';
            // 检查变量是否已经被使用
            if(is_active[var_index]) return -1;
            loop_stack.push(var_index);
            is_active[var_index] = true;
            index = 4;
            value_a = read_value(index, program_code[i]);
            value_b = read_value(index, program_code[i]);
            //printf("a:%d  b:%d\n",value_a,value_b);
            if(value_b - value_a > 1000) {
                // 判断是否当前没有活动的循环
                if(active_flag == -1) {
                    current_exponent++;
                    max_exponent = max(max_exponent, current_exponent);
                    has_incremented[var_index] = true;
                }
            }
            // 判断循环是否不会执行
            if(value_a > value_b) {
                if(active_flag == -1) active_flag = var_index;
            }
        }
        if(program_code[i][0] == 'E') {
            if(loop_stack.empty()) return -1;
            int var_index = loop_stack.top();
            loop_stack.pop();
            is_active[var_index] = false;
            if(active_flag == var_index) active_flag = -1;
            if(has_incremented[var_index]) {
                has_incremented[var_index] = false;
                current_exponent--;
            }
        }
    }
    if(!loop_stack.empty()) return -1; // 检查所有循环是否已经结束
    return max_exponent;
}

int main() {
    //freopen("complexity.in","r",stdin);
    //freopen("complexity.out","w",stdout);
    
    cin>>test_case_count;
    while(test_case_count--) {
        int actual_exponent;
        cin>>line_count; // 读取行数，并忽略后面的空格
        /*在使用 cin >> 读取整数或字符串后，紧接着使用 getline 时，
        需要调用 cin.ignore() 来忽略缓冲区中残留的换行符或其他空白字符，确保 getline 能正确读取下一行的内容。*/
        cin.ignore();
        getline(cin, complexity_str); // 读取复杂度字符串
        claimed_exponent = get_claimed_exponent(); // 解析声明的时间复杂度
       
        for(int i = 1; i <= line_count; i++) getline(cin, program_code[i]); // 读取程序的每一行代码
        
       
        actual_exponent = check_time_complexity(); // 检查实际的时间复杂度
     
        if(actual_exponent == -1) cout << "ERR\n"; // 语法错误
        else {
            if(actual_exponent == claimed_exponent) cout << "Yes\n"; // 时间复杂度匹配
            else cout << "No\n"; // 时间复杂度不匹配
        }
    }
}