ACM-ICPC青岛赛区网络预选赛 C Halting Problem
发布时间
阅读量：
阅读量
题目链接https://vjudge.net/problem/ZOJ-4049
题目中的难点：思路大家都很容易想到，并且复杂度理论上也不会超出预期范围。关键就在于细节处理上。特别是输入输出操作时需要注意的问题较多。不能使用memset这一函数（注：这里的"函数"实际上是关键字），多感谢队友的提醒吧！即使反复计算也会觉得没问题。
AC代码
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
char str[10];
int v;
int k;
};
#define N 10007
#define mod 256
node nodes[N+300];
int dp[N+300][259];
int n;
int tt;
bool dfs(int x,int y)
{
if(x>n)
return true;
if(dp[x][y]==tt)
return false;
dp[x][y]=tt;
if(strcmp("add",nodes[x].str)==0)
return dfs(x+1,(y+nodes[x].v)%mod);
if(strcmp("beq",nodes[x].str)==0)
{
if(y==nodes[x].v)
return dfs(nodes[x].k,y);
else
return dfs(x+1,y);
}
if(strcmp("bne",nodes[x].str)==0)
{
if(y!=nodes[x].v)
return dfs(nodes[x].k,y);
else
return dfs(x+1,y);
}
if(strcmp("blt",nodes[x].str)==0)
{
if(y<nodes[x].v)
return dfs(nodes[x].k,y);
else
return dfs(x+1,y);
}
if(strcmp("bgt",nodes[x].str)==0)
{
if(y>nodes[x].v)
return dfs(nodes[x].k,y);
else
return dfs(x+1,y);
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
tt=1;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",nodes[i].str);
if(nodes[i].str[0]=='a')
scanf("%d",&nodes[i].v);
else
scanf("%d %d",&nodes[i].v,&nodes[i].k);
}
if(dfs(1,0))
printf("Yes\n");
else
printf("No\n");
tt++;
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~