Logo zuotingting的博客

博客

CSP模拟二题解

2023-02-02 11:16:12 By zuotingting

站队问题

因为每一个人都有一个属于自己的最终位置,这个位置可以通过排序后得到,所以我们可以从前往后依次让每一个人换到他最终的位置之后,他就不用再动了。(就像是给每一个人分配座位,你走到这人面前对他说:“朋友,你去那个座位”,然后他去了就不用再动了)。具体代码只需要模拟这个思路即可。这里借助map随时记录每个人的位置(当然也可以用其他方法)

avatar

奶牛的执念

先排序,然后dp[i]表示之前都满足要求,选到第i个之后的可能总数。思路是选第i个的时候,有两种可能,一种是其归属于上一个棚,此时就是dp[i+1],另一种是其自记分一个棚,此时就是dp[i+ai[i]]。

然而在选第一个的时候,他已经不可能归属上一棚了,因此dp[1]=dp[1+ai[1]]

avatar

城市魅力

首先要读懂题目,题目中指出互通并相等的位置是一个公司。所以我们可以用BFS来确定一个公司,连通的则为一个公司(bfs的同时判断是否美丽,对于每个点都判断周围没有比他大的,一旦有一个大的,则不算美丽的公司),bfs的这一个公司全部标记0,不用重复遍历。

avatar

avatar

avatar

欣欣找宝藏

 这题就是结构体排序,让每个点高度从小到大排序。然后累加欧几里得距离即可。

avatar

评论

xushuoxin
第二题有点前后矛盾了: "所以我们要先排个序,从大到小。" sort(a+1,a+n+1); 程序中写的是从小到大吧
xushuoxin
第三题用dfs应该能过吧
Andy0815
@zuotingting “queue<node>p”是什么意思?
H4K16a5
很好,三年没碰C艹已经快看不懂了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。