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相等的点对数就是当前询问的
继续阅读
icontofig | 发布于 2019-05-19 21:03:32 | 阅读量 362 | 莫队 树状数组
发布于 2019-05-19 21:03:32 | 莫队 树状数组
XTCPC2019 湘潭邀请赛 Problem C Chika and Friendly Pairs (莫队+树状数组)
 题意:给定n个数,m条询问,每个询问中包含l、r查询这个区间[l,r]中有多少个数对满足两个数的绝对值之差小于等于K 题解:上来一看区间查询,第一反应一般都是线段树/树状数组等数据结构。 但是看一下这道题要求什么,求区间内满足条件的数对个数。 我好像没有见过能维护数对个数的树状数组或者线段树什么的。 对于数对而言,一般都应该先枚举其中一个数,剩下的才能去判断吧。 如果两个数i,j满足绝对值之差小于等于K,那么肯定能有这样一个关系式:i−k<=j<=i+k 这样的话,对于某个区间内的所有数,能跟当前枚举出来的数x组成满足题意的数对的,一定在[x-k,x+k]这个区间里,我
继续阅读