首页 > 代码库 > POJ 2484-A Funny Game(对称博弈)
POJ 2484-A Funny Game(对称博弈)
题目链接:点击打开链接
题意:n个数 编号1-n 围成一个环,两个人轮流取,每次只能取相邻的两个或只取一个 ,不能取者败。
考虑这样一个问题,如果不是一个环而是一条线,即从1-n成一行排列,这样的话先手只要取中间的两个或一个构成左右个数相等(左右对称),那么先手就能立于不败之地(简单的说就是不管对手取哪一边,先手只要在另一边按照同样的方式取就能获胜)。
但这个问题是一个环,考虑特殊情况,当环的长度小于3的时候,先手必胜(直接全部拿走),但大于等于3的时候,任取其中一个就可以破环为线(链),然后因为线的时候先手必胜,所以此题答案是先手必败。
#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 10000002 #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; int main() { while(scanf("%d",&n)&&n){ if(n<3)puts("Alice"); else puts("Bob"); } return 0; }
POJ 2484-A Funny Game(对称博弈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。