c/c++语言开发共享洛谷P3952 时间复杂度(模拟)

题意

题目链接

sol

咕了一年的题解。。就是个模拟吧

考场上写的递归也是醉了。。。

感觉一年自己进步了不少啊。。面向数据编程的能力提高了不少

#include<bits/stdc++.h>  #define fi first #define se second #define mp make_pair using namespace std; const int maxn = 101; int t, top = 0, now, mx, flag; pair<char, int> st[maxn];// first 字符  second 是否算作复杂度 1 算 0不算  void init() {     top = 0;//已经用过哪些字符      now = 0;//当前进入了几层循环      mx = 0;//最大循环层数      flag = 0; } int get(char *s) {     int l = strlen(s + 1), x = 0;     for(int i = 1; i <= l; i++) if(s[i] >= '0' && s[i] <= '9') x = x * 10  + s[i] - '0';     return x; } char getopt() {     char c = ' ';     while(c != 'e' && c != 'f') c = getchar();     return c == 'f' ? 1 : 0;// 1 enter  0 end } int readround() {//n = -1     char c = ' '; int x = 0;     while(c != 'n' && (c < '0' || c > '9')) c = getchar();     if(c == 'n') return -1;     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x; } int readbuf() {//  1 n  0常数   -1重名      char c = getchar();     while(c < 'a' || c > 'z') c = getchar();     int bg = readround(), ed = readround();     for(int i = 1; i <= top; i++) if(st[i].fi == c) return -1;     if((bg != -1 && ed != -1 && bg > ed) || (bg == -1 && ed != -1)) {flag = 1, st[++top] = mp(' ', -1); return 0;}//不进入循环      if(bg != -1 && ed == -1) {//非常数循环         if(flag == 0) now++, mx = max(now, mx), st[++top] = mp(c, 1);         else st[++top] = mp(c, 0);     } else {         st[++top] = mp(c, 0);     }     return 0; } int solve() {// 1 yes 0 no  -1 err     int l, w = 0, gg = 0; char s[233];     scanf("%d %s", &l, s + 1);     if(s[3] == 'n') w = get(s + 1);     for(int i = 1; i <= l; i++) {         int opt = getopt();         if(opt == 0) {             if(top == 0) gg = -1;             else {                 if(st[top].se == -1) flag = 0;                 if(st[top--].se == 1) now--;             }         } else {             int tmp = readbuf();             if(tmp == -1) gg = -1;         }     }     if(gg == -1) return -1;     if(top) return -1;     else return mx == w; } int main() {     cin >> t;      while(t--) {         init();         int tmp = solve();         if(tmp == 1) puts("yes");         else if(tmp == 0) puts("no");         else puts("err");     }     return 0; } /* 1 2 o(n^1) f a n n e  */