题解 P3235 【[HNOI2014]江南乐】

· · 题解

毒瘤博弈论

目前luogu速度第一（666ms）

这题卡语文

我们需要忽略这句话：

也就是当每一堆石子的数量都严格小于F时，他就输掉

下面是正文

暴力很容易想到，直接枚举一个分成的堆数，直接套SG函数然后记忆化（将SG记忆化）即可

设这有i个石子的堆分成的堆的集合为S，SG_i = mex\{\oplus SG_{j\in S}\}（那个东西是异或和）

我们发现集合S中仅包含两个数，又因为任何一个数XOR它自己都为0，所以我们只需要判断是奇数还是偶数

int tmp=0;
int t1=x%i;
int t2=i-t1;
if(t1&1)tmp^=dfs(x/i+1);
if(t2&1)tmp^=dfs(x/i);

现在的瓶颈在于求mex

mex？果断珂朵莉大法好（因为只有split且每次至少分为两堆，递归层数上界为nlog_n，所以珂朵莉树的时间和空间复杂度都是对的）

然后我们还发现一个问题，枚举分成的堆数要枚举到多少，如果你勤快可以除法分块（其实是我不会），或者我们只需要枚举到\lceil x\div f\rceil + 1

然后这题就做完了（卡语文卡了一个多小时）

下面是代码

LOJ的格式化代码有点神仙

#include <bits/stdc++.h>
using namespace std;
inline int gi() {
    register int x, op = 1, c;
    while (c = getchar(), c < '0' || c > '9')
        if (c == '-')
            op = -op;
    x = c ^ 48;
    while (c = getchar(), c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48);
    return x * op;
}
void split(set<pair<int, int> >& s, int x) {
    set<pair<int, int> >::iterator it;
    it = s.lower_bound(make_pair(x + 1, -1));
    if (it == s.begin())
        return;
    --it;
    if (it == s.end())
        return;
    pair<int, int> p = *it;
    if (x > p.second || x < p.first)
        return;
    s.erase(it);
    if (x < p.second)
        s.insert(make_pair(x + 1, p.second));
    if (x > p.first)
        s.insert(make_pair(p.first, x - 1));
}
int T, m;
int sg[100001] = { 0 };
bool vis[100001] = { 0 };
int dfs(int x) {
    if (vis[x] || x < m)
        return sg[x];
    vis[x] = 1;
    int lim = ceil(x * 1.0 / m) + 1;
    set<pair<int, int> > s;
    s.insert(make_pair(0, lim + 1));
    for (int i = 2; i <= lim; i++) {
        int tmp = 0;
        int t1 = x % i;
        int t2 = i - t1;
        if (t1 & 1)
            tmp ^= dfs(x / i + 1);
        if (t2 & 1)
            tmp ^= dfs(x / i);
        split(s, tmp);
    }
    return sg[x] = (*s.lower_bound(make_pair(0, 0))).first;
}
int main() {
    vis[1] = 1;
    T = gi(), m = gi();
    while (T--) {
        int n = gi(), ans = 0;
        while (n--) ans ^= dfs(gi());
        printf("%d ", !!ans);
    }
    return 0;
}