15011418730 LV 7 @ 2025-8-24 22:14:05

自动搬运

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:14:05，当前版本为作者最后更新于2023-04-20 19:55:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好水的紫题啊。。。

思路

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

首先按照每一行的行号，将每个语句及行号排列，这样可以避免题解区里广泛说的“数据行号中有 $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 也不长。

ID

4767

时间

1000ms

内存

125MiB

难度

标签

2000
NOI

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

思路

[NOI2000] 程序分析器

信息

1 条题解

自动搬运

以下是正文

思路

[NOI2000] 程序分析器

信息

还没有账户？

登录