牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共18篇）

模拟24 题解

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

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

2019-08-17

0 355

模拟31 题解

A. math 考试时打的错解，取每个$a_i$与k的gcd，分别做背包由0直到k。但是复杂度有点问题，于是做了个筛。 $O(k sqrt(k))$一定没有问题，在不构造特殊数据下很优秀。考后突然被自己一个简单的数据hack掉了。 2 6...

dp trie树单调栈

2019-08-25

0 360

模拟37 题解

A. 简单的区间看到这种题，一眼就是枚举最值，则确定左右区间，统计跨最值点的答案。维护前缀和后缀和就完了。于是自然地想到用个主席树，还是枚举小的区间，复杂度$O(nlog^2n)$。复杂度证明见模拟31 C.English 正确的算法一定无法避免枚举小区间，已经带了一个log， ...

启发式合并单调栈 ST表桶分治组合计数 dp

2019-09-06

0 502

模拟44 题解

A. D 显然对于每一个点，它左侧的区间gcd是单调不增的。因为gcd一旦减少至少减半，不同取值不超过log个。从左到右扫一遍的过程中，维护一个单调的pair数组。第一维为区间gcd值，第二维为左端点下标。显然我们只关心同一个gcd值最小的左端点。不断维护一下这个元素个数不超过...

dp 线段树贪心单调栈

2019-09-17

0 303

模拟50 题解

A. 施工又是利用了一些结论的题，因为想不到结论，经常做不出这种题。枚举两个不变的边界，那么中间的建筑必定被提高成相同的小于等于边界的高度。于是设$f_i$表示考虑前i个建筑，并且第i个建筑高度不变的最优答案。设对于转移（i，j），中间建筑的最优高度为t，可以写出dp转移方程。拆...

单调栈 dp 分块容斥直径

2019-09-23

0 469

模拟51 题解

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

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

2019-09-27

0 360

模拟69 题解

A. chess 想一下合法方案是怎样的。因为要保证每一个正方形合法，所以新加的一列中棋子个数等于刚刚删去一列的棋子个数。当$m$很大的情况下，$mod\ n$相同的列转移系数都是相同的。接着考虑，其实$m\ mod\ n$列转移了$m/n+1$次，而$n-m\ mod \ n$列转移...

dp 组合计数单调栈莫队离线并查集

2019-10-12

0 304

模拟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

模拟79 题解

A. 树发现问题是树上对祖先链维护单调栈，然后分别二分权值和深度。因为已经做过一个类似的题，直接维护一个基于倍增进行二分的链栈（或者叫可持久化单调栈？）就完了。 B. 环 circle 一个结论是：在竞赛图中，要么不存在环，要么存在的最小环为三元环。虽然想不到，...

单调栈图论桶结论题

2019-10-20

0 365

模拟89 题解

A. 666 应当注意到一个结论：带着一个剪贴板进行删除操作是没有意义的。可以转化为粘贴之后删除。所以直接跑spfa求最短路。注意到答案不超过48，所以边权超过48的边可以忽略。 B. 1234567 显然用莫比乌斯函数容斥。发现答案为$\sum \lim...

线段树单调栈最短路数论分块莫比乌斯函数杜教筛

2019-10-27

0 430