P3952 时间复杂度

  思路:

  直接用getline(cin,str)一行一行读,写一个get_num获取其中的数字,将'n'视为一个极大的数

  • 用一个栈模拟存变量,ins标记是否被定义过,用来判ERR,used表示该变量对复杂度是否有贡献,用flag来维护最早的不能进入循环的变量(如for int i=3 ; i<=1 ; i++),因为在它之后的根本不能运行,初始化为-1,出栈时判一下如果flag=k,则其后面的语句又可以正常运行了,令flag=-1.

代码

 #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
using namespace std; #define res register int
int T,n;
stack <int> s;
bool ins[],used[];//是否在栈中,对时间复杂度是否有贡献
string o,code[]; template <typename T>
inline T my_max(T a,T b) {return a>b?a:b;}
template <typename T>
inline T my_min(T a,T b) {return a<b?a:b;} inline int get_num(int &x,string c)
{
int tmp(),len=c.size();
while(!isdigit(c[x]) && x<len)
{
if(c[x]=='n') {++x; return ;}
++x;
}
while(isdigit(c[x])) {
tmp=tmp*+c[x]-'';
x++;
}
return tmp;
} inline int get_o()
{
int tmp(),x=;
if(o[]=='n') tmp=get_num(x,o);
else tmp=;//O(1)对应0
return tmp;
} inline int check()
{
int now(),cp();//complexity
int a,b,x;
while(s.size()) s.pop();
memset(ins,,sizeof(ins));
memset(used,,sizeof(used));
int flag(-);
for(res i= ; i<=n ; i++)
{
if(code[i][]=='F')
{
int k=code[i][]-'a';
if(ins[k]) return -;
ins[k]=true; s.push(k);
x=;
a=get_num(x,code[i]);
b=get_num(x,code[i]);
//flag为最早的不能循环的对应的变量k,可以正常循环时为-1
if(b-a> && flag==-)
{
used[k]=true; now++;
cp=my_max(cp,now);
}
else if(a>b && flag==-)
flag=k;
}
else
if(code[i][]=='E')
{
if(s.empty()) return -;
int k=s.top();
s.pop(); ins[k]=false;
if(flag==k) flag=-;
if(used[k]) now--,used[k]=false;
}
}
if(s.size()) return -;
return cp;
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d ",&n);
getline(cin,o);
int x0=get_o();
for(res i= ; i<=n ; i++)
getline(cin,code[i]);
int x1=check();
if(x1==-) puts("ERR");
else
{
if(x0==x1) puts("Yes");
else puts("No");
}
}
// system("pause");
return ;
}
05-19 10:17