题目链接：E - Putting Candies (atcoder.jp) 题目大意 给定一个长度为 N 的序列，X 从 0 开始，sum 一开始是0，进行 K 次操作，每次将 A[X] 加到 sum 中，并更新 X = sum % N。求最后的 sum。 数据范围详见原题。 思路 K的范围较大，但是N的范围较小，所以考虑从N入手。K远大于N，所以大概率会出现重复的X，而且重复出现的X的状态和之前 […]

题目链接：Largest Rectangle in a Histogram (nowcoder.com) 题目难度3星，做法比较多，稍微优化一下的暴力枚举也能过，这里写一下单调栈的做法。 题目大意 给一个类似条形统计图的东西，每个点有各自的高度，求可以从中截取的最大矩形面积。 思路 有可能是最大矩形的矩形其实就是各个点的高度，向左右延伸最长距离得到的。 那么就遍历每个点，向左右延伸，直到遇到比该点 […]

题目链接：D - Sequence Query (atcoder.jp) 题目大意 一开始有一个空序列A，可以进行三种操作，共进行Q种操作。 操作1 x：将 x 插入到序列A中。 操作2 x k ：求序列A中比 x 小且第 k 大的数。 操作3 x k ：求序列A中比 x 大且第 k 小的数。 数据范围详见原题。 思路 最典型的思路是维护一个有序序列，然后二分查找进行操作2 3，二分的复杂度为O( […]

题目链接（牛客网）：[USACO 2006 Nov S]Bad Hair Day (nowcoder.com) 视频教程：[USACO 2006 Nov S]Bad Hair Day（单调栈）_哔哩哔哩_bilibili 题目大意： FJ有n只牛（0 <= n <= 80,000），每只牛有一个独特的身高（不会出现一样高的牛），每头牛向右看，能看见所有比自己矮的牛，直到遇到比自己高的牛 […]

题目链接：1611 -- The Suspects (poj.org) 题目大意（我自己翻的）： SARS病毒很猛，接触了就感染，0号是最初的感染者，接下来将编号为0~n-1的人分组（同一个组内的人都发生了接触），问有多少人会感染SARS？ 输入格式（多组输入） n m k1 a1 a2 a3...ak1 k2 a1 a2 a3...ak2 km a1 a2 a3...akm 当n m都为0时结束 […]

首先解释一下什么是并查集，来自百度百科： 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。 这段文字讲的很详细，其实我们可以通俗的将并查集理解成一种处理点集之间的连通关系的数据结构。 既然是数据结构，那么就应该有对应的图来描述。并查集由许多相连或者不相连的点组成，我们维护这些点的祖先（父节点的父节点的父节点........ […]

题目传送门：小A买彩票 思路 观察数据范围 0 <= n <= 30，如果使用搜索的话，复杂度是O(2 ^ N)显然不行，因为这里的每个状态（购买彩票的数量）之间是有关联的，所以考虑DP，但是这个DP不是线性的。 既然知道是DP，那么就需要给每个状态一个准确的定义，这时候有个小技巧就是观察数据范围，n最大为30，30的平方不会超，30的三次方也不会超，所以我们的dp数组可能是二维或者三 […]