| 题目名称 | 763. [USACO Open09] 数字的游戏 |
|---|---|
| 输入输出 | cdgame.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-04-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：35， 提交：81， 通过率：43.21% | ||||
 甘罗 |
100 | 0.057 s | 7.15 MiB | C++ |
 Marvolo |
100 | 0.057 s | 7.94 MiB | C++ |
 thomount |
100 | 0.082 s | 4.10 MiB | C++ |
 /k |
100 | 0.123 s | 4.13 MiB | C++ |
 CAX-DY |
100 | 0.125 s | 2.07 MiB | Pascal |
 CAX_CPG |
100 | 0.144 s | 1.12 MiB | Pascal |
 QhelDIV |
100 | 0.168 s | 2.25 MiB | C++ |
 ppfish |
100 | 0.168 s | 38.46 MiB | C++ |
 nancheng58 |
100 | 0.178 s | 3.72 MiB | C++ |
 song |
100 | 0.182 s | 4.08 MiB | C++ |
| 本题关联比赛 | |||
| 20120416 | |||
| EYOI与SBOI开学欢乐赛12th | |||
| 关于 数字的游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
+1
| ||||
|
简单的动态规划
QhelDIV
2012-04-16 14:25
1楼
| ||||
苏轼【题目描述】
Bessie正跟FJ玩一个数字游戏，她想让你帮她赢。
游戏的第$i$局由一个整数$N_i(1 \leq N_i \leq 1,000,000)$开始，Bessie先手，接下来两个人交替进行，轮到谁时，她（他）可以在当前整数中挑一个最大的或最小的非零数字，并减去该数字，所得的差成为新的游戏数。比如若当前整数为3014，我们可以从中减去最大数字4或最小非零数字1，得数为3010或3013。每一局游戏以得到数0为结束，而得0的选手为胜利一方。
Bessie与FJ一共要玩$G(1 \leq G \leq 100)$局，请确定每局游戏的胜者，假定他们两个都玩得很好（这意味着每轮到一方执手，他都会怎么能赢就怎么做）。
举个例子：起初$N_i=13$,Bessie先手，她选了数字3，减去后得10，FJ只能选数字1，减去后得9，Bessie选数字9，减去后得到0，Bessie赢。
【输入格式】
第$1$行：一个整数$G$；
第$2\sim G+1$行:第$i+1$行包含一个整数$N_i$。
【输出格式】
共$G$行，如果第$i$局Bessie赢则在第i行输出"YES"，如果Bessie不能赢则第$i$行的输出为"NO"。
【输入格式】
2 9 10
【输出格式】
YES NO
【样例解释】
第一局，Bessie只需选9减去即赢；第二局，Bessie只能选1（不能选0），然后FJ选9减去即赢。