icontofig | 发布于 2019-07-30 12:14:20 | 阅读量 273 | 莫队 博弈论 NIM博弈
发布于 2019-07-30 12:14:20 | 莫队 博弈论 NIM博弈
2019 Multi-University Training Contest 3 Game 经典NIM博弈SG函数 + 带修改莫队
题目大意先手选出区间L-R的连续的石子堆,后手可以交换第pos 和 pos+1堆石子,然后再从L-R选出区间l-r的石子两人进行取石子博弈。 问在L-R中有多少种后手取l-r的方案能够使得先手必胜。 题解这题是一个经典的NIM博弈。我们需要用SG函数来解决。 我们考虑前缀SG函数异或和,区间L-R内有多少选择l-r的方案使得先手必胜这一点我们可以转化为有都少方案使得先手必败(SG函数异或和为0) l-r的SG函数异或和为0,即前缀异或和ssg满足ssg[r] = ssg[l-1],问题转化为统计区间中有多少ssg相等的点对数。 然后我们使用区间点对总数减去区间中ssg相等的点对数就是当前询问的
继续阅读