P5756 [NOI2000] 程序分析器 题解

· · 题解

好水的紫题啊。。。

思路

看到题解区都是依次枚举的行数，而我的做法是将每行排序，然后从小到大遍历。

首先按照每一行的行号，将每个语句及行号排列，这样可以避免题解区里广泛说的“数据行号中有 0 行”的问题。

既然排序了，那么我们的行号可以进行一个小小的改变，虽然叫的是几几行，但是我们完全可以按照之前排好的序来排啊，然后开一个桶记录每行所对应的是数组的第几个序号，当之后的 GO 语句访问时，直接访问桶中的数据好了。

读入行数时别忘吞空格。

接下来是对于每个语句的细节：

首先对于 END 操作直接输出没什么好说的。

当是 GO 语句时，发现里面的数字不是特别方便转字符，这时候我们可以用快读模板的方法一位一位来算，然后用得出的数字访问桶好了。

当是变量加法的语句时，我们发现我们还没有存当前的值，这时候我们要想怎么记录，不难想到 map 中是可以以 char 类型作为下标的，于是只要将 map 中的数加上所要加上的值即可。

当是 IF 语句时，只需判断变量对应的值是否相等，如果相等直接执行 GO 语句就行了。

如果当前顺序执行完，下标还是那个下标，直接自增 1。

注意判断超时的次数开到 10^7。

按这个思路，不难打出如下代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
#define f(W, X, Y, Z) for(int W = X; W <= Y; W += Z)
#define F(W, X, Y, Z) for(int W = X; W >= Y; W -= Z)
#define debug puts("QAQ")
namespace SyxQwQ{
    inline int qwq(){
        return 0;
    }
    struct _{
        string s;
        int line;
    }p[114];
    bool cmp(_ a, _ b){
        return a.line < b.line;
    }
    int checkline[3111];
    map<int, int> a;
    map<char, int> z;
    int doingtime = 0, nowline;
    inline int getnowz(int &i){
        //debug;
        int x = 0;
        while(p[nowline].s[i] > '9' || p[nowline].s[i] < '0') ++i;
        while(p[nowline].s[i] <= '9' && p[nowline].s[i] >= '0'){
            //cout << p[nowline].s[i];
            //x = (x << 3) + (x << 1) + (p[nowline].s[i] - '0');
            x = x * 10 + (p[nowline].s[i] - '0');
            ++i;
        }
        //cout << x << " ";
        return x;
    }
    inline void func(){
        p[nowline].s += " ";
        int l = p[nowline].s.size();
        doingtime++;
        //cout << nowline << " ";
        if(doingtime > 10000000){
            printf("-1\n");
            exit(0);
        }
        //if(p[nowline].line == 50) cout << p[nowline].s.size() << '\n';
        for(int i = 0; i < l; i++){
            //debug;
            //if(p[nowline].line == 50) cout << p[nowline].s[i];

            if(p[nowline].s[i]=='E' && p[nowline].s[i+1]=='N' && p[nowline].s[i+2]=='D'){
                //debug;
                printf("%lld\n", doingtime);
                exit(0);
            }else if(p[nowline].s[i] == 'G' && p[nowline].s[i+1] == 'O'){
                //debug; 
                nowline = a[getnowz(i)];
                return ;
            }else if(p[nowline].s[i] == 'I' && p[nowline].s[i+1] == 'F'){
                //debug;
                i += 3;
                int sjh = z[p[nowline].s[i]];
                i += 2;
                int q = getnowz(i);
                //cout << q << '\n';
                if(sjh == q){
                    nowline = a[getnowz(i)];
                    return ; 
                }else{
                    nowline++;
                    return ;
                }
            }
            else if(p[nowline].s[i] >= 'A' && p[nowline].s[i] <= 'Z'){
                char sjh = p[nowline].s[i];
                //debug;
                ++i;
                if(p[nowline].s[i] == '?') continue;
                else if(p[nowline].s[i] == '+'){
                    int o = getnowz(i);
                    z[sjh] += o;
                    ++i;
                    //cout << z[o] << ' ';
                }
            }
        }
        //debug;
        ++nowline;
        return ;
    }
    inline int main(){
        int len = 0;
        while(cin >> p[++len].line){
            getchar();
            getline(cin, p[len].s);
        }
        --len;
        sort(p + 1, p + 1 + len, cmp);
        f(j, 1, len, 1){
            a[p[j].line] = j;
            //cout << p[j].line << '\n';
        }
        nowline = 1;
        while(1) func();
        printf("%lld\n", doingtime);
        return qwq();
    }
}
signed main(){
    SyxQwQ::main();
    return 0;
}

但是交上去，发现 TLE 了 3 个点，此时考虑优化。

可以发现，语句一共就只有 100 句，如果要 TLE，其中肯定执行了许多次重复的语句，我们可以把所有的代码的要标记和执行的预先处理出来，当跳到那一行时，只需对应判断即可，这样可以省掉每次跳到那里循环一次的复杂度。

但是思考要处理哪些标记是真的烦。

我是这么搞标记的：

是否有 END；

是否是 GO 语句，如果是，跳转到哪一行；

是否有 IF，判断的是哪个变量，判断的是改变量对应的哪个值，如果成立要 GO 到哪一行；

是否是变量增加，加的是哪个变量，加的是几。

于是就有了这份代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
#define f(W, X, Y, Z) for(int W = X; W <= Y; W += Z)
#define F(W, X, Y, Z) for(int W = X; W >= Y; W -= Z)
#define debug puts("QAQ")
namespace SyxQwQ{
    inline int qwq(){
        return 0;
    }
    struct _{
        string s;
        int line;
        bool willend, willgo, willif, willplus;
        int gotowhere, ifvalue, ifgoto, plusvalue;
        char ifchar, pluschar;

    }p[114];
    bool cmp(_ a, _ b){
        return a.line < b.line;
    }
    map<int, int> a;
    map<char, int> z;
    int doingtime = 0, nowline;
    inline int getnowz(int &i){
        //debug;
        int x = 0;
        while(p[nowline].s[i] > '9' || p[nowline].s[i] < '0') ++i;
        while(p[nowline].s[i] <= '9' && p[nowline].s[i] >= '0'){
            x = x * 10 + (p[nowline].s[i] - '0');
            ++i;
        }
        //cout << x << " ";
        return x;
    }
    inline void func(){
        p[nowline].s += " ";//不加会RE
        int l = p[nowline].s.size();
        for(int i = 0; i < l; i++){
            if(p[nowline].s[i]=='E' && p[nowline].s[i+1]=='N' && p[nowline].s[i+2]=='D'){
                //printf("1\n");
                p[nowline].willend = 1;
                return ;
            }else if(p[nowline].s[i] == 'G' && p[nowline].s[i+1] == 'O'){
                //printf("2\n");
                p[nowline].willgo = 1;
                p[nowline].gotowhere = getnowz(i);
                return ;
            }else if(p[nowline].s[i] == 'I' && p[nowline].s[i+1] == 'F'){
                //printf("3\n");
                p[nowline].willif = 1;
                i += 3;
                p[nowline].ifchar = p[nowline].s[i];
                i += 2;
                p[nowline].ifvalue = getnowz(i);
                p[nowline].ifgoto = getnowz(i);
                return ; 
            }
            else if(p[nowline].s[i] >= 'A' && p[nowline].s[i] <= 'Z'){
                //printf("4\n");
                p[nowline].pluschar = p[nowline].s[i];
                ++i;
                if(p[nowline].s[i] == '?') continue;
                else if(p[nowline].s[i] == '+'){
                    p[nowline].willplus = 1;
                    p[nowline].plusvalue = getnowz(i);
                    ++i;
                }
            }
        }
        return ;
    }
    inline void check(){
        doingtime++;
        if(doingtime > 5000000){
            printf("-1\n");
            exit(0);
        }
        if(p[nowline].willend){
            printf("%lld\n", doingtime);
            exit(0);
        }else if(p[nowline].willplus){
            z[p[nowline].pluschar] += p[nowline].plusvalue;
        }else if(p[nowline].willgo){
            //debug;
            nowline = a[p[nowline].gotowhere];
            return ;
        }else if(p[nowline].willif){
            //if('A' == p[nowline].ifchar) printf("%lld\n", p[nowline].ifgoto);
            if(z[p[nowline].ifchar] == p[nowline].ifvalue){
                nowline = a[p[nowline].ifgoto];
                return ;
            }
        }
        nowline++;
    }
    inline int main(){
        int len = 0;
        while(cin >> p[++len].line){
            //if(p[len].line == 2800) debug;
            getchar();
            getline(cin, p[len].s);
        }
        --len;
        sort(p + 1, p + 1 + len, cmp);
        f(j, 1, len, 1){
            a[p[j].line] = j;
            nowline = j;
            //if(p[j].line == 2800) debug;
            func();
        }
        nowline = 1;
        while(1){
            //printf("%lld\n", z['A']);
            check();
            //printf("%lld\n", nowline);
        }
        //printf("%lld\n", doingtime);
        return qwq();
    }
}
signed main(){
    //freopen("QAQ.out", "w", stdout);
    SyxQwQ::main();
    //fclose(stdout);
    return 0;
}

别说跑的真挺快的，目前最优解。

3KB 也不长。