ICPC 2018 青岛网络预赛 C Halting Problem

xiaoxiao2021-03-01  11

【题目链接】

题目意思

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:; } }