牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

模拟61 题解

A. 砖块简单模拟。对于最后一问，算一算复杂度就可以知道开map没有任何问题，然而map真的方便很多，所以为什么不用呢。 B. 数字容易发现末尾的0一定是被质因子2和5凑出。并且，对于任意的$n!$，质因子2的个数不小于质因子5的个数。简单的暴力$O(n)$做...

线段树模拟吉司机线段树 Hash 中国剩余定理数学

2019-10-06

0 416

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365

zkw线段树学习笔记

ZKW线段树应某迪要求，写一篇数据结构学习笔记。实际上还没有学很多东西，只是一些基础的操作。 zkw线段树的学习资料，网上有很多，这里记录的只是自己的一些理解。建树 1 inline void build(){ 2 for(bit=1,n=read();bi...

线段树

2019-10-07

0 421

模拟87 题解

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

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

2019-10-25

0 374

模拟89 题解

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

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

2019-10-27

0 430

模拟90 题解

A. 新的世界显然与顺序无关，所以问题转化为最短路问题。用$dijkstra$的思想贪心。 B. 邻面合并看到这个数据范围，显然是状压。矩形上的操作，考虑轮廓线/插头dp。然而逐个转移似乎有些复杂，所以逐行转移，大力分类讨论。压缩状态的方法有很多。 ...

最短路状压 dp 线段树轮廓线

2019-10-27

0 308

模拟91 题解

A. Dove 打扑克显然的结论是：超过$\sqrt n$的牌堆不会超过$\sqrt n$个。所以可以分块维护信息：对于牌数小于$\sqrt n$的，用一个桶维护。对于牌数大于$\sqrt n$的，用$vector$暴力插入删除维护。同时维护答案，为了做到$O(1)$修改，也用分...

分块 dp 线段树猫树位运算

2019-10-28

0 386

模拟92 题解

A. 数列要求$ax+by=s$，使得$abs(x)+abs(y)$最小的一组解$(x，y)$。首先用$exgcd$求出一组特解$(x_1,y_1)$。因为$a,b$均为正数，可以将$s$转化为正数。不妨将解$x,y$画到一个坐标系上，显然$abs(x)+abs(y)$在$x$接...

exgcd dp 线段树最短路

2019-10-29

0 315

模拟97 题解

A. 小盆友的游戏手玩表找规律。 B. 花弱智$dp$题，用逆元随便处理一下就能处理字符集很大的问题。 C. 表格利用了扫描线的思想。首先将横坐标离散化，对纵坐标建线段树。枚举横坐标，则矩形转化为在横坐标的左边界$insert$，在右边界+...

扫描线 set 线段树

2019-11-04

0 729

模拟99 题解

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

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

2019-11-04

0 359