牛客周赛 Round 10 解题报告

牛客周赛 Round 10 解题报告 在牛客博客上

https://blog.nowcoder.net/n/78952ae55788456aabe075d175377afe

A. 简单的滑窗

它本质是数组切分成块

枚举左端点，然后寻找最远的右端点

然后把新的左端点挪到上一个右端点+1

B. 有趣的DFS题

非常容易TLE，最好的方法是分组计数，然后dfs，这样天然去重

感觉这题还是卡 去重 的方式了

C. 数学题

典型的凸函数

有两种方式，一种是三分模板，另一个种是求导数

导数需要注意：t = (sqrt(xy) - v) / x, 有可能为负， 但是时间是非负数

因此最小的时间点 t = max( (sqrt(xy) - v) / x, 0)

D. 回文计数

分类讨论

• 同一个01序列中, 长度为len， len*(len+1)/2
• 中心扩展，两边延伸，则min(arr[i - j], arr[i + j])

n = 1000, 所以可以大胆的n^2