牛客周赛 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
中科院自动化所一面3人在聊
投递美团等公司9个岗位