首页 > 代码库 > ZJU 1893 A Multiplication Game 【简单博弈】
ZJU 1893 A Multiplication Game 【简单博弈】
感觉ZJU上有不少博弈的题目。
这道题目还是比较好理解的，题目大概意思是：两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。
还是寻找必败点必胜点，不过在这个题目里转换成了寻找必败区间必胜区间的问题
以输入1000为例，我们可以倒着来，每个人除2到9之间的一个数
1000 | 999 ... 112 | 若占住999到112，则对手必胜。 必须让对手占领此段。
1000 | 999 ... 112 | 111 ... 56 | 因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。
如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1
| 必胜区间 | 必败区间 | 胜 | 败 | 胜
到此，思路已经非常明显。
Source Code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <fstream>#include <cstring>#include <cmath>#include <stack>#include <string>#include <map>#include <set>#include <list>#include <queue>#include <vector>#include <algorithm>#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))#define MOD 1000000007#define pi acos(-1.0)using namespace std;typedef long long ll ;typedef unsigned long long ull ;typedef unsigned int uint ;typedef unsigned char uchar ;template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}const double eps = 1e-7 ;const int N = 1 ;const int M = 200022 ;const ll P = 10000000097ll ;const int INF = 0x3f3f3f3f ;int main(){ int i, j, t, n, m, k; while(cin >> n){ bool flag = true; while(n > 1){ if(flag){ if(n % 9 == 0) n /= 9; else n = n / 9 + 1; } else{ if(n % 2 == 0) n /= 2; else n = n / 2 + 1; } flag =! flag; } if(!flag) cout << "Stan wins." << endl; else cout << "Ollie wins." << endl; } return 0;}
ZJU 1893 A Multiplication Game 【简单博弈】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。