牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共15篇）

省选模拟11 题解

A. 组合数问题还没想明白如何做，待补。 B. recollection 因为原图为trie树，树上两个点的lcp长度等于两个点的lca深度。考虑通过广义sam来维护两个点的lcs。树上同时对应着一个$endpos$，树上两个点对应的$endpos$对应的广义sam上节点在后缀...

并查集平衡树后缀自动机线段树

2020-01-29

0 405

省选模拟16 题解

A. GCD和LCM 简单莫比乌斯反演。因为有一个$a$的限制，我们离线询问，将询问按$a$排序。随时更新要维护来统计答案的数组就可以了。 B. 平面图给出了平面图，所以自然想到对偶图。如果知道平面图上每个点所连的边的顺序，一个平面图转对偶图的方式是：考虑给每条边开两个...

启发式合并并查集莫比乌斯函数

2020-02-02

0 360

省选模拟17 题解

A. 选择可以发现问题是$a$ $b$是否在一个边双里。因为没有强制在线，所以将难处理的删边转化为加边。对于一棵树上的加边操作，只要将两个点之间的路径上的点，添加到同一个边双集合里即可。因为边双的特殊性质，加上并查集的操作，这样只考虑树边的做法是正确的。具体的实现方法实际上通过并...

多项式并查集线段树树链剖分拉格朗日插值二分答案矩阵树定理

2020-02-03

0 424

省选模拟25 题解

A. 环是一道很巧妙的构造题。考虑写出满足条件的 $s_i,s_{i+1}$ 一定满足的式子。设 $x_{i,j}$ 表示 $s_i$ 中第 $j$ 个 $1$ 的位置。由操作A有 $k*t+\sum \limits_{j=1}^k x_{i,j}\equiv \sum \limi...

构造题贪心字符串并查集

2020-02-18

0 344

省选模拟34 题解

A. 倚天剑的愤怒考虑特殊的情况，如果 $a_i <0$ ，那么最优的决策一定是把最差的跳过。然后可以考虑如果存在一个 $a_i>0$ ，那么这个 $i$ 无法对前面的操作产生影响，但是可以是把后面的一些小于 $0$ 的元素抵消掉。抵消之后呢？问题仍然是把最差的跳过。所以...

并查集分治贪心线段树直径

2020-02-29

0 327