首页 > 代码库 > Acdream1311_Apple

Acdream1311_Apple

2024-07-12 21:51:45   215人阅读

无聊的时候看到上一次acdream群赛的一个题目，中间居然是有alice和bob的博弈题目，于是就去做了。

给n，m，两人轮流操作，每次操作可以使n+1，或者m+1，谁操作后满足nm>=A，那么此人lose。

简单的博弈知识即可解决问题，如果当前状态的所有后继状态都是必胜态，那么该状态就是必败态；如果当前状态的后继状态中有一个是必败状态，那么这个状态就是必胜状态。

记忆化搜索。状态数其实不多sqrt(N)*log(N)，其中N=109。

不过要注意几种特殊情况，一开始n，m的幂就大于A的时候，不需要判断后继状态，直接是lose。如果n=1，而m=log2A，那么会是draw，因为谁加了n谁就输了，两人都不会动n。如果m=1，而n>=sqrt(A)，那么游戏只能沿着n增加的方向走动，直接判断步数只差的奇偶即可得出答案。剩下的问题就需要通过一些编程技巧来解决了。。。。

搜索的时候也是有一定技巧可言的。

 

 

召唤代码君：

 

 

/** this code is made by 092000* Problem: 1131* Verdict: Accepted* Submission Date: 2014-07-18 19:32:01* Time: 0MS* Memory: 10268KB*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std; int f[33333][33],tag[33333][33],TAG=520;int n,m,A; bool large(int x,int y){    int tot=1;    while (y)    {        if (y&1)        {            if (tot>A/x) return true;                else tot*=x;        }        y>>=1;        if (y && x>A/x) return true;            else x*=x;    }    return tot==A;} int dfs(int x,int y)//power(x,y){    if (tag[x][y]==TAG) return f[x][y];    tag[x][y]=TAG;    if (large(x,y)) return f[x][y]=-2;//power    if (x==1 && large(x+1,y)) return f[x][y]=0;    if (y==1 && large(x,y+1))    {        int tmp=A-x;        if (tmp&1) return f[x][y]=-1;            else return f[x][y]=1;    }    f[x][y]=-1;    int tmp1=dfs(x+1,y),tmp2=dfs(x,y+1);    if (tmp1>-2) f[x][y]=max(f[x][y],-tmp1);    if (tmp2>-2) f[x][y]=max(f[x][y],-tmp2);    return f[x][y];} int main(){    for (;scanf("%d%d%d",&n,&m,&A)!=EOF;TAG++)    {        if (dfs(n,m)==0) puts("draw");            else if (dfs(n,m)>0) puts("win");                else puts("lose");    }}


联系
我们