POJ 2484A Funny Game(对称博弈) -电脑资料

电脑资料 时间:2019-01-01 我要投稿
【www.unjs.com - 电脑资料】

    题目链接:点击打开链接

    题意:n个数 编号1-n 围成一个环,两个人轮流取,每次只能取相邻的两个或只取一个 ,不能取者败,

POJ 2484A Funny Game(对称博弈)

    考虑这样一个问题,如果不是一个环而是一条线,即从1-n成一行排列,这样的话先手只要取中间的两个或一个构成左右个数相等(左右对称),那么先手就能立于不败之地(简单的说就是不管对手取哪一边,先手只要在另一边按照同样的方式取就能获胜)。

    但这个问题是一个环,考虑特殊情况,当环的长度小于3的时候,先手必胜(直接全部拿走),但大于等于3的时候,任取其中一个就可以破环为线(链),然后因为线的时候先手必胜,所以此题答案是先手必败。

   

#include #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 longusing namespace std;int n;int main(){	while(scanf("%d",&n)&&n){        if(n<3)puts("Alice");		else puts("Bob");	}	return 0;}

最新文章