ICPC 2018 青岛网络预赛 C Halting Problem

【题目链接】

题目意思

图灵停机问题，判断是否会停机，停机输出Yes，否则No。

Sample Input
4
2
add 1
blt 5 1
3
add 252
add 1
bgt 252 2
2
add 2
bne 7 1
3
add 1
bne 252 1
beq 252 1
Sample Output
Yes
Yes
No
No

Hint

For the second sample test case, note that is a 8-bit register, so after four “add 1” instructions the value of will change from 252 to 0, and the program will halt.

For the third sample test case, it’s easy to discover that the value of will always be even, so it’s impossible for the value of to be equal to 7, and the program will run forever.

解题思路

1.记忆化搜索，记录这一步某个数字是否出现过，若出现过，则可判断不会停机，否则，可停机。
2.标记是否出现过的数组千万别用int啊，要用bool，memset bool类型的数组只用了200ms，memset int类型用了900ms，怪不得比赛一直tle，QAQ。

AC代码

#include <iostream>
#include <cstring>
char s[10005][10];
int f[10005][2];
bool v[10005][258];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(v, 0, sizeof v);
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%s", s[i]);
			if (s[i][1] == 'd')
				scanf("%d", &f[i][0]);
			else
				scanf("%d%d", &f[i][0], &f[i][1]);
		}
		int flag = 1, num = 0;
		while (flag <= n)
		{
			if (v[flag][num])
			{
				printf("No\n");
				goto qwe;
			}
			v[flag][num] = true;
			if (s[flag][1] == 'd')
			{
				num += f[flag][0];
				num %= 256;
				flag++;
			}
			else if (s[flag][1] == 'e')
			{
				if (num == f[flag][0])
					flag = f[flag][1];
				else
					flag++;
			}
			else if (s[flag][1] == 'n')
			{
				if (num != f[flag][0])
					flag = f[flag][1];
				else
					flag++;
			}
			else if (s[flag][1] == 'l')
			{
				if (num < f[flag][0])
					flag = f[flag][1];
				else
					flag++;
			}
			else if (s[flag][1] == 'g')
			{
				if (num > f[flag][0])
					flag = f[flag][1];
				else
					flag++;
			}
		}
		printf("Yes\n");
	qwe:;
	}
}