[洛谷P3952] 时间复杂度

洛谷题目连接:时间复杂度

题目因为markdown复制过来有点崩格式,就不复制了,看题请戳上面的链接.

一句话题意: 处理一堆的字符串,形式为F i x y或者是E,表示的是开始一个循环或者是一个循环的结束,问多个循环随意组合嵌套之后的时间复杂度.

题解: 显然是模拟,这里主要讲一下那些可能会遇到的细节问题 (话说我道题居然搞了两个小时,还是联赛之后才写的,联赛的时候调了两个小时最后心态爆炸全部输出yes得了20分,很为我下一次联赛担忧呀...)

• 循环读入的时候最好不要按行的读入,也不要按字符的读入,这样都可能出玄学问题 (事实上是因为cin.getline/getline(cin,s)这些操作我都不是很熟练),最好是先读入一个字符判断是开始了一个循环还是一个循环结束,然后再考虑之后的读入.
• 输入字符用cin永远不会那么玄学.
• 为了使代码看起来比较简洁,也是为了防止代码都挤到主函数一堆辣眼睛,可以写一些函数把部分内容放进去,确保这个函数没问题了就别看这个函数了(最好是写一个函数检查一个函数).
• 把每个用到的变量都清零,因为多组数据.
• 复杂度可以用栈来实现,这样每多加入一重循环就在栈内多申请一个变量,结束循环就直接出栈就可以了.
• 麻烦的地方主要是考虑栈的模拟,如何加入新的循环和删除循环,下面列举一下可能遇到的问题:
  • 循环的下标从大到小无法进入循环,之后嵌套在这重循环内的循环都无法增加时间复杂度.
  • 循环从n开始(当然你可以直接写一个函数计算一个字符串的值,也就是计算循环起点和终点,可以直接将字符为n的赋为一个较大的值.
    

主要的细节大概也只有上面这一些了吧.

主要还是考验自己的代码能力,认真打,想清楚每个变量是什么意思,自己是肯定做的出来的 (只不过看要调多久了233).

下面放一下自己巨丑无比的代码:

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;

int T, line, ans0, ans, top = 0, mistake, lev, mx, f, stk1[100+5];
char opt, var, begin[10+5], end[10+5], stk[100+5], given[10+5];
map <char, int> vis;

int getc(){
    int len = strlen(given), res = 0, flag = 0;
    for(int i=0;i<len;i++){
        if('0' <= given[i] && given[i] <= '9')
            res = res*10+given[i]-'0';
        if(given[i] == 'n') flag = 1;
    }
    return flag ? res : 0;
}

int change(char s[]){
    if(s[0] == 'n') return inf;
    int len = strlen(s), res = 0;
    for(int i=0;i<len;i++)
        res = res*10+s[i]-'0';
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--){
        cin >> line >> given;
        ans0 = getc(); ans = -1, mx = mistake = lev = 0; f = inf; vis.clear();
        memset(stk1, 0, sizeof(stk1));
        for(int i=1;i<=line;i++){
            cin >> opt;
            if(opt == 'F'){
                cin >> var >> begin >> end;
                int st = change(begin), ed = change(end);
                if(vis[var]) mistake = 1;
                stk[++top] = var; vis[var] = 1; lev++;
                if(lev < f){
                    if(st != inf && ed == inf) stk1[top] = 1, mx++;
                    if(st > ed) f = lev;
                }
            }
            else vis[stk[top]] = 0, mx -= stk1[top], stk1[top] = 0, lev--, top--;
            if(lev < f) f = inf;
            if(lev < 0) mistake = 1;
            ans = max(ans, mx);
        }
        if(mistake || lev) cout << "ERR" << endl;
        else if(ans0 == ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

为什么这道题是绿题呀!!!可能是我太菜了吧