牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共21篇）

奇袭 CodeForces 526F Pudding Monsters 题解

考场上没有认真审题，没有看到该题目的特殊之处：保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样的。于是无论如何也想不到复杂度小于$O(n^3)$的算法，只好打一个二维前缀和草草了事。所以还是要仔细审题。 $O(n^2)$算法：因为每行上只有一个军队，...

分治桶

2019-07-16

0 341

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

模拟60 题解

A. 嘟嘟噜约瑟夫问题，然而线性过不去。观察本题的特殊性质：m远小于n。再看递推公式，发现当m很小的时候取模次数并不多，所以在这种情况下可以直接用一次乘法代替多次加法。 B. 天才绅士少女助手克里斯蒂娜拆一拆式子就可以将i和j分离出来。然后用分治的思想在线...

分治线段树树状数组 dp

2019-10-06

0 341

模拟93 题解

A. 序列一眼二分，然后发现二分有点不对？一测大样例果然不对，因为有两个限制，问题并不具有单调性。作前缀和后问题其实是个三维偏序问题，似乎还得一个$log$复杂度。先打个$cdq$分治套树状数组，结果极限数据$0.3s$，所以就$AC$了。正解确实是一个$log$。最后一维偏...

dp 树状数组分治高斯消元

2019-10-30

0 400

模拟94 题解

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

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

2019-10-30

0 343

模拟103 题解

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

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

2019-11-07

0 394

模拟104 题解

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

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

2019-11-07

0 405

模拟106 题解

A. 合并集合显然的区间dp。断环成链，预处理出每个连续区间集合的元素个数。然后直接dp就完了。 B. climb 想了一些简单的贪心，然后都伪了。所以考虑如何暴力$O(n^2)$来做这个题。枚举最终用来跳最后一步的药丸，显然前面的药丸可以按$a_i-b_i...

并查集博弈论区间dp dp 拓展域分治线段树

2019-11-09

0 490

模拟111 题解

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

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

2019-11-12

0 343