[博弈]poj-2484

祝自己早日抽到不知火

http://poj.org/problem?id=2484

↑题目链接

题目大意：

爱丽丝和鲍勃决定玩一个有趣的游戏。在游戏开始时，他们选择n(1 <= n <= 106)个硬币围成一个圆圈。移走一个或两个相邻的硬币，而不动其他硬币。至少要取出一枚硬币。玩家们轮流走几步，爱丽丝先走。取出最后一枚硬币的玩家获胜。(最后一个取走硬币的玩家获胜。如果你不能取走硬币，你就输了。

注:对于n > 3，我们使用c1, c2，…， cn表示硬币顺时针方向，如果爱丽丝移去c2，则c1和c3不相邻!(因为c1和c3之间有一个空位置。)

本周是博弈专题 这个题很基础 当n小于3时 （n=1或者n=2时）爱丽丝直接取走就获得胜利了 当N大于三时 我想出后手必胜的方法是 一个环当先手的人走完之后必定是一个偶数或者奇数的链 后手将这条链再分为两个长度相等的链 之后无论先手作什么 对着另一条链做相同的操作 即能达到必胜。

[cpp] #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const int eps = 1e-7; const int maxbit = 30; const int maxn = 200005; const double PI = 3.14; using namespace std; int main() { ios::sync_with_stdio(0); int n; while (cin >> n, n) { if (n < 3) cout << “Alice\n”; else cout << “Bob\n”; } return 0; } [/cpp]

uncategorized > POJ
[博弈]poj-2484
https://47.97.0.163/2019/04/23/trashed/
作者
John Doe
发布于
2019年4月23日
许可协议