M_sea

洛谷3235 [HNOI2014]江南乐
LuoguBZOJ分析0首先发现这是个$\mathrm{Multi-SG}$游戏,然后发现可以用 $SG$ 函数来...
扫描右侧二维码阅读全文
19
2019/02

洛谷3235 [HNOI2014]江南乐

Luogu

BZOJ

分析

0

首先发现这是个$\mathrm{Multi-SG}$游戏,然后发现可以用 $SG$ 函数来做。

显然的,对于任意的$x<F$,$SG(x)=0$。

1

先考虑怎么暴力求 $SG(x)$ 。

大力枚举分成的堆数。如果将 $x$ 分成了$i$ 堆,那么这 $i$ 堆中有 $x\% i$ 堆$\left\lceil\frac{x}{i}\right\rceil$,有 $i-x\%i$ 堆 $\left\lfloor\frac{x}{i}\right\rfloor$ 。

于是对于每个$i$,算出它的 $SG$ 值(为所有分出来的堆数的 $SG$ 值的异或和),再取个$\mathrm{mex}$就是 $SG(x)$ 了。

2

发现求 $SG$ 函数的过程中有重复计算,于是可以记忆化一下。

3

因为要计算的是异或和,而$a\ \mathrm{xor}\ a=0$,于是只要根据 $x\%i$ 和 $i-x\%i$ 的奇偶性讨论一下就行了。

到这里求 $SG$ 函数的代码大概长这样:

inline int SG(int x) {
    if (x<F) return 0;
    if (sg[x]!=-1) return sg[x];
    for (re int i=2;i<=x;++i) {
        int a=x%i,b=x/i+1,c=i-x%i,d=x/i,s=0;
        if (a&1) s^=SG(b);
        if (c&1) s^=SG(d);
        vis[s]=x;
    }
    for (re int i=0;;++i) //求mex
        if (vis[i]!=x) return sg[x]=i;
}

于是就愉悦地获得了 $70$ 分。

4

发现 $\left\lfloor\frac{x}{i}\right\rfloor$ 最多只有 $2\sqrt{n}$ 个取值,于是可以数论分块来枚举 $\left\lfloor\frac{x}{i}\right\rfloor$ 。

然后因为 $SG(\left\lceil\frac{x}{i}\right\rceil)$ 和 $SG(\left\lfloor\frac{x}{i}\right\rfloor)$ 是否产生贡献只和 $x\%i$ 和 $i-x\%i$ 的奇偶性有关,于是只要算 $i$ 与 $i+1$ 的情况了,因为分为 $\geq i+2$ 堆时的 $SG$ 值一定和$SG(i)$ 与 $SG(i+1)$ 中的一个相等。

现在求 $SG$ 函数的代码是这个样子的了:

inline int SG(int x) {
    if (x<F) return 0;
    if (sg[x]!=-1) return sg[x];
    for (re int l=2,r;l<=x;l=r+1) {
        r=x/(x/l);
        for (re int j=l;j<=min(l+1,r);++j) {
            int a=x%j,b=x/j+1,c=j-x%j,d=x/j,s=0;
            if (a&1) s^=SG(b);
            if (c&1) s^=SG(d);
            vis[s]=x;
        }
    }
    for (re int i=0;;++i) //求mex
        if (vis[i]!=x) return sg[x]=i;
}

于是就愉悦地$\color{LimeGreen}{\text{AC}}$了本题。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int sg[100010],vis[100010];
int T,F;

inline int SG(int x) {
    if (x<F) return 0;
    if (sg[x]!=-1) return sg[x];
    for (re int l=2,r;l<=x;l=r+1) {
        r=x/(x/l);
        for (re int j=l;j<=min(l+1,r);++j) {
            int a=x%j,b=x/j+1,c=j-x%j,d=x/j,s=0;
            if (a&1) s^=SG(b);
            if (c&1) s^=SG(d);
            vis[s]=x;
        }
    }
    for (re int i=0;;++i)
        if (vis[i]!=x) return sg[x]=i;
}

int main() {
    memset(sg,-1,sizeof(sg));
    T=read(),F=read();
    while (T--) {
        int n=read(),ans=0;
        for (re int i=1;i<=n;++i) ans^=SG(read());
        printf("%d ",(bool)ans);
    }
    putchar('\n');
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 53 PM

5 条评论

  1. Itst

    M-sea做题怎么这么快啊QAQ

    1. M_sea
      @Itst

      哪里快了qwq

      您比我快多了qwq

      1. smy
        @M_sea

        怎么这么假啊qwq

  2. smy

    %%%

    1. M_sea
      @smy

      %%%%%

发表评论