牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共29篇）

省选模拟46 题解

A. 俄罗斯方块一道很神奇的 bitset 题。考虑维护每个格子最上面属于哪个块，这个东西可以用一个 set 来维护每个连续段，操作方法类似珂朵莉树。对于每次操作，直接用 set 遍历每个有交的连续段，询问并取 $\max$，以得到当前的高度，然后进行覆盖操作。所以现在的问题是，有一...

容斥多项式 set bitset 提交答案

2020-03-16

0 851

组合计数题解乱写

3.组合计数上 1.ARC102E 把当前限制对应的每个二元组提出来。枚举有多少个二元组中的数字出现了，然后问题是每个组中二选一。出现的数字可以出现 $>0$ 次，不在任何一个二元组中的数字可以出现 $\geq 0$ 次。统一一下就可以直接插板法了。 2.小Z的礼物通过...

二项式反演轮廓线容斥组合计数

2020-03-17

0 747

省选模拟56 题解

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

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

2020-03-28

0 399

省选模拟53 题解

A. 数（number）对于 $n$ 为偶数，容易发现确定一半就行了，答案为 $10^{\frac{n}{2}}$。对于 $n$ 为奇数，列式子可以发现形如 $\sum 2x_i = \sum 2y_i \ \ +y_{mid}$。一步很神的操作是，把 $y_i$ 转化为 $9-y_i$...

容斥二项式反演二分答案贪心线段树

2020-03-25

0 396

省选模拟61 题解

A. GTM 考虑一个点 $(x,v)$ ，能够碰到的点 $(x',v')$。有 $(x',v')$ 满足 $x'<x,v'>v$ 或者 $x'>x,v'<v$。然后有这样一个结论，我们将所有的点按照 $v$ 排序，然后在每个点能影响到的是一个连续区间。区间的左...

结论题树状数组容斥线段树

2020-04-03

0 800

杂题

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。然后只要考虑每个...

dp 期望容斥字符串组合计数

2020-04-07

0 457

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381

省选模拟101 题解

石子游戏问题可以简单转化为最少能取出多少个数，使得异或和为 \(k\)。显然答案是小于 \(log(A_i)\) 的，因为线性基已经可以拼出所有数了。所以可以考虑枚举这个答案，然后就是 \(dp_{i,j}\) 表示用 \(i\) 个数能否拼出 \(j\)。转移可以用 \(FWT\) 优化，...

状压容斥 fwt dp 筛法

2020-05-20

0 367

noi前第十八场题解

##A. 林海的密码难点主要就是如何构造加法操作。一个点数 $2 \log n$，边数 $5 \log n$ 的做法是这样的。像这样构造一个双向的环，显然一个内向生成树为断掉红边的后缀、黑边的前缀。发现这样每次只能使贡献 \(*2\) 或者不变，所以问题就是用若干个连续的 $2$ 的次幂...

构造题分治二项式反演多项式容斥

2020-08-02

0 601