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

2023-02-26 13:07:35

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，这个速度比较滚粗，于是本人打算明天再来一发优化题解么么哒！！！

 /**************************************************************

     Problem:

     User: HansBug

     Language: Pascal

     Result: Accepted

     Time: ms

     Memory: kb

 ****************************************************************/

 var

    i,j,k,l,m,n,t:longint;

    a:array[..,..] of boolean;

    b:array[..,..] of longint;

 function max(x,y:longint):longint;

          begin

               if x>y then max:=x else max:=y;

          end;

 function min(x,y:longint):longint;

          begin

               if x<y then min:=x else min:=y;

          end;

 begin

      a[,]:=false;a[,]:=true;

      for i:= to  do

          begin

               j:=i;k:=;t:=;

               while j> do

                     begin

                          k:=max(k,j mod );

                          if (j mod )> then t:=min(t,j mod );

                          j:=j div ;

                     end;

               a[i,]:=false;

               if a[i-t,] then a[i,]:=true;

               if a[i-k,] then a[i,]:=true;

               a[i,]:=true;

               if not(a[i-t,]) then a[i,]:=false;

               if not(a[i-k,]) then a[i,]:=false;

          end;

      readln(n);

      for i:= to n do

          begin

               readln(m);

               if a[m,] then writeln('YES') else writeln('NO');

          end;

      readln;

  end.

码农公寓