站队问题
因为每一个人都有一个属于自己的最终位置,这个位置可以通过排序后得到,所以我们可以从前往后依次让每一个人换到他最终的位置之后,他就不用再动了。(就像是给每一个人分配座位,你走到这人面前对他说:“朋友,你去那个座位”,然后他去了就不用再动了)。具体代码只需要模拟这个思路即可。这里借助map随时记录每个人的位置(当然也可以用其他方法)
奶牛的执念
先排序,然后dp[i]表示之前都满足要求,选到第i个之后的可能总数。思路是选第i个的时候,有两种可能,一种是其归属于上一个棚,此时就是dp[i+1],另一种是其自记分一个棚,此时就是dp[i+ai[i]]。
然而在选第一个的时候,他已经不可能归属上一棚了,因此dp[1]=dp[1+ai[1]]
城市魅力
首先要读懂题目,题目中指出互通并相等的位置是一个公司。所以我们可以用BFS来确定一个公司,连通的则为一个公司(bfs的同时判断是否美丽,对于每个点都判断周围没有比他大的,一旦有一个大的,则不算美丽的公司),bfs的这一个公司全部标记0,不用重复遍历。
欣欣找宝藏
这题就是结构体排序,让每个点高度从小到大排序。然后累加欧几里得距离即可。