【题解】Codeforces Round #772 (Div. 2)
2022/2/21 23:44:36
本文主要是介绍【题解】Codeforces Round #772 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
vp→rk205,剩一个小时给E结果理解错题了,吃个饭回来发现题看错了然后就会了(
E
图论题
F
x 数组升序;查询区间 \([l, r]\) 内 \(|x_i−x_j|⋅(w_i+w_j)\) 的最小值
感觉比较合理的思路应该是:先考虑对整个区间的查询 → 考虑贪心推一下性质 → 假设(i,j)是答案,通过微调观察对答案的影响 → 得到答案的形式/特征( → 待选的答案可能有限,就可以从此下手)
假设 (i, j) 是答案,显然 (i, j) 之间的所有 w 都应该大于 w[i] 和 w[j],所以这就是答案的形式
转化一下,对每个端点 i,其和左边第一个w小等于其的位置构成一个可能的答案,和右边第一个w小等于的也构成一个,所以最多有 2n 个待选的答案数对,用个栈就能处理
回到区间查询,可能的答案依然满足上述的形式,想想会知道依然是从那 2n 个数对里选而且肯定有解
既然待选的答案有限,那么只需重新考虑这些待选的答案
那么问题就变成:询问属于 [l, r] 的带权区间中的最小权值是多少
离线+线段树就行了
另外注意一下题目问的是最小还是最大值,别想着想着就想反了
这篇关于【题解】Codeforces Round #772 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-25【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享