题解 P5698 【[CTSC1998]算法复杂度】

囧仙 · 2021-08-29 10:01:26 · 题解

题解

本题的循环仅存在数字和 n 两种情况，并且不存在判断语句，因此我们可以将整个程序转换为一个表达式：

对于 \text{op} 操作，我们可以看做在这个位置放置了一个数字（操作次数）。同时在它前面加一个加号。
对于 \text{continue} 和 \text{break} 操作，每当我们读取到它们时，就忽略接下来的所有运算，直到碰到当前循环的 \text{end} 语句。
对于 \text{loop} 语句（和 \text{begin} 语句），我们在该出放置一个左括号，同时在左括号前边放一个加号、后边放一个数字 \bm 0。如果对应的循环结构内存在 \text{break}，那么在左括号之前放置一个数字 1；否则放置 \text{loop} 语句执行的次数（数字或者 n）。
对于 \text{end} 语句，直接放置一个右括号，即可和对应 \text{loop} 语句的左括号匹配。

然后……对其中缀表达式求值，就做完了。以下我们举个例子（使用了样例）：

\begin{gathered}\boxed{\begin{aligned} &\verb!begin!\cr &\verb! loop n!\cr &\verb! loop 3!\cr &\verb! loop n!\cr &\verb! op 20!\cr &\verb! end!\cr &\verb! end!\cr &\verb! end!\cr &\verb! loop n!\cr &\verb! op 3!\cr &\verb! break!\cr &\verb! end!\cr &\verb! loop n!\cr &\verb! loop n!\cr &\verb! op 1!\cr &\verb! break!\cr &\verb! end!\cr &\verb! end!\cr &\verb!end!\cr \end{aligned}} \Rightarrow \boxed{\begin{aligned} &\verb!begin!\cr &\verb! loop n!\cr &\verb! loop 3!\cr &\verb! loop n!\cr &\verb! op 20!\cr &\verb! end!\cr &\verb! end!\cr &\verb! end!\cr &\verb! loop 1!\cr &\verb! op 3!\cr &\verb!!\cr &\verb! end!\cr &\verb! loop n!\cr &\verb! loop 1!\cr &\verb! op 1!\cr &\verb!!\cr &\verb! end!\cr &\verb! end!\cr &\verb!end!\cr \end{aligned}} \Rightarrow \boxed{\begin{aligned} &\verb!+(0!\cr &\verb! +n(0!\cr &\verb! +3(0!\cr &\verb! +n(0!\cr &\verb! +20!\cr &\verb! )!\cr &\verb! )!\cr &\verb! )!\cr &\verb! +1(0!\cr &\verb! +3!\cr &\verb!!\cr &\verb! )!\cr &\verb! +n(0!\cr &\verb! +1(0!\cr &\verb! +1!\cr &\verb!!\cr &\verb! )!\cr &\verb! )!\cr &\verb!)!\cr \end{aligned}} \end{gathered}

接着我们去除所有多余的空格和换行符。终于，我们得到了：

+(0+n(0+3(0+n(0+20)))+1(0+3)+n(0+1(0+1)))

计算它的值：

n(3\times 20n)+1\times 3+n\times 1\times 1=60n^2+n+3

具体操作的时候，就直接使用两个栈进行中缀表达式求值。（更详细的可以看这篇）。其中一个栈维护处理到的数字，另外一个栈维护处理到的运算符。数字入数字栈；每当碰到运算符时，不断取出运算符栈的栈顶，若优先级不小于当前的运算符，则不断取出数字栈栈顶的两个数字，运算后再推入数字栈，最后再将该运算符入栈；对于左括号直接入栈，碰到右括号则不断取运算符栈栈顶进行运算，知道碰到对应的左括号。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
struct Node{
    vector<i64> A; Node(){} Node(vector <i64> _A){A=_A;}
    Node operator +(const Node &t){
        Node r; r.A.resize(max(A.size(),t.A.size()));
        for(int i=0;i<r.A.size();++i)
            r.A[i]+=(i<A.size()?A[i]:0)+(i<t.A.size()?t.A[i]:0); return r;
    }
    Node operator *(const Node &t){
        Node r; r.A.resize(A.size()+t.A.size()-1);
        for(int i=0;i<A.size();++i)
            for(int j=0;j<t.A.size();++j)
                r.A[i+j]+=A[i]*t.A[j]; return r;
    }
    void wrt(){
        bool h=true; dn((int)A.size()-1,0,i) if(A[i]){
            if(!h) cout<<"+"; h=false;
            if(A[i]!=1||i==0) cout<<A[i];
            if(i==1) cout<<"n"    ; else
            if(i!=0) cout<<"n^"<<i;
        }
        if(h) cout<<"0"; cout<<endl;
    }
};
string x,y; stack<int> T; stack<Node> S; int n,f,g;
int main(){
    ios_base::sync_with_stdio(false); T.push(0);
    do{
        cin>>x;
        if(x=="begin"){
            T.push(0); S.push(Node({1})),S.push(Node({0}));
        } else
        if(x=="end"){
            if(g>1){--g;continue;}
            while(T.top()!=0){
                Node a=S.top(); S.pop();
                Node b=S.top(); S.pop();
                S.push(a+b),T.pop();
            }
            Node a=S.top(); S.pop();
            Node b=S.top(); S.pop();
            if(f==2) S.push(a); else S.push(a*b);T.pop(),f=0,--n;
        } else if(x=="loop"){
            if(f) {++g;continue;}
            cin>>y; T.push(1),T.push(0),++n;
            if(y=="n"||y=="0") S.push(Node({0,1}));
            else               S.push(Node({atoi(y.c_str())}));
            S.push(Node({0}));
        } else if(!f&&x=="op"){
            cin>>y; T.push(1);
            if(y=="n"||y=="0") S.push(Node({0,1}));
            else               S.push(Node({atoi(y.c_str())}));
        }
        else if(!f&&x=="continue"&&n!=0) f=1,g=1;
        else if(!f&&x=="break"   &&n!=0) f=2,g=1;
    }while(T.size()>1);
    S.top().wrt();
    return 0;
}