NOIp2017 时间复杂度 题解

分析

模拟，模拟，还是模拟。

给定了 $n$ 行 A++ 代码和一个小明算的时间复杂度，判断此复杂度是否正确（$Yes$ 和 $No$）。

若代码存在语法问题（$F$ 与 $E$ 未匹配或变量名重复定义），则输出 $ERR$。

思路

循环可以嵌套，也可以并列，考虑用栈来模拟每一组循环。

使用两个栈，一个使用结构体维护循环信息 $st$，一个维护当前的时间复杂度信息 $opts$。

为了方便，开始之前先将 $opts$ 内压入一个 0。

（本题解时间复杂度表示中，$w$ 表示复杂度为 $O(n^w)$。）

接下来是模拟流程。

维护一个整数数组 $u$，$u_c$ 表示字符 $c$ 在此时被使用的次数。

如果读取到 $F$：

- 将循环的参数 $i$、$x$ 和 $y$ 压入 $st$；为方便，将 $n$ 看做 101。

- 如果此前参数 $i$ 已经被使用，则将 $isERR$ 设为 1；

- 将 $u_i$ 的值增加 1；

- 将 0 压入 $opts$。

如果读取到 `E`：

- 若此时栈空，即没有循环需要退出，$isERR$ 设为1；

- 否则弹出当前 $st$ 顶的循环，使用 $opts$ 栈顶更新 $opts$ 次顶的时间复杂度。弹出栈顶。将 $u_i$ 的值减少 1。

当 $l$ 行代码运行完毕，若 $st$ 栈内仍有元素，则将 $isERR$ 设为 1。

最后，判定算得结果是否与小明的答案相同即可。

更新时间复杂度

本题解将着重讲解一下时间复杂度的更新。

对于一层循环 ${i,x,y}$，其复杂度与内部的所有嵌套的子循环有关，且为所有嵌套的子循环中时间复杂度的最大值，再加上该循环自身的复杂度。

首先，若此循环中 $x>y$，即无法进入，则此循环及往下的复杂度一定为 $O(1)$，表示为 0；

若 $y=101$ 且 $x\neq 101$，则此循环的复杂度为 $O(n)$，表示为 1。

特别地，$x$ 与 $y$ 都为 101 时，此循环的复杂度仍记为 $O(1)$。

CODE

#include<bits/stdc++.h>
#define ll long long
#define rev(x) reverse(x.begin(),x.end())
#define lb(x) (x&(-x))
using namespace std;
struct node{
    char varName;
    int from,to;
    node(){
        varName=' ';
        from=to=0;
    }
    bool ableToRun(){
        return from<=to;
    }
};
int varNameIsUsed[26];
stack<node> st;
stack<int> opts;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	freopen("2017complexity.in","r",stdin);
//	freopen("2017complexity.out","w",stdout);
	
	int t;cin>>t;
	while(t--){
	    while(!st.empty()) st.pop();
	    while(!opts.empty()) opts.pop();
	    opts.push(0);
	    memset(varNameIsUsed,0,sizeof varNameIsUsed);
	    bool isERR=false;
	    
	    int ls;cin>>ls;
	    string ops;cin>>ops;
	    
	    for(int lne=1;lne<=ls;lne++){
	        char p;cin>>p;
	        if(p=='F'){
	            node wp;
	            cin>>wp.varName;
	            string fm,tm;cin>>fm>>tm;
	            if(fm=="n") wp.from=101;
	            else{
	                int nw=0;
	                for(int i=0;i<fm.length();i++) nw=nw*10+fm[i]-'0';
	                wp.from=nw;
                }
	            if(tm=="n") wp.to=101;
                else{
	                int nw=0;
	                for(int i=0;i<tm.length();i++) nw=nw*10+tm[i]-'0';
	                wp.to=nw;
                }
                
                if(varNameIsUsed[wp.varName-'a']) isERR=true;
                varNameIsUsed[wp.varName-'a']++;
                
	            st.push(wp);
	            opts.push(0);
	            
            }else{
                if(!st.empty()){
                    node tp=st.top();
                    st.pop();
                    
                    varNameIsUsed[tp.varName-'a']--;
                    
                    int nwOpt=(opts.top()+(tp.to==101&&tp.from!=101?1:0))*tp.ableToRun();
                    opts.pop();
                    int kkk=opts.top();
                    opts.pop();
                    kkk=max(kkk,nwOpt);
                    opts.push(kkk);
                }else{
                    isERR=true;
                }
            }
        }
        if(!st.empty()) isERR=true;
        
        int opsINT=0;
        if(ops=="O(1)") opsINT=0;
        else{
            for(int i=4;i<ops.length()-1;i++) opsINT=opsINT*10+ops[i]-'0';
        }
        
        if(isERR) cout<<"ERR"<<endl;
        else if(opsINT==opts.top()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        
        
    }
	
	return 0;
}