文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blog
AtCoder Beginner Contest 320
搜索
主页
分类
标签
归档
友链
AtCoder Beginner Contest 320
发表于
2024-10-24
|
更新于
2025-12-13
|
ICPC
|
浏览量:
AtCoder Beginner Contest 320
https://atcoder.jp/contests/arc106/tasks/arc106_e
文章作者:
WTY
文章链接:
https://my-mathmaster-github-io.vercel.app/posts/696c39ed.html
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
爱飞鱼的blog
！
上一篇
三分法
三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。 三分整数模板 整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知 凹函数的极小值 123456789101112131415int sfmin(){ int l=0,r=1e9; while(l+2<r){ //cerr<<l<<" "<<r<<endl; int m1=(r-l)/3+l; int m2=r-(r-l)/3; if(cal(m1)>cal(m2))l=m1; else r=m2; } int ans=cal(l); for(int...
下一篇
bellman-ford算法理解
bellman-ford算法理解 从本题谈起再回归到最短路。本题为限制边数的最短路，是这个算法优势领域的题目。为什么它能解决？ 最外层每循坏一次，就是各点向外走一条边，内层对边的遍历是对所有边进行松弛操作，每次进行该操作时，需要用到备份数组，目的是防止连锁反应，保证每次每个点到起点的距离只能因为上一轮的更新而更新。 若只是求最短路，则外层循坏n-1次。为什么是n-1？ 假如最短路存在，认为没有负环 从上面算法理解可以知道，外层n-1次相当于起点已经走过了n-1条边（bfs到n-1层） 那么从最坏情况考虑，由于已经假设最短路存在，那么其长度应该<=n-1. 假如最短路不存在 而如果n-1条边还没有更新到d[n]，即没有找到一条长度<=n-1的路径从1能到n，说明n可能和1不连通或者图中存在负环 ...
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
最新文章
贪心
2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
2024-12-21
Codeforces Round 895 (Div. 3)
2024-12-16
可持久化字典树（Trie）
2024-12-16
网格图上问题
2024-12-15
搜索
数据加载中
