牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟51 题解

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

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

2019-09-27

0 360

模拟50 题解

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

单调栈 dp 分块容斥直径

2019-09-23

0 469

模拟49 题解

A. 养花利用根号的一些性质，可以得到很多在最坏情况下$n\sqrt n logn$的算法，然而出题人似乎根本没有给这个算法分的意思。正解是分块。预处理出每个块内对于每个k的答案。对于询问，大块直接统计，小块暴力就可以了。设值域为s，块的大小为q，那么总共有$\frac{n}...

分块 dp 最短路

2019-09-22

0 371

模拟48 题解

A. String Master $O(n^3)$随便做。 B. Tourist Attractions 因为数据范围$n^2$没有任何问题。考虑设$dp(i,j,k)$表示节点i从节点j来，并再走k步的方案数。显然$dp(i,j,1)=du(i)-1$，除了返回j，...

最短路 bitset dp

2019-09-22

0 384

模拟47 题解

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

线段覆盖线段树 KMP 字符串

2019-09-20

0 368

模拟46 题解

A. Set 原序列中，一定存在一段连续的区间，保证区间和整除n。不妨将区间和表示为前缀和的形式，如果存在任意两个相同的取值，那么该区间合法。而前缀和总共有n+1个，不同的取值最多有n个，固一定存在至少一个合法区间。 B. Read 题意其实是问序列中是否存在大于...

trie树

2019-09-19

0 450

模拟45 题解

A. kill 显然本题可以二分答案。于是问题转化为判断一个距离是否可行。将人和怪物分别按位置排序，那么每个人选择范围内可以选择的最靠左的怪物，不会使答案更差。单调指针扫一遍就可以了。 B. beauty 统计每条边儿子方向上的关键点数量，设为$cnt[i]$...

二分答案单调指针结论题 lct 最小生成树

2019-09-18

0 369

关于lct维护动态生成树问题

水管局长数据加强版题意是要求维护一棵最小生成树，支持删边操作。删边操作比较难处理，因为如果删掉树上的边，很难从已经有备选集合中找出连接不同联通块的最小的边。然而题目并没有要求在线。所以离线。问题由删边转化为加边。考虑加的每一条边：如果两个点没有联通，直接联通。如果两...

主席树 lct 最小生成树

2019-09-17

0 435

模拟44 题解

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

dp 线段树贪心单调栈

2019-09-17

0 303

模拟43 题解

A. A 发现不断加a，乘b。枚举将s乘k次b，则有 $t=s*b^k+\sum \limits_{i=0}^{k-1}used[i]*a*b^i$ 答案即是使得$\sum \limits_{i=0}^{k-1}used[i]$最小的方案。将s，t表示为b进制会比较好算。当a=1时...

dp 组合计数欧拉函数贪心三分

2019-09-15

0 284