2020.9.6 解题报告

技术文章 1年前 (2020) 完美者
478 0

标签:超过   考试   最小   mat   contain   节点   解题报告   block   max   

2020.9.6

目录
  • 2020.9.6
  • 答题情况
  • 各题目分析
  • 题目解析
  • 代码实现


\[\text{完全憑依!} \]

\[\text{By:Th15.5Block} \]


答题情况

总成绩 : 150 , 排名 : 5 / 6
T1 : 100 T2 : 20 T3 : 30

各题目分析

题目 1 :
预估成绩 : 100 实际成绩 : 100 考试用时 : 8:00 ~ 8:20

签到题。

题目 2 :
预估成绩 : 100 实际成绩 : 20 考试用时 : 8:20 ~ 9:00,10:00 ~ 11:00

先写了 \(O(n^3\log m)\) 的暴力,卡常卡到 2.4s 想出正解。
写完正解扔了,最后 FST 了。
有暴力一定要拍暴力!

题目 3 :
预估成绩 : 0 实际成绩 : 30 考试用时 : 9:00 ~ 10:00,11:00 ~ 11:30

一开始就觉得不可做,弃了,写了贪心。


题目解析

T1

将 n 个串中相同位置的 0/1 的数量记录下来。
贪心的找每一位数量较少的数字即可。


T2

二分最小的长度,DP 检查。
\(f_{i,j}\) 表示使用了 \(i\) 次红,\(j\) 次绿后,能覆盖到的最远的法坛的位置。
DP 方程:

\[f_{i,j} = \max(f_{i-1,j} + k, f_{i,j-1} + h) \]

\(k\) 表示从 \(f_{i-1,j}\) 开始,使用一次红光,能覆盖到的最远的右侧的法坛。
可以通过二分得到,\(h\) 同理。

最后检查能否覆盖到 \(n\) 即可,复杂度 \(O(n^2\log m)\)\(m\) 为答案最大值)。


T3

要求次短路,先求出最短路。
设到达节点 \(x\) 的最短路长为 \(s1\), 与结点 \(x\) 相连的最短边长度为 \(c\)
\(s2=s1+2\times c\)\(s2\) 即为次短路长度的上界。
DFS,搜索过程中利用 \(s2\) 进行剪枝,不断更新 \(s2\)
可以证明每个节点被到达不超过 \(n\) 次。


代码实现

T1 :

考场代码



T2:

考场代码


正解



T3:

考场代码

正解


2020.9.6 解题报告

标签:超过   考试   最小   mat   contain   节点   解题报告   block   max   

原文地址:https://www.cnblogs.com/luckyblock/p/13621784.html

版权声明:完美者 发表于 2020-09-17 16:22:57。
转载请注明:2020.9.6 解题报告 | 完美导航

暂无评论

暂无评论...