牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

省选模拟100 题解

A. 小B的棋盘这种方案不好枚举的题的一个解决方案就是考虑怎样的方案是可能合法的。如果 \(k \geq n\) 那么一定无解，否则可以找到至少一组点的中点来表示最终的答案。容易发现取 \(k+1\) 个点至少存在一个能匹配到的，所以复杂度可以做到 \(O(n^2 k)\)。如果判断一下每个...

最小生成树 lct dp

2020-05-19

0 409

省选模拟96 题解

A. 多边形因为本题保证了 \(n\) 不为偶数，所以 \(n\) 没有 \(\frac{n}{2}\) 这个循环节。然后考虑 \(\frac{n}{3}\) 这个循环节，如果能形成锐角一定有 \(m=3\)。如果存在更小的循环节，那么一定不存在锐角了。所以尽量特殊处理一下 \(m=3\) ...

多项式 trie树

2020-05-14

0 372

省选模拟93 题解

A. A 肯定是用子序列自动机。然后暴力就是预处理出 DAG 上的路径数然后强行跑。优化的方法类似重链剖分，设 \(f_i\) 表示节点 \(i\) 之后的路径数。 \(f_i\) 等于每个转移边的加和。考虑求出每个节点的重转移。当 \(f_i<inf\)，重转移为每个转移中 \(f\) ...

倍增构造题矩阵期望线性代数

2020-05-11

0 399

杂题题解又乱写

1.AppleTrees (SRM489) 考虑对于每一种排列，求出顺次摆放最少的位置。然后把多余的位置插入在\(n+1\)个空位中即可。对于前一个问题，可以发现就是每个空位的贡献是 \(max(r_i,r_{i+1})\)。所以把所有的树按照 \(r_i\) 的大小排序，每次把最大的插入其中...

2020-05-10

0 349

省选模拟88 题解

A. 或许容易发现 $u,v$ 联通仅当 $u \oplus v$ 能被集合 $S$ 通过 $\oplus$ 运算表出。所以只需要维护线性基内元素个数。然后暴力的做法就是直接线段树分治。然后有一个能进行删除的离线操作是，不断尝试用被删除最晚的替换线性基中的元素。 B. 这就是 ...

线性基莫队根号分治 dp 状压

2020-05-05

0 381

省选模拟87 题解

A. a 直接构造一个简单的生成函数，就转化为求 $A^n(x)$ 的前 $x$ 项系数。一个很神奇的解决多项式 $A^n(x)$ 前 $n$ 项系数的做法。复杂度为 $O(nk)$，其中 $k$ 为 $A(x)$ 的项数。做法是这样的，对 $A^{n+1}(x)$ 分别用乘法 $A(...

网络流构造题二分图多项式

2020-05-04

0 402

省选模拟86 题解

A. 人生有一点 dp 套 dp 的意思，内层的 dp 就是直接在拓扑序上进行的简单 dp。外层记录的是 dp 的状态，然后 $O(n^3)$ 的做法是显然的。当转移到第 $i$ 个位置的时候，只要关心前面有多少个黑点 dp 值为 $1$，前面有多少个白点 dp 值为 $1$，前面的 d...

字符串状压后缀自动机 dp

2020-05-02

0 380

省选模拟85 题解

A. rng 有这样一个想法，我们把实数值域变成整数的。具体来说就是把给每个区间的 $r_i$ 都减去 $1$。这样的话期望就不难计算了：以值域作为下标，修改就是每次把 $[l_i,r_i]$ 区间加上一个 $\frac{1}{r_i-l_i+1}$。每次查询逆序对，其实就是求这个...

dp 莫比乌斯反演数学线段树

2020-05-01

0 409

省选模拟83 题解

A. table 首先考虑怎么暴力 dp，然后发现难点在于怎么知道不受影响的格点的个数。其实特殊之处在于碰到矩形边界之后没办法计数，所以考虑枚举在哪个位置碰到了矩形边界。然后发现每次转移是类似的，只要求 $a$ 次向下走，$b$ 次向右走，$c$ 次在边界上走能贡献的总的权值。其实等价...

组合计数树状数组 dp

2020-04-29

0 413

概率期望计数题解乱写

CF398B 大概是一种很常见的思路。设 $f_{i,j}$ 表示已经有 $i$ 行 $j$ 列有特殊点。转移只要考虑是放在了怎样的行列中即可计算出结果。因为有自环，所以移项消一下即可。 CF605E 设 $f_i$ 表示 $i$ 号节点到 $n$ 的期望时间。考虑如果有...

2020-04-26

0 402