Codeforces Round #472 (rated, Div. 2, based on VK Cup 2018 Round 2) Summary

比赛蓝链

A. Tritonic Iridescence

Description

给你一个由个区域组成的帆布,有的区域已经涂上了颜色,有的区域没有颜色。现在告诉你这个帆布的信息,问你是否至少存在两种方案,使得这个帆布不存在两个相邻的区域颜色相同。有就输出Yes,否则输出No

阅读更多

KMP 小结

经典问题

给定一个文本串和一个匹配串,让你求出匹配串在文本串中出现了几次,以及其出现的位置

算法流程

如果用朴素算法去解决问题,复杂度为。于是我们就要去用一个强大的工具——来解决问题了

阅读更多

HDU5923 Prediction

题目蓝链

Description

给你一个个节点,条边的图。再给你一棵个节点的树,如果这课树某一个节点被选择,那么它到根节点的路径上的每一个点都会被选择。每选择一个点,那么图上编号为的边将会被连上。

每次询问给你一个树上的点集,你要选择这个点集,问你连完边之后,图上有多少个连通块

阅读更多

回文树 小结

经典问题

最近学了一个处理回文的一个特别有用的工具:Palindrome Tree

他能很方便求出以下问题:

  1. 在以任意一个位置结束的回文串的数量
  2. 在整个串中本质不同的回文串的个数以及长度

  3. 在整个串中回文串的个数以及长度

阅读更多