牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟8 题解

A. 匹配 $Hash$直接搞。如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。 B. 回家刚开始以为是割点，打完后仔细一想发现不对。于是打了圆方树，没有什么技巧。另一种简单的做法：只判断割点，但修改判断割点的方法。 ...

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 308

模拟47 题解

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

线段覆盖线段树 KMP 字符串

2019-09-20

0 368

模拟78 题解

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

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

省选模拟37 题解

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

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

2020-03-04

0 376

noi前第十六场题解

##A. 小B的班级莫名想到了一个结论，这种题可以找到选中的点形成的重心。然后求所有点与重心距离的和即可。原因是，任意一个子树大小均小于 \(m\)，所以总可以构造出方案。在这道题中，只要枚举最接近 $1$ 号点的可能的重心，然后计算方案数就可以 \(O(n^3)\)。仔细想一下，可以把...

线段树分治单调栈 KMP 字符串

2020-07-30

0 518