牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共6篇）

模拟50 题解

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

单调栈 dp 分块容斥直径

2019-09-23

0 469

模拟58 题解

A. Divisors 看题看了很长时间。然后发现似乎是弱智题。用一个哈希表统计每个因子出现了多少次就可以了。 B. Market 显然将物品和询问都排序，单调指针就不用管时间限制。刚开始看成了无限背包，看到数据范围就傻了，$c=10^9$还无法矩阵快速幂。打...

并查集离线直径 dp 分治线段树启发式合并

2019-10-03

0 383

模拟65 题解

A. Simple 首先求出n,m的gcd，那么显然只有gcd的倍数可能被拼出，其他数一定是不好的数。所以问题转化为用$\frac{n}{gcd}$,$\frac{m}{gcd}$，拼不出的$\frac{q}{gcd}$范围内的数。因为除gcd后的n，m互质，用某凯的疑惑中的结论可知最...

贪心直径数学

2019-10-09

0 750

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

省选模拟34 题解

A. 倚天剑的愤怒考虑特殊的情况，如果 $a_i <0$ ，那么最优的决策一定是把最差的跳过。然后可以考虑如果存在一个 $a_i>0$ ，那么这个 $i$ 无法对前面的操作产生影响，但是可以是把后面的一些小于 $0$ 的元素抵消掉。抵消之后呢？问题仍然是把最差的跳过。所以...

并查集分治贪心线段树直径

2020-02-29

0 327

省选模拟37 题解

A. 奶酪发现问题是求删去每一条边之后两个连通块的直径。也就是子树直径和除掉子树之外的直径。容易发现一个简单的维护三个最值的换根 $dp$ 就解决了。然而换根 $dp$ 容易写错。所以考虑子树直径直接合并就完事了。对于除掉子树之外的直径，可以考虑除掉一段连续的 $dfs$ 序...

dp KMP 高斯消元提交答案直径

2020-03-04

0 376