[HNOI2014]江南乐
题目地址:https://www.luogu.com.cn/problem/P3235
题目意思是这样的:
给定\(n\)堆石子,每次操作选择一堆石子数目\(x\)(\(x>=f\)),把它分成\(m\)堆(\(2<=m<=x\)),分出来的每一堆中石子数目最大值和最小值相差不超过\(1\)(也就是均分的意思),问你先手是否必胜。
其实这个问题可以转化成\(n\)个子问题,每一个子问题都只对一堆石子进行操作。
然后就可以转化成\(SG\)函数的问题了。
SG定理:\(SG=SG(a_1) \bigoplus SG(a_2) \bigoplus SG(a_3)... \bigoplus SG(a_n)\),及总问题的SG值为分问题的SG值的异或和,本文就不进行证明了。
想法1
考虑到\(x\)的\(SG\)值只跟\(f\)有关,题目在最开始已经把\(f\)告诉我们了,我们可以考虑预处理。
我们用枚举每个\(x\)分成的石子堆数\(m\)(\(2<=m<=x\)),将这\(m\)堆石子的\(SG\)异或起来,然后对于所有的\(m\)的异或和取\(mex\)。
这显然是\(O(x^2)\)的做法,会直接TLE。
所以我们不能预处理,我们就想到了记忆化搜索。
想法2
受到想法1的启发,我们可以枚举\(m\),然后异或和取\(mex\),这不过这一次我们不预处理出\(SG\)值,而是边暴力递归边存\(SG\)值,遇到已经算过的\(SG\)值直接返回即可。
那么如何计算异或和呢?
我们用到异或的一个性质\(x \bigoplus x=0\)
看到下面这张图
我们发现把\(x\)分成\(m\)份的异或和只有可能是\(0,SG(x/m),SG(x/m+1),SG(x/m) \bigoplus SG(x/m+1)\)
那么接下来该如何计算\(mex\)值呢
我们每一次算完异或和以后,用一个数字打上一个特殊的标记,然后最后统计\(mex\)值的时候找到第一个没有这种标记的值即可
然后我们就可以拿到了70分(TLE30)
#include
using namespace std;
int T,F,sg[200000];
int n,a,po[200000],q=0;
int SG(int x,int pos)
{
if(sg[x]>-1)return q--,sg[x];//已经算出来过
if(x
想法3
我们可以观察到其实同一个\(x\)分成\(m\)份时会出现\(t\)和\(t+1\)两个值,我们可以把分出来的\(t\)和\(t+1\)都相同的\(m\)一起算,此时答案只有可能是\(SG(t),SG(t) \bigoplus SG(t+1)\)两种,而且存在一定的奇偶关系
我们可以发现,同一个t和t+1,m0与m0+2的答案是一样的,因此我们可以枚举t,然后算出对应的前两个m即可
可以看下面这个图,尤其是1和2的蓝色部分,规律非常明显
AC Code
#include
using namespace std;
int T,F,sg[200000];
int n,a,po[200000],q=0;
int SG(int x,int pos)
{
if(sg[x]>-1)return q--,sg[x];
if(x