牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共15篇）

模拟10 题解

A. 辣鸡(ljh) 模拟。对于同一块内的答案，直接统计。对于不同块内的，枚举i和大于i的$j=i+1～n$，一个有效的剪枝：以$x_1$为第一维排序，当$x_{1j}>x_{2i}+1$时break退出循环。然而如果用纵向链状的数据还是会被卡成$O(n^2)$，然而...

数学期望启发式合并线段树模拟

2019-07-30

0 344

模拟24 题解

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

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

2019-08-17

0 355

模拟30A 题解

A. 树联想起远古考试时做的题记忆的轮廓。树上走一些步数的期望。显然可以直接解方程。然而复杂度$O(qn^3)$，利用树上的性质优化一下，直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。然而只有20分。预处理出每个点走到每个儿子的期望步...

dp 期望 Hash 二分答案字符串启发式合并

2019-08-25

0 306

模拟37 题解

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

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

2019-09-06

0 502

模拟58 题解

A. Divisors 看题看了很长时间。然后发现似乎是弱智题。用一个哈希表统计每个因子出现了多少次就可以了。 B. Market 显然将物品和询问都排序，单调指针就不用管时间限制。刚开始看成了无限背包，看到数据范围就傻了，$c=10^9$还无法矩阵快速幂。打...

并查集离线直径 dp 分治线段树启发式合并

2019-10-03

0 383

模拟94 题解

A. 凉宫春日的忧郁数据范围就长得很可写高精度的样子。可以维护高精度的高位，舍弃低位信息。正解是取对数。 $x^y=y*log\ x$ $y!=\sum \limits_{i=1}^{y}log\ i$ 然后可以直接比较两个取对之后的$double$类型。 B....

启发式合并分治虚树 dp 差分

2019-10-30

0 343

模拟96 题解

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

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

2019-11-04

0 408

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394

模拟111 题解

A. 物理课发现每次反弹之后移动的距离是上一次的$d^2$倍。计算出第一次反弹之前移动的距离的答案$k$，总的答案即$\sum \limits_{i=0}^{inf}d^{2*i}*k$。发现这个东西就是一个等比数列求和。设答案为$s$，那么有$s=\sum \limits_{i...

线段树分治并查集启发式合并组合计数

2019-11-12

0 343

省选模拟16 题解

A. GCD和LCM 简单莫比乌斯反演。因为有一个$a$的限制，我们离线询问，将询问按$a$排序。随时更新要维护来统计答案的数组就可以了。 B. 平面图给出了平面图，所以自然想到对偶图。如果知道平面图上每个点所连的边的顺序，一个平面图转对偶图的方式是：考虑给每条边开两个...

启发式合并并查集莫比乌斯函数

2020-02-02

0 360