博弈之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