avatar
文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blogAtCoder Beginner Contest 320
搜索
主页
分类
标签
归档
友链

AtCoder Beginner Contest 320

发表于2024-10-24|更新于2025-08-05|ICPC
|浏览量:

title: AtCoder Beginner Contest 320
categories:

  • ICPC
    tags:
  • null
    abbrlink: 696c39ed
    date: 2024-10-24 00:00:00

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！
cover of previous post
上一篇
三分法
title: 三分法 categories: ICPC tags: null abbrlink: 7481085d date: 2024-10-22 00:00:00 三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。 三分整数模板 整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知 凹函数的极小值 int sfmin(){ int l=0,r=1e9; while(l+2<r){ //cerr<<l<<" "<<r<<endl; int m1=(r-l)/3+l; int...
cover of next post
下一篇
bellman-ford算法理解
title: bellman-ford算法理解 categories: ICPC tags: null abbrlink: 98c51b99 date: 2024-10-25 00:00:00 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不连通或者图中存在负环 ...
avatar
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
最新文章
贪心
贪心2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
Z函数与扩展KMP算法详解 - 以CF126B为例2024-12-21
Codeforces Round 895 (Div. 3)
Codeforces Round 895 (Div. 3)2024-12-16
可持久化字典树（Trie）
可持久化字典树（Trie）2024-12-16
网格图上问题
网格图上问题2024-12-15
©2022 - 2025 By WTY
框架 Hexo|主题 Butterfly
Copyright 爱飞鱼
搜索
数据加载中