自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:13:32，当前版本为作者最后更新于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;
}