一维反Nim游戏

无心人

先罗列结果 2，3， 5，6，7，8先手胜，1，4先手负 (1, 1), (1, 2), (1, 3),先手胜 (2, 2) (3, 3)先手负 由几个先手负得到下面的几个先手胜 (2, 3), (2, 4), (1, 4),（3,4)，(3,5) [ 本帖最后由 无心人 于 2008-9-11 20:45 编辑 ]

shshsh_0510

如果20#没算错的话，Z1=4的所有奇异局势为： p4 o1p4,p2p4,p3p4, p1o4,o2o4,o3o4 p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4 p1o2o3p4,o1p2p3p4, ,p1p2p3o4,o1o2o3o4, Z1<=4的所有奇异局势为： p1,o2,o3,p4 o1o2,o1o3,o2o3,o2o4,o3o4,p2p4,p3p4, p1o4, o1p4 o1o2o3,p1p2p3, p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4 p1o2o3p4, o1p2p3p4, ,p1p2p3o4, o1o2o3o4 有点规律，但挺难描述 [ 本帖最后由 shshsh_0510 于 2008-9-11 17:34 编辑 ]

mathe

假设p4奇异,那么p2p4奇异肯定有错,应为对于1个2和1个4的情况,可以取掉2只余下4的.

shshsh_0510

check了一下，确实有bug ：）不过改完感觉更好了，去掉了看着很不爽的p2p4,p3p4 p4， o1p4, p1o4,o2o4,o3o4 p1o2p4,p1o3p4,p2p3p4,o1o2o4,o1o3o4 p1o2o3p4,o1p2p3p4, ,p1p2p3o4,o1o2o3o4,

shshsh_0510

太容易出错，需要编个程序验证一下

mathe

我现在觉得除了1和4以外，都是先手必胜。

mathe

定义一个表格: s[1]=1 s[2]=2 s[3]=3 s[4]=0 s[5]=1 s[6]=3 s[7]=4 s[8]=1 s[9]=6 s[10]=3 s[11]=2 s[12]=1 s[13]=6 s[14]=2 s[15]=4 s[16]=6 s[17]=7 s[18]=4 s[19]=3 s[20]=1 s[21]=7 s[22]=3 s[23]=8 s[24]=1 s[25]=6 s[26]=5 s[27]=4 s[28]=9 s[29]=6 s[30]=4 s[31]=3 s[32]=6 s[33]=1 s[34]=4 s[35]=5 s[36]=6 s[37]=10 s[38]=5 s[39]=2 s[40]=1 s[41]=10 s[42]=11 s[43]=4 s[44]=6 s[45]=11 s[46]=4 s[47]=3 s[48]=8 s[49]=1 s[50]=10 然后对于任意一个状态下，只要不是全部1或1个1和1个2的情况，对于其余情况，如果分成k堆，每堆分别有$x_1,x_2,...,x_k$个 那么对应状态数就是$s[x_1]"^"s[x_2]"^"..."^"s[x_k]$，只有那些状态数为0的状态才是先手负的。 上面的猜测还没有验证

mathe

而那几个特例是奇数个1状态数为0，偶数个1状态数为1，1*2+1*1状态数为1

mathe

晕，好像上面结论还是不行。因为两个4的情况不对。看来最大数据在4一下的都要枚举出来，可能5以后才能有比较好的规律，这样的话，最终结果还是很难求出来

无心人

俺重新描述下题目 有元素序列S，里面是正整数的从小到大排列 每个序列有状态胜和负 如果有序列s中元素k 1、当k <= 2，去掉元素k，得到的序列重新排列后得到序列s1 2、当k >= 2，用k - 1代替k，得到的序列重新排列后得到序列s1 3、当k >= 3，用k - 2代替k，得到的序列重新排列后得到序列s1 4、当k >= 3，把k分裂成两个元素k1, k2，且使得k = k1 + k2 + 1，得到的两个元素代替k进入序列，重新排列得到序列s1 5、当k >= 4，把k分裂成两个元素k1, k2，且使得k = k1 + k2 + 2，得到的两个元素代替k进入序列，重新排列得到序列s1 所有满足条件1，2，3的序列s1称为s的直接子序列，其集合称为s的直接子序列集合 定义，只有且仅有偶数个1的序列状态是胜，只有且仅有奇数个1的序列状态是负 则，如果序列的直接子序列有一个序列状态是负，则序列的状态是胜 如果序列的直接子序列集合中的所有序列状态均是胜，则序列状态是负 呵呵，这么写，清楚了么？ 而且似乎可以用来计算吧