洛谷 2953? [USACO09OPEN]牛的數字游戲Cow Digit Game

題目描述

Bessie is playing a number game against Farmer John, and she wants you to help her achieve victory.

Game i starts with an integer N_i (1 <= N_i <= 1,000,000). Bessie goes first, and then the two players alternate turns. On each turn, a player can subtract either the largest digit or the smallest non-zero digit from the current number to obtain a new number. For example, from 3014 we may subtract either 1 or 4 to obtain either 3013 or 3010, respectively. The game continues until the number becomes 0, at which point the last player to have taken a turn is the winner.

Bessie and FJ play G (1 <= G <= 100) games. Determine, for each game, whether Bessie or FJ will win, assuming that both play perfectly (that is, on each turn, if the current player has a move that will guarantee his or her win, he or she will take it).

Consider a sample game where N_i = 13. Bessie goes first and takes 3, leaving 10. FJ is forced to take 1, leaving 9. Bessie takes the remainder and wins the game.

貝茜和約翰在玩一個數字游戲．貝茜需要你幫助她．

游戲一共進行了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．最后貝茜贏．

輸入輸出格式

輸入格式：

* Line 1: A single integer: G

* Lines 2..G+1: Line i+1 contains the single integer: N_i

輸出格式：

* Lines 1..G: Line i contains 'YES' if Bessie can win game i, and 'NO' otherwise.?

輸入輸出樣例

輸入樣例： 2 9 10 輸出樣例： YES NO

說明

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.

其實，這一堆英文我也沒看懂，but，但是，我有翻譯器啊，hhh。

不過好像大家都有。

代碼

1 #include<cstdio> 2 #include<iostream> 3 bool win[1000010]; 4 int T,n,maxn,minn,x; 5 int main() { 6 scanf("%d",&T); 7 for(int i=1; i<=9; i++) win[i]=1; 8 for(int i=10; i<=1000010; i++) { 9 int s=i,t; 10 maxn=-1,minn=10; 11 while(s) { 12 t=s%10; 13 if(t>maxn&&t) maxn=t; 14 if(t<minn&&t) minn=t; 15 s/=10; 16 } 17 if(maxn!=-1) win[i]|=(!win[i-maxn]); 18 if(minn!=10) win[i]|=(!win[i-minn]); 19 } 20 while(T--) { 21 std::cin>>x; 22 if(win[x]) { 23 puts("YES"); 24 printf("\n"); 25 } else { 26 puts("NO"); 27 printf("\n"); 28 } 29 } 30 } 代，代代代碼

?

轉載于:https://www.cnblogs.com/GTBA/p/9068650.html

總結

以上是生活随笔為你收集整理的洛谷 2953 [USACO09OPEN]牛的数字游戏Cow Digit Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。