牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟23 题解

A. mine 设dp(i,0/1/2/3,0/1)表示前i位，且第i位填入0/1/2/炸弹的方案数。当第i位填入1的时候，需要关注炸弹在1的左侧或者右侧，故加半维表示炸弹在1的哪一侧，当i为不为1，最后一维无意义。简单转移。 B. water 第一眼：直接考虑临...

dp 最小生成树莫比乌斯函数桶容斥

2019-08-16

0 407

模拟24 题解

A. Star Way To Heaven 如果二分答案，问题就转化为不经过一些等大的圆，能否从左侧到达右侧。然后我就不会了。其实问题很简单：不能从左侧走到右侧，等价于能从下侧沿障碍走到上侧，也就是说一些圆将路阻断开。二分答案，用并查集或者dfs都可以做到$O(k^2)$建边之后$...

启发式合并线段树单调栈最小生成树凸包

2019-08-17

0 355

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

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

主席树 lct 最小生成树

2019-09-17

0 435

模拟45 题解

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

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

2019-09-18

0 369

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365

模拟73 题解

A. 小P的2048 简单模拟。 B. 小P的单调数列首先有一个简单的dp。设$dp_{i,j}$表示已经选择的最后一个是第$i$个数，已经有了$j$个单调段。转移并不困难，简单数据结构维护一下可以做到$O(n^2logn)$ 然后发现这个dp的第二维其实可以省去。 ...

模拟结论题最小生成树

2019-10-14

0 363

省选模拟14 题解

A. 开车关系似乎和欧拉回路很大。所以考虑首先通过构造欧拉回路的方式干掉所有的偶度点。然后发现问题转化为所有奇度点的最小带权匹配。刚开始的思路一直局限于靠原有的边匹配。后来发现只要是一条路径连接即可。考虑利用题中的特殊性质，二进制下所有小边的加和不大于大边。所以直接使用最小生成树...

最小生成树欧拉路杨氏矩阵

2020-02-01

0 335

LCT 题解乱写

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

最小生成树 lct

2020-03-17

0 398

省选模拟76 题解

A. MiniumCut 首先看到这个题，可以想到最小割树。然后发现原图的最小割树与原图是等价的。那也就是说，答案可以表示为一个树。然后考虑如何求出来这个树。大概的思路就是由小到大考虑每一组关系或者由大到小考虑每一组关系。这里用后一种思路，大概套用一下类似克鲁斯卡尔重构树的思想，然...

最小生成树回文自动机 Hash dp

2020-04-21

0 419

省选模拟100 题解

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

最小生成树 lct dp

2020-05-19

0 409