题目链接（牛客网）：[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数组可能是二维或者三 […]