[BZOJ1188][HNOI2007]分裂游戏（博弈论）
2024-08-28 17:29:33
题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1188
分析：
设SG[i]表示一个石子在位置i上的SG值
这个很容易暴力求，因为i的后继状态肯定是所有的(j,k)，其后继状态的SG值就是SG[j]^SG[k]
然后整个游戏的SG值就是SG[1]^SG[1]^SG[1]^...^SG[2]^SG[2]^......也就是说一个堆有多少个石子就要异或多少下。
因为异或的特殊性质，所以如果一个堆的石子个数是偶数，那么就是偶数个同样的数相异或，结果为0，不考虑。如果一个堆的石子个数是奇数，可以看作偶数+1，所以只要异或1次
至于题目还要求第一步的方法和方案数，可以枚举解决。
设整个游戏的SG值为ans
那么我们枚举(i,j,k)作为第一步，那么什么样的(i,j,k)可以作为第一步呢？最直接的想法对于每个i,j,k，把a[i]-=1,a[j]+=1,a[k]+=1，对整个局面重新异或计算下新的全局SG值。当然其实没必要这么做，这样很慢的。再次根据异或的特殊性质，可以直接新的SG=ans^SG[i]^SG[j]^SG[K]。为什么呢？因为我在原来的基础上，再次异或一个SG[i]就相当于减去一个i位置上的石子，异或一个SG[J]就相当于加上一个j位置上的石子，异或一个SG[k]就相当于加上一个k位置上的石子。
于是就解决了。
最新文章
- Https方式使用Git@OSC设置密码的方式
- 如何使用github搭建个人博客
- Finalize()、Dispose()、SafeHandle、GC
- 【Android】Android Camera实时数据采集及通过MediaCodec硬编码编码数据的流程
- Flex弹性布局在移动设备上的应用
- Ansible之playbook
- 信号量及PV原语
- Java基础知识强化50：运行javac 报告javac不是内部或外部命令（已解决）
- 常见的 http 状态码
- Intellij idea生成Hibernate实体类
- EclipseEE导入项目出现的那些问题
- session与cookie的区别与联系
- iOS数据解析UI_14
- sql 查询 某字段 重复次数 最多的记录
- recovery 升级'@/cache/recovery/block.map' failed错误问题
- android:ListView 的简单用法
- MySQL 单条记录长度最大65535
- Python：高效计算大文件中的最长行的长度
- java读取txt文件的2中方法---并将内容（每一行以固定的字符分割切成2段）存到map中去
- springjdbc使用c3p0连接池报错 java.lang.NoClassDefFoundError: com/mchange/v2/ser/Indirector