牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共18篇）

模拟99 题解

A. 陶陶摘苹果一眼线段树维护单调栈，所以写就完了。当然本题中修改不继承，所以有更好的一个$log$的做法。 B. 开心的金明贪心地选择当前最优的策略。用一个$set$维护备选的集合。当跨月的时候，如果集合中元素个数大于限制数，可以不断去除最劣的选择。 ...

set 贪心线段树单调栈构造题

2019-11-04

0 359

模拟102 题解

A. 你相信引力吗显然是单调栈处理。然而优弧/劣弧两种情况，加上高度存在相同，就比较难处理。然而环是可以平移的，所以一个好的方法是将其中的最大值移到一个端点，于是跨环端点的情况只出现在右半部分形成一个单调不降的序列。顺便去重就可以了。 B. 停不下来的团长奥...

图论 dp 线段树单调栈拓扑排序并查集

2019-11-06

0 327

模拟104 题解

A. 中间值二分答案在数组$a$中的排名，则得到期望的在数组$b$中的排名。当数组$b$中对应的数恰好是大于二分值的第一个数，代表二分到了答案。通过对应的数与当前数的大小关系，可以确定二分方向。同理还应当二分答案在数组$b$中的排名。然而这个做法实现比较困难，还有另一个更帅的二分...

分治二分答案线段树 dp 单调栈

2019-11-07

0 405

模拟114 题解

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

倍增单调栈凸包

2019-11-14

0 333

数据结构+插头dp+多项式题解乱写

可持久化数据结构 A.森林树上的数据结构常可以启发式合并，用启发式合并的思路合并树上主席树就可以了。 B.影魔一个常见的这种数据结构题的套路是：离线询问，按右端点排序。在右指针扫过去的同时在数据结构（常为线段树）中更新该右端点能产生的答案。同时在数据结构中查询统计右端点对应的区间就好...

单调栈线段树状压 dp 多项式

2019-12-29

0 450

省选模拟102 题解

A. island 对于正负不同的情况，\(O(n)\) 枚举左侧的位置然后计算。对于正负性相同的情况，把笛卡尔树建出来，然后每次考虑跨过最小值的贡献。分几种情况：左右均不超过最小值，左右仅有一个超过最小值，左右都超过最小值。然后顺便统计上其中一个端点为划分点的贡献。然后疯狂的写式子拆式子就没...

圆方树贪心单调栈

2020-05-21

0 388

noi前第十六场题解

##A. 小B的班级莫名想到了一个结论，这种题可以找到选中的点形成的重心。然后求所有点与重心距离的和即可。原因是，任意一个子树大小均小于 \(m\)，所以总可以构造出方案。在这道题中，只要枚举最接近 $1$ 号点的可能的重心，然后计算方案数就可以 \(O(n^3)\)。仔细想一下，可以把...

线段树分治单调栈 KMP 字符串

2020-07-30

0 518

noi前第十七场题解

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

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

2020-08-02

0 555