首页 > 代码库 > [原博客] POJ 2505 A multiplication game 组合游戏
[原博客] POJ 2505 A multiplication game 组合游戏
题目链接
题意： 有一个数p=1，甲乙两人轮流操作，每次可以把p乘2~9中的一个数，给定一个n，当一个人操作后p>=n,那么这个人赢，问先手是否必胜。
- 必胜状态：存在一种走法走到一个必败状态。
- 必败状态：后继状态都为必胜状态。
我们可以知道>=n的数都为必败状态，可以转移到>=n的最小的数为n/9（上取整），所以 n/9~n-1都为必胜态，同理n/9/2（都为上取整）为最小的必须转移到n/9~n-1（必胜状态）的状态，所以n/9/2~n/9-1为必败态，于是就可以这样推到1，看一下1是必胜态还是必败态输出即可。
ps. a/b（上取整）可以写为 (a-1)/b+1（整除）。方便运算。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring> //by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9); int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif LL n; while(~scanf("%lld",&n)){ bool ok; while(1){ LL p=(n-1)/9+1; if(1>=p){ ok=1;break; }else n=p; p=(n-1)/2+1; if(1>=p){ ok=0;break; }else n=p; } if(ok){ puts("Stan wins."); }else{ puts("Ollie wins. "); } } return 0;}
[原博客] POJ 2505 A multiplication game 组合游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。