牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟24 题解

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

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

2019-08-17

0 355

模拟51 题解

A. Tree 可以发现，在开始时以1为根处理出dfs序。那么： 1.修改节点的子树不包含lca，那么直接使用该节点的子树区间。 2.修改节点的子树包含lca，那么只要扣掉lca在该节点的哪一个儿子的子树部分就可以了。对于换根lca：分类讨论即可正解是求出root与a，root...

ntt 生成函数 dp 线段树单调栈凸包

2019-09-27

0 360

模拟75 题解

A. 导弹袭击想到了凸包，推出了题中的式子，然而没有继续推下去。或者说，高考数学线性规划没有学好。一种导弹的飞行时间函数为： $z_i=A*\frac{1}{a_i}+B*\frac{1}{b_i}$ 似乎显然是一个线性规划式，设$x=\frac{1}{a_i},y=\frac{1}...

dp 单调栈凸包高斯消元倍增

2019-10-16

0 0

模拟87 题解

A. maze 做过类似的题，维护最短路对于$k$的一个凸包，答案就是凸包与$y=s$直线交点的横坐标，这个还挺难打的。然而答案显然具有单调性，所以直接二分答案就完了。实际上，这个二分答案的操作，等价于选定直线$x=mid$，求出$x=mid$与凸包的交点的纵坐标，并通过这个纵坐标与$...

凸包二分答案 dp 线段树字符串

2019-10-25

0 374

模拟88 题解

A. 军训队列仔细看题，会发现问题是随便交换位置。为了使答案更小，显然可以进行排序后$dp$。有$dp_{i,k}=dp_{j-1,k-1}+(a[i]-a[j])^2$。拆开平方式会发现是最简单的斜率$dp$式，而且$a$数组是单调的。所以用单调队列维护一下凸包就完了。因为...

dp 模拟凸包状压

2019-10-26

0 321

模拟114 题解

A. A 正解是给二次函数除一个$x$，于是问题转化为简单的单调栈维护凸包问题。最后直接乘回一个$x$就好了。然而考场上并没有想到这个东西，所以维护答案$x$的最优转移点，暴力枚举最优转移点的前后三百个最优的二次函数就好了。本来以为自己打了个乱搞特别没素质，后来发现因为数据保证值域...

倍增单调栈凸包

2019-11-14

0 333

省选模拟31 题解

A. Skip 一眼决策单调性，但是感觉因为带个权值就不好处理了。实际上对权值开个线段树，然后直接在线段树上维护决策单调性就完事了。而且这个式子是一个显然的斜率优化 dp ，在权值线段树上维护凸包也挺套路的。感觉这题没做出来比较可惜，没有想到通过对权值开线段树，来实现权值的无关操作。 ...

状压线段树凸包 dp 决策单调性

2020-02-26

0 410

省选模拟38 题解

A. Inverse 似乎这类问题的套路都是考虑每一个点对。然后考虑一个 dp 。设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。然后发现这个玩意可以优化，如果枚举翻转区间...

分块单调指针差分 dp 计算几何平衡树凸包

2020-03-05

0 428

省选模拟47 题解

A. 老夫发现这个问题有点类似二维偏序。所以考虑类似扫描线的做法，枚举第一个维度，同时在第二个维度上用一个数据结构维护答案。所以枚举 $c$ 的取值，然后发现每次的操作是插入一个点。以值域为下标建立一个数据结构，对应的操作就是前缀加下标，询问操作就是全局查询最大值。所以用一个简单...

凸包扫描线分块 dp 矩阵线性代数

2020-03-16

0 378

noi前第十七场题解

##A. 黑白沙漠考虑这样一个做法，对于每个点处理出左侧和右侧分别的最优决策点，然后比较二者谁更优即可。当然这样的点可以表示为若干个区间，对于其中每个区间，左右侧谁更优是单调的，可以通过二分求解。所以问题就是如何处理出这样的若干个区间。可以想到这个最优决策点就是上凸包会切到的点。所以写一...

网络流凸包分治单调栈线性规划

2020-08-02

0 555