LP3235 [HNOI2014]江南乐 [博弈]
Solution
Multi-SG 问题。
一个局面有多个子局面,一个子局面可以看做一个游戏包含多个子游戏。
则子局面的 SG 函数为子游戏 SG 函数异或和,而局面的 SG 函数为子局面的 mex。
考虑一个石堆 $i$ 可以拆成 $x-i\%x$ 个 $\left \lfloor \frac{i}{x} \right \rfloor$ 和 $i\%x$ 个 $\left \lfloor \frac{i}{x} \right \rfloor+1$ 石堆。
又发现石堆的最终呈现效果只和 $\left \lfloor \frac{i}{x} \right \rfloor$ 有关,因此考虑数论分块。
异或和跟奇偶性相关,考虑 $x-i\%x$ 和 $i\%x$ 的奇偶性。令 $i=kx+b$,则讨论 $(k+1)x-i$ 与 $i-kx$ 的奇偶性。又发现 $k$ 与 $i$ 皆为定值,所以直接枚举两种 $x$ 的奇偶性情况即可。
关于特判问题,我不是很懂题目的意思。因为压根没有说明相关限制条件。
Code
// Code by ajcxsu
// Problem: div stone
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int sg[N];
int ocr[N];
int cac(int k, int i, int x) {
int ret=0;
if((i-k*x)&1) ret^=sg[k+1];
if(((k+1)*x-i)&1) ret^=sg[k];
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int t, f;
cin>>t>>f;
if(f==1) f++;
bool a, b, c, d;
int k;
for(int i=f;i<N;i++) {
for(int l=1, r; l<=i; l=r+1) {
r=i/(i/l), k=i/l;
ocr[cac(k, i, l)]=i;
if(r-l) ocr[cac(k, i, l+1)]=i;
}
for(int j=0;j<N;j++) if(ocr[j]!=i) { sg[i]=j; break; }
}
int n, nsg, na;
while(t--) {
nsg=0, cin>>n;
for(int i=0;i<n;i++) cin>>na, nsg^=sg[na];
cout<<bool(nsg)<<' ';
}
cout<<endl;
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-3235.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆