世界未末日 题解

VinstaG173 · 2021-04-25 18:33:35 · 题解

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

前置知识：k-SG。

Subtasks

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;
}