这道题是道模拟题，要求模拟循环嵌套的复杂度计算，一般嵌套这种问题就需要考虑栈的实现。然后在针对这种问题的时候需要理解题目的意思，否则容易出问题

首先输入格式里面，第一行是样例数，每个样例前头是行数和预期复杂度，剩下的这部分就全是代码内容。
然后针对每个样例里面的代码行如何输入，这里大家可以根据自己的习惯去做。可以像那种getline读取一行后再处理，也可以像我这样分情况讨论（因为只有两种输入格式：F i x y和E，可以先读取第一个字符后再判断）
每个样例的处理逻辑：
- 首先通过F和E来出栈入栈，我这里栈func存的内容包括变量名(char)和循环体状态(int)
- 因为题目要求不出ERR的话需要保证变量名不重复，因此需要记录每个变量的使用情况；（在出栈入栈时修改对应变量的状态，如果发现有重复那么就认为存在ERR；另外如果在空栈时出栈或者最终没有空栈就说明F和E没有匹配好，也应该是ERR）
```
if (cmd == 'E') {
  if (func.empty()) {// 空栈
    invalid = true;
    continue;
  }
  //......
} else {
  //...
  if (vars[var - 'a']) { // 当前变量已使用过，尚未删除
    invalid = true;
    continue;
  }
  //...
}  
```
- 而循环体状态则是为了记录当前循环是否会增加复杂度（由于这里每层循环最多执行常数次或n次，因此每层循环都是O(1)或O(n)的）
- 那么如何判断当前循环是否会增加复杂度呢，我们首先看下F i x y的逻辑，
  - x是"n"时：
    1. y是"n"：进入循环，但只做一次(这里我之前没考虑，以为这也不进入循环，结果只有80%样例通过)
    2. y是常数：x = n > 100 > y，则不进入循环
  - x不是"n"时:
    1. y是"n": 进入循环，并且复杂度加一层
    2. y >= x: 进入循环，执行常数次
    3. y < x: 不进入循环
- 那么针对这些我们就可以写个函数专门判断它是否进入循环。然后针对进入循环的情况判断是否需要加一层计数。并在对应层出栈时减一
- 但是如果只做了上面这些还不行，因为有可能这部分循环体在更上层的循环体里面就没有执行，因此我这里计数的时候设计了三种状态（1:增加计数，0：常数循环，不增加计数，-1:不进入循环，里层更不进入），如果当前状态已经是-1，那下一层循环体也一定是-1.

完整代码

#include <bits/stdc++.h>
using namespace std;

int toNumber(string& x) {
  if (x == "O(1)") return 0;
  int result = 0;
  for (int i = 4; i < x.length() - 1; ++i) {
    result = 10 * result + (x[i] - '0');
  }
  return result;
}

bool check(string x, string y) {
  if (x == "n") return (y != "n");
  if (y == "n") return false;
  if (x.length() > y.length()) return true;
  if (x.length() == y.length()) return x > y;
  return false;
}

int main() {
  int t;
  int L;
  string complex;

  // Input
  cin >> t;
  while (t--) {
    cin >> L >> complex;
    int target = toNumber(complex);

    // Commands
    char cmd, var;
    string x, y;

    // Status
    int cur_level = 0, max_level = 0;
    stack<pair<char, int> > func;
    bool invalid = false;     // Check ERR
    bool vars[26] = {false};  // Check duplicate vars

    for (int i = 0; i < L; ++i) {
      cin >> cmd;

      if (cmd == 'E') {
        if (invalid) continue;  // skip following statements
        if (func.empty()) {
          invalid = true;
          continue;
        }
        // Change states
        vars[func.top().first - 'a'] = false;
        if (func.top().second == 1) cur_level -= 1;
        func.pop();
      } else {
        cin >> var >> x >> y;
        if (invalid) continue;  // skip following statements
        if (vars[var - 'a']) {
          invalid = true;
          continue;
        }

        vars[var - 'a'] = true;
        // invalid cond or  outer loop is already invalid cond
        if (check(x, y) || (!func.empty() && func.top().second == -1))
          func.push(make_pair(var, -1));
        else
          func.push(make_pair(var, (y == "n" && x!= "n")));

        // add complex count
        if (func.top().second == 1) {
          cur_level += 1;
          max_level = max(cur_level, max_level);
        }
      }
    }

    if (!func.empty() || invalid)
      cout << "ERR" << endl;
    else {
      cout << ((max_level == target) ? "Yes" : "No") << endl;
    }
  }

  return 0;
}

题解 | #[NOIP2017]时间复杂度#

全站热榜