牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共241篇）

noi前第十场题解

A. 集合划分可以直接写出一个简单的 \(dp\)，然后发现这个 \(dp\) 的信息只需要存 \(A\) 集合选的个数和末尾选的哪个集合。不妨写成一个多项式，那么我们只关心边界的情况。所以写一个分治 \(FFT\) 即可。 B. ACT4！⽆限回转！考虑对于每条边，枚举所有能到达...

计算几何分治多项式 dp 辛普森积分

2020-07-22

0 405

二次剩余

二次剩余 PS:以下内容大概都是抄的。大概是解这样一个方程： \[x^2 \equiv n \pmod p \] 这里讨论 \(p\) 为奇素数。称非 \(0\) 数 \(n\) 是二次剩余当 \(n\) 存在上述方程的解，反之成为非二次剩余。二次剩余的数量为 \(\fr...

数学

2020-07-22

0 486

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379

数据结构乱写

loj6515 贪玩蓝月容易发现本题中要求的信息不支持快速合并，不支持快速删除，但是支持快速插入。所以一个简单的离线做法就是线段树分治。只要按照时间建线段树，把每个操作插入到对应节点上。最后 \(dfs\) 一遍线段树顺便插入，在叶子节点输出答案即可。然而这个信息是支持快速合并两个信息的。...

dp 单调队列分块启发式合并线段树 lct

2020-07-13

0 448

字符串乱写

loj6158 考虑在一个位置放上加号，\(S=A+B\)。若末尾存在 \(0\) ，一定是说 \(A\) 的最后一个数字与 \(B\) 的最后一个数字相加为 \(10\)。（特别的，需要特判二者末尾均为 \(0\) 这个情况）对于进位的问题，其实就是要求 \(A\) 前面的数字与 \(B\) ...

字符串 AC自动机 ST表分块后缀自动机线段树

2020-07-06

0 379

奇怪的基础容斥数学课件

子集反演一般有一个很套路的方法。比如现在有一个全集条件集合 \(U\)。现在要求恰好 \(S\) 集合满足，\(U-S\) 集合不满足的方案数，设其为 \(f_S\)，然而这个并不能直接算出。有一个比较好算的东西是，钦定 \(T\) 集合满足，不管 \(U-T\) 集合是否满足的方案数，设其...

2020-06-22

0 400

省选模拟104 题解

A. 签到题把每个点向它右侧比他大的第一个点之间连边，如果没有那么向 \(root\) 连边。那么可以构成一棵树。特判一些情况之后，可以认为问题就是： 1.给某节点和它的所有儿子节点权值加上一个值。 2.询问一条路径的权值和。首先考虑如果只询问单点的维护方法，其实就是打一个标记表...

线段树网络流树链剖分

2020-05-23

0 362

省选模拟103 题解

2020-05-23

0 360

省选模拟102 题解

A. island 对于正负不同的情况，\(O(n)\) 枚举左侧的位置然后计算。对于正负性相同的情况，把笛卡尔树建出来，然后每次考虑跨过最小值的贡献。分几种情况：左右均不超过最小值，左右仅有一个超过最小值，左右都超过最小值。然后顺便统计上其中一个端点为划分点的贡献。然后疯狂的写式子拆式子就没...

圆方树贪心单调栈

2020-05-21

0 388

省选模拟101 题解

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

状压容斥 fwt dp 筛法

2020-05-20

0 367