自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:34:50，当前版本为作者最后更新于2021-04-25 18:33:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

初二时搞的题，当时玩了好久，换了一堆版本（

前置知识：k-SG。

Subtasks

Subtask No.	$n \le$	$S \le$	分值
$1$	$300$	$300$	$7$
$2$		$3 \times 10^7$	$8$
$3$		$3 \times 10^{10}$	$16$
$4$	$3 \times 10^6$	$3$	$3$
$5$		$3 \times 10^3$
$6$		$3 \times 10^7$	$16$
$7$		$3 \times 10^{10}$	$47$

Solutions

我不知道有没有其他的做法……反正我会的都在这了，还有一个有点毒瘤于是放了加强版……

为了简洁，我在部分分对应代码中均省去具体处理 k-SG 的部分，在正解对应代码（std）里会有。处理 k-SG 可以在 $O(n\log{S})$ 时间内完成，不算入具体部分分的时间复杂度分析中。

Sol. $\rm{I}$

Subtask $\# 4$，$3$ pts

发现 $\le 3$ 不可操作。直接输出 NO。

Code:

#include<cstdio>
int main()
{
	puts("NO");
	return 0;
}

Sol. $\rm{II}$

Subtask $\# 4,1$，$10$ pts

直接依题意暴力计算 $\operatorname{SG}$ 函数，时间 $O(nS^2)$。

Code:

#include<cstdio>
#define rg register
int n,k,S,s;
int vs[307];
int SG[307];
int sg[3000007];
int main()
{
	scanf(" %d %d %d",&n,&k,&S);
	for(rg int i=0;i<n;++i)
	{
		scanf(" %d",&s);
		SG[0]=0;
		for(rg int i=1;i<=s;++i)
		{
			for(rg int j=i;j*j/4>=i;--j)vs[SG[i-j]]=1;
			while(vs[SG[i]])++SG[i];
			for(rg int j=i;j*j/4>=i;--j)vs[SG[i-j]]=0;
		}
		sg[i]=SG[s];
	}
}

Sol. $\rm{III}$

Subtask $\# 4,1,5$，$13$ pts

把询问内计算换成递推，时间 $O(S^2+n)$。

Code:

#include<cstdio>
#define rg register
int n,k,S,s;
int vs[3007];
int SG[3007];
int sg[3000007];
int main()
{
	scanf(" %d %d %d",&n,&k,&S);
	SG[0]=0;
	for(rg int i=1;i<=S;++i)
	{
		for(rg int j=i;j*j/4>=i;--j)vs[SG[i-j]]=1;
		while(vs[SG[i]])++SG[i];
		for(rg int j=i;j*j/4>=i;--j)vs[SG[i-j]]=0;
	}
	for(rg int i=0;i<n;++i)
	{
		scanf(" %d",&s);
		sg[i]=SG[s];
	}
}

Sol. $\rm{IV}$

Subtask $\# 4,1,5,2,3$，$37$ pts

发现一个性质：$x$ 的后继状态集合为 $[0,x-2\sqrt{x}]\cap\mathbb{Z}$。

由于 $x-2\sqrt{x}=(\sqrt{x}-1)^2-1$ 递增，因此后继状态集合不减，所以 $\operatorname{SG}$ 函数值不减。因此 $\operatorname{SG}(x)=\operatorname{SG}(\lfloor x-2\sqrt{x} \rfloor)+1$。直接计算，时间 $O(n\sqrt{S})$。

Code:

#include<cmath>
#include<cstdio>
#define rg register
#define ll long long
ll S,s;
int n,k;
int sg[3000007];
int main()
{
	scanf(" %d %d %lld",&n,&k,&S);
	for(rg int i=0;i<n;++i)
	{
		scanf(" %lld",&s);
		while(s>3)s=(ll)(s-sqrt(s)*2),++sg[i];
	}
}

Sol. $\rm{V}$

Subtask $\# 4,1,5,2,6$，$37$ pts

把询问内计算换成递推，时间 $O(S+n)$。

Code:

#include<cmath>
#include<cstdio>
#define rg register
int n,k,S,s;
int sg[3000007];
int SG[30000007];
int main()
{
	scanf(" %d %d %d",&n,&k,&S);
	for(rg int i=4;i<=S;++i)SG[i]=SG[int(i-sqrt(i)*2)]+1;
	for(rg int i=0;i<n;++i)
	{
		scanf(" %d",&s);
		sg[i]=SG[s];
	}
}

Sol. $\rm{VI}$

Subtask $\# 4,1,5,2,6,3$，$53$ pts

结合 Sol. $\rm{IV \& V}$ 即可。

Code:

#include<cmath>
#include<cstdio>
#define rg register
#define ll long long
ll S,s;
int n,k;
int sg[3000007];
int SG[30000007];
int main()
{
	scanf(" %d %d %lld",&n,&k,&S);
	if(n<=300)
	{
		for(rg int i=0;i<n;++i)
		{
			scanf(" %lld",&s);
			while(s>3)s=(ll)(s-sqrt(s)*2),++sg[i];
		}
	}
	else
	{
		for(rg int i=4;i<=S;++i)SG[i]=SG[int(i-sqrt(i)*2)]+1;
		for(rg int i=0;i<n;++i)
		{
			scanf(" %d",&s);
			sg[i]=SG[s];
		}
	}
}

Sol. $\rm{VII}$

讲正解。感觉前面的分应该会 k-SG 都能拿到吧，算是送了

首先我们要在 $\rm{IV}$ 里的结论基础上继续找性质。

想到 $\operatorname{SG}$ 函数值不减，所以尝试对 $v$ 找满足 $\operatorname{SG}(x)=v$ 的最小 $x$。

我们发现设 $\operatorname{SG}(x)=v$ 的最小 $x$ 为 $x_v$，则 $\lfloor x_v-2\sqrt{x_v}\rfloor=x_{v-1}$。直接递推就行了。

计算出来后直接二分找出最大的 $x \le s_i$ 就行了。时间 $O(\sqrt{S}+n\log{S})$。

Code:

#include<cmath>
#include<cstdio>
#define rg register
#define ll long long
inline char gc()
{
	static char buf[1048576],*pn=buf,*pe=buf;
	return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,1048576,stdin),pn==pe)?EOF:*pn++;
}
inline int read()
{
	int x=0;
	char c=gc();
	while(c<'0'||c>'9')c=gc();
	while(c>='0'&&c<='9')x=x*10+(c^48),c=gc();
	return x;
}
inline ll _read()
{
	ll x=0;
	char c=gc();
	while(c<'0'||c>'9')c=gc();
	while(c>='0'&&c<='9')x=x*10+(c^48),c=gc();
	return x;
}
ll s,S;
int n,k;
int ans[19];
int cnt,bt,sg;
ll dsg[173273];
inline int SG(ll x)
{
	int l=0,r=cnt,m;
	while(l<r)
	{
		m=r-((r-l)>>1);
		if(dsg[m]==x)l=r=m;
		else (dsg[m]<x)?(l=m):(r=m-1);
	}
	return l;
}
int main()
{
	n=read(),k=read()+1,S=_read(),dsg[0]=0;
	for(rg int i=1;;++i)
	{
		double v=sqrt(dsg[i-1]+1)+1;
		dsg[i]=(ll)(v*v);
		if(dsg[i]-2*sqrt(dsg[i])<dsg[i-1])++dsg[i];
		if(dsg[i]>=S){cnt=i;break;}
	}
	for(rg int i=0;i<n;++i)
	{
		s=_read();
		sg=SG(s),bt=0;
		while(sg)
		{
			(sg&1)&&(++ans[bt],\
			(ans[bt]==k)&&(ans[bt]=0));
			sg>>=1,++bt;
		}
	}
	int flag=0;
	for(rg int i=0;i<18;++i)
	{
		if(ans[i])
		{
			flag=1;break;
		}
	}
	puts((flag)?"YES":"NO");
	return 0;
}