首页 > 代码库 > BZOJ 1982 [Spoj 2021]Moving Pebbles（博弈论）
BZOJ 1982 [Spoj 2021]Moving Pebbles（博弈论）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1982
【题目大意】
两个人玩游戏. 每次任选一堆，首先拿掉至少一个石头,
然后移动任意个石子到任意堆中. 谁不能移动了，谁就输了
【题解】
首先如果对于奇数堆，那么先手必胜，因为可以构建必败态
对于偶数的情况，如果是石子堆两两相同的对称局面，则为必败态，反之必胜
【代码】
#include <cstdio>#include <algorithm>#include <string>using namespace std;string s[100010];char tmp[10010];int n;int main(){ scanf("%d",&n); if(n&1){puts("first player");return 0;} for(int i=1;i<=n;i++){scanf("%s",tmp);s[i]=tmp;} sort(s+1,s+n+1); for(int i=1;i<=n;i+=2)if(s[i]!=s[i+1]){puts("first player");return 0;} puts("second player"); return 0;}BZOJ 1982 [Spoj 2021]Moving Pebbles（博弈论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。