题解 P3952 【时间复杂度 】

## 大概分析一下本题の做法 首先，一边判编译一边算复杂度显然是不可能的，于是我们先考虑判编译 ### 编译错误的两个定义： ①F，E不匹配，那么先统计个数，个数不同直接退。 否则就维护一个栈，每次碰到F就压栈，碰到E就弹栈顶，同时把栈顶F对应的位置和当前E的位置匹配一下。 如果弹不出，说明E多余，报错；如果不报错，最后栈一定为空（**思考一下**） ②重名，配合判FE的那个栈，每次压栈的时候标记当前这个变量名，如果当前要压进栈的变量名已经被标记过，直接报错；出栈清楚标记 于是编译错误就判完了，下面开始讲解程序的复杂度计算 ### 程序的结构大概如下 F …… E 或者是 F …… E F …… E …… F …… E **两个情况：整个程序被一组FE包起来，或者由多组FE首尾相接组成** 对于被FE包的程序，O(1)算出最外层FE的复杂度，如果初值大于终值直接返回O(1)，如果两头都是常数或都是n，也返回O(1)，否则返回O(n) 接下来把这对FE去掉，算去掉以后的程序复杂度，再加上刚刚算出来的最外层复杂度 对于多组FE，各个击破取最大值 **但是目前来说题解里没有使用递归的程序，使用递归以后思路会很清晰，而且这题没有爆栈风险** 定义```int pd(i)```，判第i行的F复杂度，返回0代表O(1)，返回1代表O(n) 这个很好实现 ```int solve(l,r)```，判从第l到第r行的复杂度，返回k代表O(n^k) 先看边界：长度只有2，直接返回当前的```pd(l)``` 然后分类讨论 **一、被一组FE包起来，先看这个循环的初值是否大于终值，如果是返回0** 否则，```ret=solve(l+1,r-1)+pd(l)```，即内部复杂度加自身复杂度 **二、多组FE，取每组FE的最大值** ```ret=max(solve(li,ri))``` 上代码 ------------ ```cpp #include<bits/stdc++.h> #define maxn (200+5) using namespace std; int T,L; int op[maxn],x[maxn],y[maxn],p[maxn],vis[maxn]; char val[maxn]; //op F=1，E=0 //x,y 初值与终值，n=1001 //p 第i行的F所对应的E的位置 //vis 判编译的时候标记数组 //val 第i行F对应的变量名 stack<int> s; //判编译的栈 int pd(int i) { if (y[i]-x[i]>=100) return 1; //差大于一百，即x为常数，y=n else return 0; } int solve(int l,int r) { int ret=0; if (l+1==r) return pd(l); //只有两行，直接返回这行循环的复杂度 int L=l,R=p[l]; //取出第一组循环 if (R==r) //如果只有一组即FE包整个循环 if (x[l]<=y[l]) return solve(l+1,r-1)+pd(l); //如果外层会执行 else return 0; //不会执行直接return while (L<=r) //遍历每一组FE { ret=max(ret,solve(L,R)); //取一个较大值 L=R+1; R=p[L]; //取下一组 } return ret; } int main() { cin >> T; while (T--) { string s1; cin >> L >> s1; //长度和某人算的 int f=0,e=0,tar; //FE个数，tar表示某人算的复杂度指数 s1.erase(0,2); s1.erase(s1.length()-1,1); //去掉O() if (s1[0]=='1') tar=0; //O(1) else if (s1.length()==3) tar=s1[2]-48; //指数为一位数 else if (s1.length()==4) tar=(s1[2]-48)*10+s1[3]-48; //两位数 for (int i=1;i<=L;++i) { char ch; cin >> ch; //判是F还是E if (ch=='E') op[i]=0,e++; else { op[i]=1; f++; string X,Y; cin >> val[i] >> X >> Y; //变量名，初值终值 if (X[0]=='n') x[i]=1001; //如果是n赋为1001 else if (X.length()==2) x[i]=(X[0]-48)*10+X[1]-48; else x[i]=X[0]-48; if (Y[0]=='n') y[i]=1001; else if (Y.length()==2) y[i]=(Y[0]-48)*10+Y[1]-48; else y[i]=Y[0]-48; } } if (f!=e) //数量不统一 { puts("ERR"); continue; } int Err=0; while (!s.empty()) s.pop(); //清空栈，因为上次可能没做完就break memset(vis,0,sizeof(vis)); //清空标记，同理 for (int i=1;i<=L;++i) if (op[i]) { if (vis[val[i]]) //变量重名 { Err=1; break; } s.push(i); //压栈 vis[val[i]]=1; //打标记 } else { if (s.empty()) //栈空不匹配 { Err=1; break; } int l=s.top(); s.pop(); //弹掉 vis[val[l]]=0; //清标记 p[l]=i; //匹配 } if (Err) //显示编译错误 { puts("ERR"); continue; } int ans=solve(1,L); //递归过程 if (ans==tar) puts("Yes"); else puts("No"); } return 0; } ```