【题解】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-13Slicm 框架怎么进行用户认证?-icode9专业技术文章分享
- 2024-11-13在查询时将 map_coord 列的值转换为字符串有哪些方法?-icode9专业技术文章分享
- 2024-11-13如何将微信地区改成自定义文案?-icode9专业技术文章分享
- 2024-11-13DNS 缓存存在问题有哪些症状和解决方法?-icode9专业技术文章分享
- 2024-11-13HTTP 状态码(405)-Method Not Allowed是什么意思?-icode9专业技术文章分享
- 2024-11-13HTTP 状态码(500)-Internal Server Error是什么意思?-icode9专业技术文章分享
- 2024-11-13在 Element UI 中无法修改 $confirm 的取消按钮文字是什么原因?-icode9专业技术文章分享
- 2024-11-13unity XR是什么?-icode9专业技术文章分享
- 2024-11-13伴随矩阵是什么?-icode9专业技术文章分享
- 2024-11-13怎么使用grep -E 来查找匹配最后 2 条数据?-icode9专业技术文章分享