[nowcoder1100B]仓鼠的石子游戏
题目
传送门 to nowcoder
题目描述
仓鼠和兔子被禁止玩电脑，无聊的他们跑到一块空地上，空地上有许多小石子。
兔子捡了很多石子，然后将石子摆成 n n n 个圈，每个圈由 a i a_i ai 个石子组成。
然后兔子有两根彩色笔，一支红色一支蓝色。
兔子和仓鼠轮流选择一个没有上色的石子涂上颜色，兔子每次可以选择一个还未染色的石子将其染成红色，而仓鼠每次可以选择一个还未染色的石子将其染成蓝色。
仓鼠和兔子约定，轮流染色的过程中不能出现相邻石子同色，谁不能操作他就输了。
假设他们两个都使用了最优策略来玩这个游戏，并且兔子先手，最终谁会赢得游戏？
输入格式
第一行输入一个正整数 T T T ，表示有 T T T 组测试案例。
每组测试案例的第一行输入一个 n n n ，表示有 n n n 圈石子。 第二行输入 n n n 个正整数 a 1 , a 2 , a 3 , … , a n a_1,a_2,a_3,dots,a_n a1,a2,a3,…,an ，表示每个圈的石子数量。
输出格式
对于每组测试案例，如果兔子赢了，输出“ r a b b i t tt rabbit rabbit”(不含引号)如果仓鼠赢了，输出“ h a m s t e r tt hamster hamster”(不含引号)。
数据范围与约定
对于前 100 % 100% 100% 的数据，满足 1 ⩽ n ⩽ 1 0 3 , 1 ⩽ a i ⩽ 1 0 9 , 1 ⩽ T ⩽ 1 0 2 1leqslant n leqslant 10^3,1leqslant a_ileqslant 10^9,1leqslant Tleqslant 10^2 1⩽n⩽103,1⩽ai⩽109,1⩽T⩽102 。
思路壹
博弈题当然要 从最简单的情况开始找规律 啊！
其实，只有一个环的情况下，先手胜当且仅当 a = 1 a=1 a=1 （只有一个石子）。
可以考虑 对抗性 的策略：
假设 2 ∣ n 2|n 2∣n ，那么选择一条线作为对称轴，对称放置。假设 n n n 为奇数，在先手的位置旁边作为对称轴，对称放置。
故先手必败。现在把问题推向更复杂的情况：
假设有偶数个 a = 1 a=1 a=1 的环，先手涂一个 a = 1 a=1 a=1 的环，后手也涂一个；先手在哪个环里操作，我也在哪个环里操作。故后手必胜。
与之相对的，如果有奇数个 a = 1 a=1 a=1 的环，先手涂一个之后，就变成了上方的情况。 则先手必胜。
思路贰
本蒟蒻作者有一个不太博弈的方法……
思路壹的本质是，你能涂多少个，我也能涂多少个。
这提示我们计算每个人究竟能够操作多少次。如果先手的可操作次数 ≤ le ≤ 后手的可操作次数，那么先手将失败。
假设目前已经没有人可以操作了，考虑一个没有被涂色的石头，一定是一边是红色、一边是蓝色。
将所有的白石头拿走，剩下的环就会是红蓝相间的。不拿发现，这样的环上，红色点和蓝色点数量相同。
而且这 与操作顺序无关！无论是“兔子你随便涂，涂爽了再让我涂”还是“一人涂一次”，最后的红蓝点数量相同。
那么我们就要抢夺 a = 1 a=1 a=1 的环！因为这会拉开差距。
那么偶数的时候回平分秋色，回到普通环上，先手负（其可操作次数与后手相同）；奇数时先手略高一筹，后手负（其可操作次数比先手少 1 1 1 ）。得到了一样的结论。
代码
略。
相关知识
仓鼠救援游戏安卓版
工程常用的石料、石子、砂子种类，你搞清楚了吗？
有哪些好玩的仓鼠游戏?仓鼠游戏大全
洛阳洛宁砂石料厂家「大型沙场」石子河沙石粉
我的仓鼠游戏
重磅｜砂子140.33元/吨、石子131.50元/吨——山东部分地区砂石
仓鼠游戏有哪些2023 热门的仓鼠游戏分享
2024关于仓鼠的游戏大全 热门的仓鼠游戏盘点
2024有趣的仓鼠游戏有哪些 经典的仓鼠游戏推荐
热门的仓鼠游戏推荐2024 好玩的仓鼠题材的游戏合集
网址: [nowcoder1100B]仓鼠的石子游戏 https://m.mcbbbk.com/newsview982803.html
| 上一篇: 从远程桌面连接切换回主屏幕的快捷 |
下一篇: 【山东宠物鱼饲料颗粒批发市场】 |
