欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[洛谷P3952] 时间复杂度

程序员文章站 2024-03-19 09:08:10
...

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

题目因为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;
}

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