牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

bzoj5461 Minimax 题解

https://www.lydsy.com/JudgeOnline/problem.php?id=5461 看到题目，必将m种权值离散化。首先是一个显然的dp设计。设$f(i,j)$表示第i个节点，最终取值为j（已离散化）的概率。因为树上的节点儿子数不超过2，不妨设值k出现在左儿子上。...

dp 线段树

2019-09-02

0 366

模拟40 题解

A. 队长快跑非常显然的数据结构优化dp，线段树下标为a的最小值，要求支持区间最值，区间加，单点取max。随便写下转移方程就好了。 B. 影魔树上数颜色？但是要求了一个深度。我的做法是将询问离线，显然在一个询问中我们只关注每种颜色在该子树中出现的最...

dp 树状数组线段树离线

2019-09-08

0 358

模拟41 题解

A. 夜莺与玫瑰与题解中的定义类似：枚举每个斜率，设为向量$(a,b)$ 如果$gcd(a,b)!=1$，那么直接跳过。考虑每个点(x,y)，它的前趋为(x-a,y-b)，后继为(x+a,y+b)。一个点是合法的当且仅当不存在前趋，存在后继。于是$ans=\sum \limit...

点分治组合计数线段树

2019-09-10

0 346

模拟44 题解

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

dp 线段树贪心单调栈

2019-09-17

0 303

模拟47 题解

A. Emotional Flutter 显然第一步的位置只有k种不同的取值。前缀和对步长k取模，那么每条黑线限制的是一段连续区间。问题是是否完全限制k个位置。第一个思路是动态开点线段树，想了想，害怕卡空间，没打。之后的想法是将每条线段离线下来，对线段的左右端点和两条线段之间的区域...

线段覆盖线段树 KMP 字符串

2019-09-20

0 368

模拟51 题解

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

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

2019-09-27

0 360

模拟52 题解

A. 平均数刚开始没想到。突然想到二分判定。然后想到平衡树，想着这题也太难了。然后想到树状数组离散一下就好打了。然后忘了开longlong，被搞成了60分。其实精度确实有问题，和暴力拍千组左右数据会出错。所以其实问题是求逆序对，打归并排序或许常数会小一点。 ...

二分答案矩阵 dp 线段树

2019-09-27

0 338

模拟55 题解

A. 联一眼线段树。觉得T1似乎不应该这么难打。然而看了几分钟没有想出更好的做法。于是花了二十多分钟码了线段树。段错误一会之后，一遍过样例就交了。后来对拍也过了，很偷税。所以直接维护一下出现位置最靠坐的0 1就行了。一种比较好的离散化做法是将左闭右闭的区间转化为左闭右...

线段树三分 dp

2019-09-29

0 286

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