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后进行,然后依次轮流
下去,直到比赛结束。
众所周知, Wiki和Alpha都绝顶聪明,请问谁将赢得最终胜利?如果Wiki得到"卡哇伊"魔法权杖,请输
出"Wiki Wins";否则,输出"Wiki Loses"!
Input
第 一 行 输 入 两 个 正 整 数n和k, 表 示 魔 法 权 杖 需 要 的 能 量 值 和 能 量 水 晶 的 种 类 个
数(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 }