比赛总结
- 2024.10.6日比赛总结
- A题:
- 题面描述:
- 解法分析:
- B题:
- 题面描述:
- 解法分析:
- C题:
- 题面描述:
- 解法分析:
- D题:不会啊qwq
2024.10.6日比赛总结
A题:
题面描述:
我们有一个长度为 k k k 的序列,要在其中取出 n × m n\times m n×m 个数来组成一个矩阵,矩阵每一行的代价为这一行的最大值减去最小值,整个矩阵的代价为所有行的代价的最大值。问:矩阵代价最少是多少。
解法分析:
由于涉及最大值最小问题,首先想到二分答案。我们知道,如果给原来的 k k k 个数排序(从小到大),那么组成每一行的 m m m 个数一定连续的,因为这样才能保证最大值和最小值在区间的两侧。于是,我们使用 O ( m ) O(m) O(m) 枚举找到这些区间,如果满足条件的区间超过 n n n 个,就返回一。
B题:
题面描述:
有 n n n 个点,可以与其他点碰撞产生反应 。现在我们给定一些关系,只有有关系的点相互碰撞才可以得分。问:最高得分是多少?
解法分析:
关系作用于两点之间, A A A 与 B B B 的关系应当是相互作用的,所以可以把关系网看为一张无向图。经过研究,发现,无向图只要联通,所有点都是可以互相到达的。但是总有一个点是别人到达他,而他自己无法到达,我们称为“聚点”。根据前面的推论,聚点的个数应当等于联通块的个数,而其他所有点都可以到达其联通块所在的聚点(即处聚点外的所有点都可以得分),所以分数为点数减联通块数。用 b f s bfs bfs 或 d f s dfs dfs 求一下联通块染色即可。
C题:
题面描述:
有两个数组, A A A, B B B都是 n n n 的排列。如果 A i ! = B i A_i!=B_i Ai!=Bi那么可以将两者同时取出,否则只能选择其中一个数组并取出第一位,问:最少需要取多少次。
解法分析:
看到这题,一眼DP,我们现将好想的
n
2
n^2
n2 暴力DP写出来。
d
p
i
,
j
dp_{i,j}
dpi,j表示
A
A
A数组取了
i
i
i个,
B
B
B数组取了
j
j
j个的最优答案。解析式并不难推导:
d
p
i
,
j
=
min
(
d
p
i
−
1
,
j
,
d
p
i
,
j
−
1
,
d
p
i
−
1
,
j
−
1
)
dp_{i,j}=\min(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1})
dpi,j=min(dpi−1,j,dpi,j−1,dpi−1,j−1)
d
p
i
−
1
,
j
−
1
dp_{i-1,j-1}
dpi−1,j−1时记得特判一下,确保两数不同。
接下来需要优化:我们知道两个数组都是
n
n
n 的排列,所以如果
A
i
=
B
i
A_i=B_i
Ai=Bi,那么也有且只有这一个相同,其他一定都不与这一位相同,所以只需要记录一下这一位的位置,到时候特判一下。