题解 P3952 【时间复杂度 】

_虹_

2018-09-09 21:44:31

Solution

蒟蒻首篇题解,有点害怕。 流输入输出在线操作 输入的小细节多的令人窒息,又感到了几年前被命令行贪吃蛇的输出支配的恐惧 ~~然而我还是感觉在线版本更好写~~ 基本上就是两个堆栈保存单个循环的信息,几个变量统计嵌套数等信息。然后疯狂匹配格式。 细节注释里说的应该挺清楚了。 ```cpp #include <iostream> #include <stack> #include <string> using namespace std; stack<char> s; stack<int> s2; //0:正常o(n) 1:o(1) 2:进不去 bool myhash[150]; bool boot=false; int t,n; int deepth,data,ans,rundeepth; int stopwork; char c; int x,y; string ml; void reboot() { for(char i='a';i<='z';++i) { myhash[i]=false; } boot=deepth=data=ans=rundeepth=stopwork=c=x=y=0;//boot置0避免后来的yes/no输出 n++;//这个++下面有解释 while(n)//清空剩余输入 { //c=cin.get(); //if(c=='\n') if(cin.get()=='\n')//几个\n就是几行,因为当前行调用reboot函数前已经减去了,但是换行符还在,所以给剩余行数(换行符数)+1 --n; //cout<<c<<flush; } } int main() { ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>n; cin.get(); cin.get(); cin.get(); if(cin.peek()=='n')//peek函数可以偷窥缓冲区的下一个字符还在缓冲区里保留它 { cin.get(); cin.get(); cin>>data; cin.get(); } else { data=0; cin>>ml;//其实跟下面出现的while(cin.get()!='\n');应该是等价的 } while(n--) { boot=true; cin>>c; if(c=='F') { deepth++; cin>>c; if(myhash[c]==true)//变量判重 { cout<<"ERR"<<endl; reboot();//重置各种状态 break; } myhash[c]=true;//标记一下变量使用情况 s.push(c);//堆栈保存变量 cin.get(); if(cin.peek()=='n') { cin.get(); cin>>c; if(c!='n') { if(!stopwork)//标记一下第几层循环开始进不去了,如果目前这个循环早就进不去了就不更新 stopwork=deepth; s2.push(2); while(cin.get()!='\n');//把目前行可能的 剩余字符吃掉,不然6,7点会炸 } else s2.push(1); } else { cin>>x; cin.get(); if(cin.peek()!='n') { cin>>y; if(x>y) { s2.push(2); if(!stopwork)//同上 stopwork=deepth; } else s2.push(1); } else { cin.get(); if(!stopwork)//如果这个循环是o(n)的,还能被运行,就更新目前o(n)循环深度,更新答案 { rundeepth++; ans=max(rundeepth,ans); s2.push(0); } else s2.push(2); } } } else { //deepth--; if(stopwork==deepth)//既然目前这个正在退出的循环是最早的不可进入循环,那么前面的都可以进入,所以 把标志位置0 { stopwork=0; } if(s.empty())//E比前面的F还多 { cout<<"ERR"<<endl; reboot(); break; } c=s.top(); s.pop(); myhash[c]=false;//变量名出栈并且 删除使用记录 x=s2.top(); s2.pop();//看看现在正在退出的循环的类型 if(!x)//现在退出一个 o(n)循环,所以o(n)循环的深度要-1,既然是变小,就不需要更新答案了 rundeepth--; deepth--;//总循环深度-1 } } if(boot)//如果都err了,就没有yes/no什么事了 { if(deepth!=0)//有循环没有被E结束(其实s2.empty也能用来判断这个) cout<<"ERR"<<endl; else cout<<(ans==data?"Yes":"No")<<endl;//判断答案对错 reboot();//重置各种状态 } } return 0; } ```