牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共30篇）

省选模拟28 题解

A. 战略游戏容易发现完全覆盖的边是连续的。考虑暴力做法，枚举两个点表示完全覆盖的路径，统计答案是两个点相对于父边的权值相乘。可以发现这个权值可以表示为一个简单生成函数的形式，去掉一条边的贡献，可以表示为直接除掉一个简单的多项式 $(k*x+1)$ 。但是不管怎么做复杂度都是 $O(...

dp 差分多项式贪心

2020-02-22

0 856

省选模拟35 题解

A. two 考虑现在要通过蓝边删掉红边。其实等价于要找出有哪些红边，满足恰好只有一个端点在蓝边的儿子方向子树中。考虑对蓝树跑出一个 $dfs$ 序来，那么问题转化为恰好一个端点在给定区间中。这像是一个二维偏序问题。考虑以线段树下标为其中的第一维，第二维进行排序处理。然后用一个 $...

单调指针点分治多项式二分图网络流线段树

2020-03-02

0 334

省选模拟36 题解

A. Alchemy 考虑递归挪动这个塔的过程。然后发现有一些递归是没有必要的。通过初始状态可以判断递归的前半部分或后半部分是没有必要的。直接统计不递归的部分的贡献，然后递归另一部分就好了。这样的复杂度应该可以做到线性。 B. Algebra 要统计这个答案无非两个办法。...

多项式

2020-03-03

0 396

省选模拟45 题解

A. matrix 当然考虑左端点为 $l$的所有矩形的贡献。通过一个 trie，对 trie 上每个节点开一个 set，来找到每个串 $s$ 存在的位置。那么可以把当前答案的形式化成 $ans=\sum \limits_{s} val_s$ ，其中 $val_s$ 表示这个串出现的区间数...

多项式 trie树 set dp 启发式合并扫描线线段树

2020-03-14

0 467

省选模拟46 题解

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

容斥多项式 set bitset 提交答案

2020-03-16

0 851

省选模拟62 题解

A. Fable 虽然没打 noi online，但是大概看了一眼题。其中 T2 就用到了一个结论是：设 $p_{i,k}$ 表示 $i$ 次冒泡排序之后，第 $k$ 个点与之前的点形成的逆序对个数。则有每次冒泡排序之后，$p_{i+1,k}=\max{p_{i,k+1},0}$。 ...

结论题高斯消元多项式 set 矩阵平衡树启发式合并树状数组线性代数

2020-04-04

0 415

省选模拟69 题解

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

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

2020-04-13

0 381

省选模拟73 题解

A. 决战因为把暴力放过去了，所以这题就成水题了。其实正解的做法与那道求匹配方案权值和的题在链上的情况很类似。大概就是说整一个分治出来，然后 $dp_{l,r}$ 处存放一个多项式。其中 $l,r$ 分别表示左右两个端点的状态，$x^k$ 项系数表示放置了 $k$ 个人的方案数。 ...

莫比乌斯反演分数规划二分答案多项式数学网络流

2020-04-17

0 383

省选模拟75 题解

A. 比特币考虑把第 $k$ 位为 $1$ 的问题放在模 $2^{k+1}$ 意义下考虑，这样问题就简单了。因为若干个循环的贡献被强制放在了同一段上考虑。然后随便弄个数据结构维护一下即可。 B. 测试类似约数个数和一题，可以用类似的构造方法来展开 $d(i*j*k)$ 这个函...

数学莫比乌斯反演多项式 dp 斯特林数

2020-04-20

0 403

省选模拟80 题解

A. 数字如果枚举 $x\ and \ y$ 的取值，可以进行一个简单的dp。 $dp_{i,0/1,0/1,0/1,0/1}$ 表示从高到低到第 i 位，最高的几位分别是否与 $lx,rx,ly,ry$ 相同，然后这个 dp 数组的取值也只有0/1。所以可以 dp 套 dp。在考虑过...

分块多项式 dp套dp dp 根号分治矩阵数位dp

2020-04-25

0 408