倍增

洛谷 P5284 [十二省联考2019]字符串问题 题解【后缀自动机】【倍增】【拓扑排序】

考场上唯一一道弃掉的题。看来 SAM 还是挺好玩的 题目背景 Yazid 和 Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基本概念。 对于一个字符串 $S$,我们定义 $|S|$ 表示 $S$ 的...

牛客 178A 最长路 题解【拓扑排序】【贪心】【分层图】【哈希】【倍增】

      这个题是倍增+hash,细节比较多……   题目描述 有一张\(n\)个点\(m\)条边的有向图,每条边上都带有一个字符,字符用一个数字表示。 求以每个点为起点的最长路,输出走过的边的字符构成...

洛谷 P2633/bzoj 2588/spoj 10628 Count on a tree 题解【可持久化】【主席树】【树上前缀和】【倍增】【LCA】

      看上去是个类似树剖的东西,不过是用树上前缀和做的。(树上两点间路径操作不要只想着树剖啊,要想到树上差分/前缀和)   题目描述 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u...