SG函数 hdu 1404 Digital Deletions
  VrZI4Uwu8BR1 2023年11月02日 61 0



sg函数,能到达0的点,赋值为1.

#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<vector>
#include<map>
#include<string>
using namespace std;
#define ll long long

int sg[1000010];
char ch[6];

int G(int x)
{
	if(sg[x]!=-1) return sg[x];
	int i=1,k,j,t,flag;
	while(x/i)
	{
		flag=(x/(i*10))?0:1;
		t=x/i%10;
		if(t==0)
		{
			if(sg[x/(i*10)]==0)
				return sg[x]=1;
			i*=10;
			continue;
		}
		k=x-(t-flag)*i;
		for(j=flag;j<t;j++)
		{
			if(sg[k]==0)
				return sg[x]=1;
			k+=i;
		}
		i*=10;
	}
	return sg[x]=0;
}
int main()
{
	memset(sg,-1,sizeof(sg));
	int i,j,k;
	sg[0]=1;
	for(i=1;i<1000000;i++)
		G(i);
	while(cin>>ch)
	{
		if(ch[0]=='0')
		{
			printf("Yes\n");
			continue;
		}
		int len=strlen(ch);
		int sum=0;
		for(i=0;i<len;i++)
		{
			sum=sum*10+ch[i]-'0';
		}
		if(G(sum))
			printf("Yes\n");
		else printf("No\n");
	}
}




【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
VrZI4Uwu8BR1