bzoj 3404: [Usaco2009 Open]Cow Digit Game又见数字游戏（SG函数）

3404: [Usaco2009 Open]Cow Digit Game又见数字游戏Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 181 Solved: 124[Submit][Status][Discuss]Description 贝茜和约翰在玩一个数字游戏．贝茜需要你帮助她．游戏一共进行了G(1≤G≤1

Jaihk662

897人浏览 · 2017-07-22 13:08:35

Jaihk662 · 2017-07-22 13:08:35 发布

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

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 181 Solved: 124
[ 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

Sample Output

YES

和丢史蒂芬妮一模一样

记忆化搜索或SG打表

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1000005];
int Sech(int x)
{
	int temp, mn, mx;
	if(dp[x]!=-1)
		return dp[x];
	temp = x;
	mn = 10, mx = 0;
	while(temp)
	{
		if(temp%10!=0)
		{
			mn = min(mn, temp%10);
			mx = max(mx, temp%10);
		}
		temp /= 10;
	}
	if(Sech(x-mn)==0 || Sech(x-mx)==0)
		dp[x] = 1;
	else
		dp[x] = 0;
	return dp[x];
}
int main(void)
{
	int T, n;
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		if(Sech(n))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

操作系统大会&openEuler Summit 2024参会指南，请查收！