【bzoj1982】【Spoj2021】【Moving Pebbles】【博弈论】
发布日期:2021-11-16 15:38:08
浏览次数:25
分类:技术文章
本文共 1244 字,大约阅读时间需要 4 分钟。
Description
2021. Moving Pebbles Two players play the following game. At the beginning of the game they start with n (1<=n<=100000) piles of stones. At each step of the game, the player chooses a pile and remove at least one stone from this pile and move zero or more stones from this pile to any other pile that still has stones. A player loses if he has no more possible moves. Given the initial piles, determine who wins: the first player, or the second player, if both play perfectly. 给你N堆Stone,两个人玩游戏. 每次任选一堆,首先拿掉至少一个石头,然后移动任意个石子到任意堆中. 谁不能移动了,谁就输了...
Input
Each line of input has integers 0 < n <= 100000, followed by n positive integers denoting the initial piles.
Output
For each line of input, output "first player" if first player can force a win, or "second player", if the second player can force a win.
Sample Input
3 2 1 3
Sample Output
first player
题解:博弈论的题都好神奇。
考虑如果这些石子能够两两配对配成n/2组(n为偶数),则是先手必败的。
因为这种情况下无论先手如何操作,后手都可以让局面回到等价的状态。
其余情况下先手必胜,因为其余情况下先手都有办法将局面变成先手必败。
代码:
#include#include #include using namespace std;int n,a[100010];int main(){ cin>>n; if (n&1){cout<<"first player"< >a[i]; sort(a+1,a+n+1); for (int i=1;i<=n;i+=2) if (a[i]!=a[i+1]){ cout<<"first player"<
转载地址:https://blog.csdn.net/sunshinezff/article/details/50916392 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月15日 22时09分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
什么是A记录、MX记录、CNAME记录
2021-06-30
MongoDB简介
2021-06-30
Varnish purges 缓存清除
2021-06-30
Linux下redis安装部署
2021-06-30
水平切分与垂直切分
2021-06-30
MySQL引擎
2021-06-30
MySQL下的NoSQL解决方案HandlerSocket
2019-04-27
Apache服务器下使用 ab 命令进行压力测试
2019-04-27
查看Firefox中的缓存
2019-04-27
http header头设置反向代理不缓存
2019-04-27
配置MySQL主从复制
2019-04-27
CI框架如何删除地址栏的 index.php
2019-04-27
expires与etag控制页面缓存的优先级
2019-04-27
取消掉Transfer-Encoding:chunked
2019-04-27
HTTP协议中的Tranfer-Encoding:chunked编码解析
2019-04-27
JavaScript面向对象编程
2019-04-27
在Javascript中使用面向对象的编程
2019-04-27
由浅入深剖析.htaccess
2019-04-27
php函数serialize()与unserialize()
2019-04-27
PHP Webservice的发布与调用
2019-04-27