牛客237787563号
牛客237787563号
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
牛客237787563号的博客
全部文章
/ 未归档
(共6篇)
模拟86 题解
A. 异或 位运算所以按位考虑。 数位$dp$统计每一位$0/1$的取值个数,随便乘一乘就出结果了。 B. 取石子 $O(n^4)$的$dp$是显然的。 可以发现$dp$中必败的状态是很少的。 所以直接打表 所以可以用必败的状态刷表进行$dp$,复杂度是对的。 ...
数位dp
博弈论
dp
位运算
2019-10-25
0
431
模拟106 题解
A. 合并集合 显然的区间dp。 断环成链,预处理出每个连续区间集合的元素个数。 然后直接dp就完了。 B. climb 想了一些简单的贪心,然后都伪了。 所以考虑如何暴力$O(n^2)$来做这个题。 枚举最终用来跳最后一步的药丸,显然前面的药丸可以按$a_i-b_i...
并查集
博弈论
区间dp
dp
拓展域
分治
线段树
2019-11-09
0
490
省选模拟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
noi前第十五场 题解
##A. zsy家今天的饭 对于 \(\binom{m}{k}\) 种方案,答案是跨过的边权*2-直径。 可以对两部分分别计算贡献。 对于前者,可以考虑计算每条边的贡献。 若将餐厅点集划分为 \(a,b\) 两部分,那么乘上的系数就是 \(\binom{m}{k}-\binom{a}{k}-\bi...
长链剖分
博弈论
dp
2020-07-29
0
490