牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共11篇）

关于lct维护动态生成树问题

水管局长数据加强版题意是要求维护一棵最小生成树，支持删边操作。删边操作比较难处理，因为如果删掉树上的边，很难从已经有备选集合中找出连接不同联通块的最小的边。然而题目并没有要求在线。所以离线。问题由删边转化为加边。考虑加的每一条边：如果两个点没有联通，直接联通。如果两...

主席树 lct 最小生成树

2019-09-17

0 435

模拟45 题解

A. kill 显然本题可以二分答案。于是问题转化为判断一个距离是否可行。将人和怪物分别按位置排序，那么每个人选择范围内可以选择的最靠左的怪物，不会使答案更差。单调指针扫一遍就可以了。 B. beauty 统计每条边儿子方向上的关键点数量，设为$cnt[i]$...

二分答案单调指针结论题 lct 最小生成树

2019-09-18

0 369

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418

省选模拟20 题解

A. Ring 似乎算是一道半原题，原题的做法是维护环上的最小编号边，然后替换。本题的是否存在环更好维护。容易发现对于一个左端点，右端点的答案是单调的。存在一个分界点，满足分界点左侧没有环，分界点右侧有环。因为单调，所以可以在左端点移动的同时，右端点用单调指针维护分界点的位置。 ...

lct 线段树单调指针

2020-02-07

0 349

省选模拟29 题解

A. circle 容易发现，如果存在一组合法答案，那么 $k$ 个钦定点之间和 $n-k$ 个不被钦定点之间一定都是存在拓扑序的。考虑一个不被钦定点不被删去，一定满足这个点的连边情况恰好满足在 $k$ 个点的排名上存在分界点。上面那个条件使得不存在不被钦定点与两个被钦定点之间的环，另一...

线段树树链剖分 lct dp 竞赛图

2020-02-23

0 313

省选模拟39 题解

A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。容易发现交换的次数就是点数减环数。所以原题转化为环的计数问题。考虑把已有的每个连通块的部分表示出来。容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。如果已...

lct 二项式反演后缀自动机容斥组合计数

2020-03-06

0 410

省选模拟48 题解

A. 事情的相似度问题是区间内最大的点对 $LCS$。容易发现 $LCS$ 其实就是两个前缀的终止节点的 $lca$ 的 $len$。考虑对每个 SAM 上节点搞一个 set 维护 endpos 集合。每次的操作就是合并两个集合，然后节点 $x$ 上 endpos 集合中两两可以形成...

搜索扫描线后缀自动机 lct 线段树启发式

2020-03-17

0 383

LCT 题解乱写

LCT 水管局长问题是要求支持删边，询问给定两点之间路径的边权最大值的最小值。可以通过动态最小生成树解决。因为不强制在线，考虑将删边转化为加边。于是只要维护链上的最大权值，每次尝试割最大边权边并加入当前边就好了。 GERALD07 对于树形结构，联通块数=点数-边数。 ...

最小生成树 lct

2020-03-17

0 398

省选模拟100 题解

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

最小生成树 lct dp

2020-05-19

0 409