3404: [Usaco2009 Open]Cow Digit Game又见数字游戏
3404: [Usaco2009 Open]Cow Digit Game又见数字游戏
HansBug
发布于 2018-04-11 02:19:57
发布于 2018-04-11 02:19:57
代码可运行
运行总次数：0
代码可运行
3404: [Usaco2009 Open]Cow Digit Game又见数字游戏
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 72 Solved: 48
Description
贝茜和约翰在玩一个数字游戏．贝茜需要你帮助她．
游戏一共进行了G(1≤G≤100)场．第i场游戏开始于一个正整数Ni(l≤Ni≤1,000,000)．游
戏规则是这样的：双方轮流操作，将当前的数字减去一个数，这个数可以是当前数字的最大数码，也可以是最小的非0数码．比如当前的数是3014，操作者可以减去1变成3013，也可以减去4变成3010．若干次操作之后，这个数字会变成0．这时候不能再操作的一方为输家． 贝茜总是先开始操作．如果贝茜和约翰都足够聪明，执行最好的策略．请你计算最后的赢家．
比如，一场游戏开始于13.贝茜将13减去3变成10．约翰只能将10减去1变成9．贝茜再将9减去9变成0．最后贝茜赢．
Input
第1行输入一个整数G，之后G行一行输入一个Ni．
Output
对于每一场游戏，若贝茜能赢，则输出一行“YES”，否则输幽一行“NO”
Sample Input
2 9 10
Sample Output
YES NO
HINT
For the first game, Bessie simply takes the number 9 and wins.
For the second game, Bessie must take 1 (since she cannot take 0), and then
FJ can win by taking 9.Source
题解：很萌的博弈论问题。。。但是我还是在读题上逗比了N次——第一次我以为每次可以减去 1-最大的位数 ；第二次我以为可以减去 最小的位数-最大的位数 ；直到第三次才发现只可以减去最大位数和最小位数。。。别的没了，博弈论经典算法AC之
PS：不过虽然AC了，但是2800ms+，时限为3s，这个速度比较滚粗，于是本人打算明天再来一发优化题解么么哒！！！
1 /**************************************************************
2 Problem: 3404
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:2804 ms
7 Memory:9992 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n,t:longint;
12 a:array[0..1000005,1..2] of boolean;
13 b:array[0..1000005,1..2] of longint;
14 function max(x,y:longint):longint;
15 begin
16 if x>y then max:=x else max:=y;
17 end;
18 function min(x,y:longint):longint;
19 begin
20 if x<y then min:=x else min:=y;
21 end;
22 begin
23 a[0,1]:=false;a[0,2]:=true;
24 for i:=1 to 1000000 do
25 begin
26 j:=i;k:=1;t:=9;
27 while j>0 do
28 begin
29 k:=max(k,j mod 10);
30 if (j mod 10)>0 then t:=min(t,j mod 10);
31 j:=j div 10;
32 end;
33 a[i,1]:=false;
34 if a[i-t,2] then a[i,1]:=true;
35 if a[i-k,2] then a[i,1]:=true;
36 a[i,2]:=true;
37 if not(a[i-t,1]) then a[i,2]:=false;
38 if not(a[i-k,1]) then a[i,2]:=false;
39 end;
40 readln(n);
41 for i:=1 to n do
42 begin
43 readln(m);
44 if a[m,1] then writeln('YES') else writeln('NO');
45 end;
46 readln;
47 end.本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2015-04-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
