牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共7篇）

模拟26A 题解

A. marshland 考试时想到了网络流，然而不会建图，就死了。正解是最大费用可行流。比较容易想到的是将每个点拆为两个点， s连没有危险值的入点，没有危险值的入点连有危险值的入点，入点出点之间限流有费用，出点再连没有危险值的出点，这些出点连向t。不断跑spfa，通过有流量...

二分答案网络流后缀数组 bitset 树链剖分

2019-08-20

0 385

模拟96 题解

A. 求和显然可以将式子中的行列贡献分开考虑。于是问题转化为等差数列求和。然而模数比较大，为了避免高精度可以用慢速乘。 B. 分组配对显然问题具有单调性，于是可以二分答案，然而这个算法并没有什么用。考虑使用基于倍增的二分。然后用个归并排序，因为$\sum ...

倍增二分答案 dp set 启发式合并树链剖分

2019-11-04

0 408

省选模拟10 题解

A. 食物链在拓扑序上dp。 B. 选点游戏要求支持合并两棵树，并同时维护树上最大独立集。考虑特殊情况，每次只加一个标号最大的点，问题是一个简单的动态dp。离线出最终树的形态，考虑加入的一个叶子节点，更新该节点到1号节点的轻链上信息就可以了。其实想到这里，一个动态dp的做...

拓扑排序树链剖分 dp 期望动态dp

2020-01-29

0 365

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

省选模拟17 题解

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

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

2020-02-03

0 424

省选模拟29 题解

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

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

2020-02-23

0 313

省选模拟104 题解

A. 签到题把每个点向它右侧比他大的第一个点之间连边，如果没有那么向 \(root\) 连边。那么可以构成一棵树。特判一些情况之后，可以认为问题就是： 1.给某节点和它的所有儿子节点权值加上一个值。 2.询问一条路径的权值和。首先考虑如果只询问单点的维护方法，其实就是打一个标记表...

线段树网络流树链剖分

2020-05-23

0 362