题解 P2229 【[HNOI2002]沙漠寻宝】

· · 题解

这题一看就知道是个模拟。

做模拟题的时候，一定要先确保你的程序能跑出正确的结果，再去想优化时间。

这道题还是很简单的，让我们开始吧：

读入

我们把输入离线，拿 string 存起来。如果不离线，那 loop 就会很难处理，加大难度。

int n;
string a[1010];//亲测最多只会有 1000 条语句

while(cin>>a[++n]);n--;

预处理

我们可以先预处理每个 start 和 loop 对应的 end 的位置。这样做的原因会在后面说。

int jump[1010];
stack<int> init;
for(int i=1;i<=n;i++){
    if(a[i]=="start"||a[i]=="loop") init.push(i);//如果是 start/loop，把编号压入栈
    if(a[i]=="end") jump[init.top()]=i,init.pop();//如果是 end，标记位置
}

运行代码

定义一个 int run(int now) 函数，使用递归实现，now 表示从哪条语句开始运行，返回值表示最终执行到哪条语句。

但我们要考虑一个问题：遇到 break 该返回什么呢？我们可以返回 -1，然后特判一下。

int run(int now){
    for(int i=now;i<=n;i++){
        if(a[i]=="write"){
        //write：输出一个表达式的值并换行
        //那就输出 a[i+1] 这个表达式的值咯
            i++;
            cout<<calc(a[i])<<endl;//这个 calc 是计算函数，后面讲
        }else if(a[i]=="loop"){
        //loop：循环语句，执行 a[i+1] 次
        //那就递归实现
            i++;
            int times=calc(a[i]);
            for(int j=1;j<=times;j++){
                int tmp=run(i+1);
                if(tmp==-1) break;//返回 -1 说明是 break，外层 loop 也跟着 break 
            }
            i=jump[i-1];//jump 的作用，跳到这个 loop 后面
        }else if(a[i]=="break"){
            return -1;//返回 -1，代表自己是 break
        }else if(a[i]=="continue"){ 
            return jump[now-2];//返回这个这个 loop 对应的 end 的位置
        }else if(a[i]=="end"){
            return i;//同 continue
        }else if(a[i]=="start"){
            //什么也不做哈哈哈
        }else{//都不是，那就是赋值语句
            int tmp=calc(a[i].substr(2));//substr(2) 表示从 2 这个位置后面的所有字符
            m[a[i][0]-'a']=tmp;//赋值
        }
    }
    return n;
}

计算表达式

这部分可以看 link，照着他的代码打一遍就好了。

int lev(char a){//优先级
    switch(a){
        case '(':return 0;
        case '+':case '-':return 1;
        case '*':case '/':return 2;
        case ')':return 3;
    }
    return 0;
}
void plu(stack<int> &s,char op){//需要注意，plus 是 STL 函数
    int num1,num2;
    num2=s.top(),s.pop();
    num1=s.top(),s.pop();
    switch(op){
        case '+':s.push(num1+num2);return ;
        case '-':s.push(num1-num2);return ;
        case '*':s.push(num1*num2);return ;
        case '/':s.push(num1/num2);return ;
    }
}
int calc(string a){//计算函数
    stack<int> s1,s2;
    for(int i=0;i<a.size();i++){
        if('a'<=a[i]&&a[i]<='z') s1.push(m[a[i]-'a']);//处理变量
        else if('0'<=a[i]&&a[i]<='9'){//数字
            int tmp=a[i]-48,j=i+1;
            while(j<a.size()&&'0'<=a[j]&&a[j]<='9') tmp=tmp*10-48+a[j],j++;
            s1.push(tmp),i=j-1;
        }else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){//加减乘除
            if(s2.empty()) s2.push(a[i]);
            else{
                while(!s2.empty()&&lev(s2.top())>=lev(a[i])){
                    plu(s1,s2.top());
                    s2.pop();
                }
                s2.push(a[i]);
            }
        }else{//括号
            if(a[i]=='(') s2.push(a[i]);
            else{
                while(s2.top()!='('){
                    plu(s1,s2.top());
                    s2.pop();
                }
                s2.pop();
            }
        }
    }
    while(!s2.empty()){
        plu(s1,s2.top());
        s2.pop();
    }
    return s1.top();
}

整合

把上面的代码结合在一起就能 A 了。

完整代码：

#pragma GCC optimize(2)
//这篇题解常数很大，会 TLE on #5，需要 O2 优化 
#include <stack>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
string a[1010];
int n,m[30],jump[1010];
int lev(const char &a){
    switch(a){
        case '(':return 0;
        case '+':case '-':return 1;
        case '*':case '/':return 2;
        case ')':return 3;
    }
    return 0;
}
void plu(stack<int> &s,const char &op){
    int num1,num2;
    num2=s.top(),s.pop();
    num1=s.top(),s.pop();
    switch(op){
        case '+':s.push(num1+num2);return ;
        case '-':s.push(num1-num2);return ;
        case '*':s.push(num1*num2);return ;
        case '/':s.push(num1/num2);return ;
    }
}
int calc(const string &a){
    stack<int> s1,s2;
    for(int i=0;i<a.size();i++){
        if('a'<=a[i]&&a[i]<='z') s1.push(m[a[i]-'a']);
        else if('0'<=a[i]&&a[i]<='9'){
            int tmp=a[i]-48,j=i+1;
            while(j<a.size()&&'0'<=a[j]&&a[j]<='9') tmp=tmp*10-48+a[j],j++;
            s1.push(tmp),i=j-1;
        }
        else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
            if(s2.empty()) s2.push(a[i]);
            else{
                while(!s2.empty()&&lev(s2.top())>=lev(a[i])){
                    plu(s1,s2.top());
                    s2.pop();
                }
                s2.push(a[i]);
            }
        }else{
            if(a[i]=='(') s2.push(a[i]);
            else{
                while(s2.top()!='('){
                    plu(s1,s2.top());
                    s2.pop();
                }
                s2.pop();
            }
        }
    }
    while(!s2.empty()){
        plu(s1,s2.top());
        s2.pop();
    }
    return s1.top();
}
int run(const int &now){
    for(int i=now;i<=n;i++){
        if(a[i]=="write"){
            i++;
            cout<<calc(a[i])<<endl;
        }else if(a[i]=="loop"){
            i++;
            int times=calc(a[i]);
            for(int j=1;j<=times;j++){
                int tmp=run(i+1);
                if(tmp==-1) break;
            }
            i=jump[i-1];
        }else if(a[i]=="break"){
            return -1;
        }else if(a[i]=="continue"){
            return jump[now-2];
        }else if(a[i]=="end"){
            return i;
        }else if(a[i]=="start"){
            //f**k ccf
        }else{
            int tmp=calc(a[i].substr(2));
            m[a[i][0]-'a']=tmp;
        }
    }
    return n;
}
stack<int> init;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    while(cin>>a[++n]);n--;
    for(int i=1;i<=n;i++){
        if(a[i]=="start"||a[i]=="loop") init.push(i);
        if(a[i]=="end") jump[init.top()]=i,init.pop();
    }
    run(1);
    return 0;
}