Busy Beavers(暴力模拟)

时间:2022-11-14 06:22:48

由于排版问题,题目无法显示,可以到 http://7xjob4.com1.z0.glb.clouddn.com/e4872a15819b6bf9d1e5250bacc2a30b  查看

题目大意是有只海狸在一排无穷多的好树上,起始心情是A,问经过一系列操作后,能否心情好(心情变成H)。

给出十组数据分别代表,A心情时,对好树的操作,A心情时,对坏树的操作,B心情时,对好树的操作,B心情时,对坏树的操作。。。以此类推

具体的操作有三种,给出的三个字符分别代表三种操作。第一种1和0代表,把当前的树变成坏树(1)或者好树(0);第二种L和R代表往左移动(L)或者往右移动(R);第三种字符(A~E和H)代表经过这树后的心情会变成什么。

那么我们可以用一个数组M,记录当前心情和树的状态为某个值时对应的操作。比如M[0]代表A心情时对好树的操作,M[1]代表A心情时对坏树的操作,以此类推。。

我们再开一个2e的bool数组模拟树的状态,我们从下标为1e的点开始,起始状态为A心情,好树,那我们就对应选择M[0]操作,假设M[0]为1RB,那我们把这树的状态改为1(坏树),然后心情变为B,然后向右走,此时海狸心情为B,树为好树,那我们对应选择M[2]。。。然后模拟5000w次,如果找到H心情,则break。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e8;
bool tree[*maxn];
struct node{
bool ok;//代表要将树变成什么状态
int step;//代表下一步动作
int mood;//0,2,4,6,8,14分别代表心情A,B,C,D,E,H
}M[];
char str[];
int main()
{
freopen("beavers.in","r",stdin);
freopen("beavers.out","w",stdout);
for (int i=;i<;i++)
{
scanf("%s",str);
M[i].ok=str[]-'';
M[i].step=(str[]=='L')?-:;
M[i].mood=*(str[]-'A');
}
int pos=maxn,Mood=,ok=;//下标从1e开始,起始心情为0
int all=;//一共模拟5000w次
while (all--)
{
bool cur=tree[pos];
tree[pos]=M[Mood+cur].ok;//改变树的状态
pos+=M[Mood+cur].step;//移动
Mood=M[Mood+cur].mood;//改变心情
if (Mood==)//14代表H,如果遇到H,break
{
ok=;
break;
}
}
if (ok) puts("happy beaver");
else puts("unhappy beaver");
return ;
}