题解 P3952 【时间复杂度 】
_虹_
2018-09-09 21:44:31
蒟蒻首篇题解,有点害怕。
流输入输出在线操作
输入的小细节多的令人窒息,又感到了几年前被命令行贪吃蛇的输出支配的恐惧
~~然而我还是感觉在线版本更好写~~
基本上就是两个堆栈保存单个循环的信息,几个变量统计嵌套数等信息。然后疯狂匹配格式。
细节注释里说的应该挺清楚了。
```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;
}
```