首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷P3952 时间复杂度(模拟)

洛谷P3952 时间复杂度(模拟)

作者头像
attack
发布2018-12-06 15:54:14
4630
发布2018-12-06 15:54:14
举报

题意

题目链接

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

*/
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-10-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档