自动搬运

查看原文

来自洛谷，原作者为

	konjacq 对不起 给大家丢脸了

搬运于2025-08-24 21:43:47，当前版本为作者最后更新于2018-08-19 15:26:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每种状态可以转移出两个新状态。博弈论的结论：

当某种状态的后继状态都是必败状态时，该状态为必胜状态；

当某种状态的后继状态有一种是必胜状态时，该状态为必败状态。

所以先将0标记为必败，1-9标记为必胜（显然），从10-1000000遍历一遍，用f数组存必败或必胜，然后输出就可以了。在求f[i]的时候只会用到f[i-max/min],而max/min必然大于0，所以顺序遍历即可。

#include <cstdio>
using namespace std;

int q,n;
bool f[1000020];

inline int fmax(int x)
{
	int m=0;
	while (x) {if (x%10>m) m=x%10; x/=10;}
	return m;
}

inline int fmin(int x)
{
	int m=10;
	while (x) {if (x%10<m&&x%10) m=x%10; x/=10;}
	return m;
}

int main()
{
	//f[0]=false 不做处理（因为f默认为false）
	for (int i=1;i<10;i++) f[i]=true;
	for (int i=10;i<1000001;i++)
	{
		if (f[i-fmax(i)]&&f[i-fmin(i)])；//不做处理（因为f默认为false）
		else f[i]=true;
	}
	scanf ("%d",&q);
	for (int i=0;i<q;i++)
	{
		scanf ("%d",&n);
		if (f[n]) printf ("YES\n");
		else printf ("NO\n");
	}
	return 0;
}

然而还有更快的方法：

#include <cstdio>
using namespace std;

bool f[1000020];

inline int fmax(int x)
{
	int m=0;
	while (x) {if (x%10>m) m=x%10; x/=10;}
	return m;
}

inline int fmin(int x)
{
	int m=10;
	while (x) {if (x%10<m&&x%10) m=x%10; x/=10;}
	return m;
}

int main()
{
	freopen (".txt","w",stdout);
	for (int i=1;i<10;i++) f[i]=true;
	printf ("f[1000020]={0,1,1,1,1,1,1,1,1,1");
	for (int i=10;i<1000001;i++)
	{
		if (f[i-fmax(i)]&&f[i-fmin(i)]) f[i]=false;
		else f[i]=true; printf (",%d",f[i]);
	}
	printf ("};"); return 0;
}

配合

#include <cstdio>
using namespace std;

int g,n;
bool //将上一个程序运行后的文件内容粘贴在这里

int main()
{
	scanf ("%d",&g);
	for (int i=0;i<g;i++)
	{
		scanf ("%d",&n);
		if (f[n]) printf ("YES\n");
		else printf ("NO\n");
	}
	return 0;
}

只是洛谷不让交……