牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟44 题解

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

dp 线段树贪心单调栈

2019-09-17

0 303

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

模拟49 题解

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

分块 dp 最短路

2019-09-22

0 371

模拟50 题解

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

单调栈 dp 分块容斥直径

2019-09-23

0 469

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

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

模拟54 题解

A. x 不妨考虑每一个质因子。那么拥有这个质因子的所有数都应当被分入一个集合中。而不拥有这个质因子的数可以有两种选择。将每个质因子的情况综合起来，用并查集维护一下联通块数量，答案就是$2^{cnt}-2$ B. y 暴力dp的设计是简单的，显然可以使用...

并查集搜索 dp 模拟

2019-09-29

0 804

模拟55 题解

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

线段树三分 dp

2019-09-29

0 286

模拟57 题解

A. 天空龙一个很好的性质是：最优方案可以不存在一个颜色A，转化为B再转化为C。因为将A直接转化为C一定更优。所以无需分类讨论，直接用一个sum判断正负就可以了。 B. 巨神兵有向图无环，所以存在拓扑序，所以用分层图dp。设f(i,j)表示已经考虑点集i，并且...

dp 容斥状压拓扑排序

2019-10-03

0 410