[USACO 2009 Ope S]Cow Digit Game

NC24877. [USACO 2009 Ope S]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 Ni (1 <= Ni <= 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 Ni = 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.

输入描述

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

输出描述

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

示例1

输入:

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.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 33ms, 内存消耗: 4192K, 提交时间: 2019-08-05 16:08:05

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int sg[N];
int main(){
for(int i=1;i<=1e6;i++){
int ma=0,mi=9,t=i;
while(t){
    int b=t%10;
    if(b){
    ma=max(b,ma);
    mi=min(b,mi);}
    t/=10;
}
sg[i]=(sg[i-ma]&sg[i-mi])^1;
}
int t;
scanf("%d",&t);
while(t--){
    int n;
    scanf("%d",&n);
    printf("%s",sg[n]?"YES\n":"NO\n");
}
return 0;}

C++11(clang++ 3.9) 解法, 执行用时: 32ms, 内存消耗: 4444K, 提交时间: 2019-08-12 11:18:17

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int sg[N];
int main()
{
	for(int i=1;i<=1e6;i++){
		int ma=0,mi=9,t=i;
		while(t){
			int b=t%10;
			if(b){
				ma=ma>b?ma:b;
				mi=mi<b?mi:b;
			}
			t/=10;
		}
		sg[i]=(sg[i-ma]&sg[i-mi])^1;
	}
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%s",sg[n]?"YES\n":"NO\n");
	}
	return 0;
}