3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 72  Solved: 48

[Submit][Status][Discuss]

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

Silver

题解:很萌的博弈论问题。。。但是我还是在读题上逗比了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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣谈编程

神速Hash

面试官: 聊聊HashMap的底层 理解HashMap底层,首先应该理解Hash函数,今天我们聊聊Hash函数出现冲突的解决办法(此故事为连载形式,若没看上篇...

2316
来自专栏marsggbo

(原创)详解KMP算法

KMP算法应该是每一本《数据结构》书都会讲的,算是知名度最高的算法之一了,但很可惜,我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

2667
来自专栏Jed的技术阶梯

Java设计模式之工厂方法模式

女娲补天的故事大家都听说过吧,今天不说这个,说女娲创造人的故事,可不是“造人”的工作,这个词被现代人滥用了。这个故事是说,女娲在补了天后,下到凡间一看,哇塞,风...

3042
来自专栏Albert陈凯

Scala简介:面向对象和函数式编程的组合

Scala简介 “Scala是一门现代的多范式编程语言,志在以简练、优雅及类型安全的方式来表达常用编程模式。它平滑地集成了面向对象和函数语言的特性。” Sc...

2796
来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 复赛1001&&HDU 6144 Arithmetic of Bomb【java大模拟】

Arithmetic of Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

3277
来自专栏一个会写诗的程序员的博客

React极简教程: Hello,World!React简史React安装Hello,World

A programming paradigm is a fundamental style of computer programming. There are...

901
来自专栏写代码的海盗

我们是80后 golang入坑系列

现在这个系列,已经开始两极分化了。 点赞的认为风格轻松,看着不困。反之,就有人嫌写的罗里吧嗦,上纲上线。所以善意提醒,里面不只是技术语言,还有段子。专心看技术的...

3517
来自专栏用户2442861的专栏

白话经典算法系列之六 快速排序 快速搞定

原文   http://blog.csdn.net/morewindows/article/details/6684558

1312
来自专栏雪胖纸的玩蛇日常

4. 高等数学——元素和极限

  假设我们知道了整数的定义,像-3,1,17这些都属于整数Z。然后有理数则是两个整数相除q/p ,q,p属于Z,则是有理数Q。

942
来自专栏专注数据中心高性能网络技术研发

[LeetCode]String主题系列{第5,6题}

1.内容介绍 本篇文章记录在leetcode中String主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

3507

扫码关注云+社区

领取腾讯云代金券