20220219-时间复杂度

Posted on

简单模拟题。

题意

略。

source: NOIP2017TG

link: https://www.luogu.com.cn/problem/P3952

思路

直接模拟啥事没有。令 $n=1000$，若 $r-l>101$ 就认为能贡献，若 $r<l$ 则认为不会进入循环。

代码

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
135
136
137
138
139
140
141
142
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <stack>
#include <unordered_set>

#define debug(x) (std::printf(#x " = %d\n", x))
#define debugl(x) (std::printf(#x " = %ld\n", x))
#define debugll(x) (std::printf(#x " = %lld\n", x))
#define debugc(x) (std::printf(#x " = %c\n", x))

#if 1
#undef debug
#undef debugl
#undef debugll
#undef debugc
#define debug
#define debugl
#define debugll
#define debugc
#endif

namespace mirai {

class custom_hash {
 public:
  char operator()(const char& x) const {
    return x ^ 19;
  }
};

std::stack<std::pair<char, int>> sta;
std::unordered_set<char, custom_hash> set;

int main(int argc, char** argv) {
  int t;
  std::scanf("%d", &t);
  while (t--) {
    // std::puts("=======");
    int n;
    std::scanf("%d", &n);
    char ch;
    int pw;
    std::scanf(" %c%c%c", &ch, &ch, &ch); // O([ch]
    if (ch == '1') {
      pw = 0;
      std::scanf("%c", &ch); // )
    } else {
      std::scanf("%c%d%c", &ch, &pw, &ch);
    }
    debug(pw);
    while (!sta.empty()) {
      sta.pop();
    }
    set.clear();
    int count1 = 0, count2 = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
      char ch;
      std::scanf(" %c", &ch);
      if (ans == 0x3f3f3f3f) {
        while ((ch = std::getchar()) != '\n');
        continue;
      }
      if (ch == 'E') {
        // std::puts("E");
        if (sta.empty()) {
          ans = 0x3f3f3f3f;
          continue;
        }
        auto top = sta.top();
        if (top.second == 1) {
          count1--;
        }
        if (top.second == 2) {
          count2--;
        }
        set.erase(top.first);
        sta.pop();
        continue;
      }
      std::scanf(" %c", &ch);
      debugc(ch);
      if (set.find(ch) != set.end()) {
        ans = 0x3f3f3f3f;
      } else {
        set.insert(ch);
      }
      char inp;
      int l = 1001;
      std::scanf(" %c", &inp);
      if (inp != 'n') {
        l = inp - '0';
        while (std::isdigit(inp = std::getchar())) {
          l = l * 10 + inp - '0';
        }
      }
      int r = 1001;
      std::scanf(" %c", &inp);
      if (inp != 'n') {
        r = inp - '0';
        while (std::isdigit(inp = std::getchar())) {
          r = r * 10 + inp - '0';
        }
      }
      if (ans == 0x3f3f3f3f) {
        continue;
      }
      debug(l);
      debug(r);
      int now = 0;
      if (r - l > 100) {
        now = 1;
        count1++;
      }
      if (r < l) {
        now = 2;
        count2++;
      }
      debug(now);
      if (count2 == 0) {
        ans = std::max(ans, count1);
      }
      // std::printf("%2d %2d %d %d %d %d\n", l == 1001 ? -1 : l, r == 1001 ? -1 : r, ans, now, count1, count2);
      sta.push({ch, now});
    }
    debug(ans);
    if (ans == 0x3f3f3f3f || !sta.empty()) {
      std::printf("ERR\n", ans);
    } else if (ans == pw) {
      std::printf("Yes\n");
    } else {
      std::printf("No\n");
    }
  }
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}