洛谷题目连接:时间复杂度
题目因为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;
}
为什么这道题是绿题呀!!!可能是我太菜了吧