牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共3篇）

省选模拟56 题解

A. 取石子游戏容易发现这个问题的 $sg$ 值就是每堆的石子个数的异或和。问题是后手能赢，也就是求删除 $d$ 的倍数个石子，使得剩余石子的异或和恰好为 $0$ 的方案数。然后发现直接 $dp$ 复杂度就是 $O(n*d*\max(a_i))$ 的。发现题面中给出了一个很特殊的限制...

模拟博弈论 SG函数 dp 容斥扫描线线段树

2020-03-28

0 399

省选模拟55 题解

A. 调兵遣将对于一个确定的右端点，只有 $log$ 种 $\gcd$ 不同的左端点。可以把这个东西写成 $(a,b,R)$ 的形式。在集合中不便于计算，可以考虑转化为总方案数减不在集合中的方案数。可以考虑设 $f_x$ 表示最后一个区间的右端点 $\leq x$ 的方案数，然后对上...

线段树扫描线博弈论 dp SG函数

2020-03-27

0 442

博弈论题解乱写

1.对于一个转移方程 $dp_{i,j}= not (dp_{i-1,j} \ and \ dp_{i,j-1})$。可以发现除了前两行两列，其他每个对角线的取值是相同的。所以只要做前三行三列的 dp 即可得到整个 dp 数组。然后这个东西的初始值不一定要整齐，只要拓展过来两三行都可以解...

线段树博弈论 SG函数

2020-03-27

0 853