首页 > 代码库 > POJ 1704-Georgia and Bob(阶梯博弈)
POJ 1704-Georgia and Bob(阶梯博弈)
题目链接:点击打开链接
题意:n个棋子分布在x正半轴上,现在两人轮流往左移动棋子,要求不能碰到其他棋子不能越界(不能移动到负半轴),最后不能移动者拜。
等价成阶梯博弈,比如 2 5 7 9 ,如果5向左移动到3(移动了2格),那么7可以移动的范围就增大了两格。
具体阶梯博弈的了解看这里:点击打开链接
注意:最右边的阶梯相当于编号为1,而非最左边的。(因为总是往左移动)还有,这题要排序。。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1002 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair<int,int> #define ull unsigned long long using namespace std; int n,a[maxn]; void solve() { a[0]=0;int tem=0; for(int i=1;i<=n;i++){ scanf("%d",a+i); } sort(a,a+n+1); for(int i=n;i>=1;i-=2){ int d=a[i]-a[i-1]-1; tem^=d; } if(tem)puts("Georgia will win"); else puts("Bob will win"); } int main() { int T;scanf("%d",&T); while(T--){ scanf("%d",&n); solve(); } return 0; }
POJ 1704-Georgia and Bob(阶梯博弈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。