博弈之nyoj 970 Yougth's Game II 题解

Yougth's Game II

描述

CET4的成绩出来了，Yougth考的很惨，为了调整心情，它决定去找CET4过了的Hrdv同学PK，当然作为一个有涵养的人，不能动不动就动手，于是他想了一个游戏和Hrdv去玩。

游戏是这样，由第三方任意给定k（1<=k<=100）个数字a1,a2,a3...ak，一开始，有x（1<=k<=10^4）枚硬币，Yougth和Hrdv轮流取硬币。每次取的硬币的枚数一定要在a1,a2,a3...ak当中。Yougth先取，还是老规矩，取走最后一枚硬币的一方获胜，而双方都非常聪明，采取最优策略，谁会获胜？

输入

多组测试数据，第一行两个数x和k
第二行是k个数a1,a2,a3...ak，为简化题目难度，k个数中一定有1.

输出

如果Yougth获胜输出“Wa,Yougth is Best!”
如果Hrdv获胜输出“Oh，Sorry！Yougth Lost!”

样例输入

9 2
1 4
10 2
1 4

样例输出

Wa,Yougth is Best!
Oh，Sorry！Yougth Lost!

题解报告

Yougth's Game II

这道题目是一道博弈题目，可以根据之前的分析博弈的方法进行分析。

首先Yougth先取，谁取完则获胜，那么谁如果面对当前有0个的局面则是必输点。

而k个数中的a1,a2,a3...ak则是先手的第一个必胜点。

推理发现必胜点加k个数中任意一个为必输点，而必输点加k个数中任意一个为必胜点。

所以对于任意一点x点。其胜负由（x-ai）决定。可以先出示x为先手必输点。假如他满足有任意一个x-ai是必输点的话，那么它一定是必胜点。

由此可得出答案，代码详见：

 
 #include 
      
       
#include 
       
         int a[110]; bool ans[11000]; int main() { int k,n; while(~scanf("%d%d",&n,&k)) { for(int i=0;i
        
         
 
         
 
        
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： C++预处理详解

下一篇： 最后一页

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");