2024.10.6日比赛总结

比赛总结

  • 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(dpi1,j,dpi,j1,dpi1,j1)
d p i − 1 , j − 1 dp_{i-1,j-1} dpi1,j1时记得特判一下,确保两数不同。
接下来需要优化:我们知道两个数组都是 n n n 的排列,所以如果 A i = B i A_i=B_i Ai=Bi,那么也有且只有这一个相同,其他一定都不与这一位相同,所以只需要记录一下这一位的位置,到时候特判一下。

D题:不会啊qwq

上一篇:【React】事件机制-事件绑定(this)


下一篇:在QT中将Widget提升为自定义的Widget后,无法设置Widget的背景颜色问题解决方法