Problem G. Wiki with Alpha
Input file: standard input Time limit: 1 second
Output file: standard output Memory limit: 256 megabytes
最近,在拉布拉多星球举办了一场举世瞩目的人机智力pk赛。当然pk赛的主角依然是我们的Wiki同学,
他的对手是一个名为"Alpha"的超强机器人!比赛规定最终获得胜利的一方将会得到"卡哇伊"魔法权杖,
得到权杖的一方也将统治拉布拉多星球。
已知"卡哇伊"魔法权杖需要注入能量才能发挥威力。现在比赛现场一共有k种的能量水晶,不同的水晶可
能具有不同的能力值ai且每种能量水晶可以被使用无限次
现在比赛要求选手轮流将能量水晶注入魔法权杖之中,选手每次可以在这k种水晶中挑选任意一个注入魔
法权杖(选中的水晶必须用完,不能剩余),谁先为权杖注满能量(这里假设魔法权杖所需能量值为n,
满意味着刚好等于n,不能多于n),谁就赢得胜利。
由于在抛硬币的过程中, Wiki赢得了胜利,因此, Wiki先进行能量注入, Alpha后进行,然后依次轮流
下去,直到比赛结束。
众所周知, WikiAlpha都绝顶聪明,请问谁将赢得最终胜利?如果Wiki得到"卡哇伊"魔法权杖,请输
"Wiki Wins";否则,输出"Wiki Loses"
Input
第 一 行 输 入 两 个 正 整 数nk, 表 示 魔 法 权 杖 需 要 的 能 量 值 和 能 量 水 晶 的 种 类 个
(1 <= n <= 100000; 1 <= k <= 100)
2019蓝桥杯软件设计大赛上海理工大学校内选拔赛
December 08, 2019
接下来输入k个正整数ai(1 <= ai <= 10000),表示每种水晶的能量值,数与数之间用一个空格隔开(题目
保证ai中至少有一个为1
Output
输出比赛结果
Samples

standard input standard output
5 2
1 4
Wiki Loses
10 8
2 1 6 7 8 10 9 20
Wiki Wins



思路:记忆化博弈;(很巧妙)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4
 5 using namespace std ;
 6
 7 const int N = 100010, M = 110 ;
 8 int n, k ;
 9 bool st[N] ;
10 int q[110] ;
11
12 int main(){
13     cin >> n >> k ;
14
15     for(int i=0;i<k;i++){
16         cin >> q[i] ;
17     }
18
19     for(int i=1;i<=n;i++){
20         for(int j=0;j<k;j++){
21             if(i>=q[j] && !st[i-q[j]]){
22                 st[i] = 1 ;
23             }
24         }
25     }
26     if(st[n]){
27         cout << "Wiki Wins" << endl ;
28     }else{
29         cout << "Wiki Loses" << endl ;
30     }
31     return 0 ;
32 } 
12-14 09:41