斜率优化 DP 笔记

心向星光，脚踩热浪，期末考试，顶峰相见！

引入 众所周知，在三个月前，我因为看到有很多人写的 CSP\mathtt{CSP}CSP 等考试的游记，就写了一篇期中考试游记（火了）。后来我又多次发布期末考试游记的预告。这次期末考试的游记，来啦！ 背景 众所不一定知，俺是一个初一的学生，在 2026 年 6 月 30 日和 7 月 1 日参加了为期两天的期末考试，本次考试为全区三十八校联考（较难），日程如下： 6 月 30 日 7 月 1 日 语文 数学 生物 政治 历史 英语 地理 暑假安全班会 再回顾一下历史战绩（呜呜期中考试生物考糊了） 为直观对比，分数全部都转化为 120 满分制，名次采用相反值 还行，其实能看，但主包作为班长+中队长（全级部 19 个班只有 6 个班长同时担任中队长，按理来说成绩应该更好），成绩在所有中队长里面比较靠下，还需要努力。 考前分析 第一场语文最好考好了，不然就会出现上次语文考太差影响政治的情况。英语排在最后其实对我不利因为前面考试对最后一场的心态影响极大。生物政治得好好考不然优势科目（英语&历史&地理）优势会减弱。All in all , 加油吧。 考前复习 着重复习的政治和生物，其他咋看。 考前状态 拉完了……感冒 + 有“点”哮喘 + 咳嗽 第一天 语文 8:00~10:00 哇塞🤩，监考老师这么良心 7:567:567:56 就发卷了，一共有 888 面。帅气聪明的我仅仅用了 111 分钟写完了基础选择👍（共 444 题），又用了 444 分钟写完了古诗默写（共 101010 空），距离正式开考仅过去了 111 分钟！ 到了第 7 题，我有点不会……它让选择错误的一项 but 我感觉都对了（但至少不是都错了），我就想起来了一个班梗：Zoe 问 Julian （通过真名发音让 AI 拟的化名）一个数学证明题，Julian 想都没想直接说：“选 C ”于是我决定第 7 题选 C 🤣 第 7 题一个小选择浪费了我 3 分钟但不要紧时间还有很多，接下来我有用了 444 分钟写完了第 8 题古诗赏析。但是，我没涂到答题卡上！我不知道还在继续做名著阅读的选择和赏析。本身名著阅读就比较难选择加赏析一共俩空浪费我 666 分钟，然后我不知怎地，居然把名著赏析写古诗赏析上了呜呜呜呜，写的满满当当，写完后才发现😭，痛失 333 分！ 我直接开狂暴，秒切文言文阅读，用 999 分钟做完俩文言文选择+文言文断句+俩文言文翻译，此时时间已经来到 8:238:238:23 ，我已经做完了 3.53.53.5 面局势一篇美好。⛰️ 文言文哲理题发现我没弄懂直接过，开始涂前面的卡，等涂完卡再写完这个哲理题发现 8:518:518:51 了瞬间老实了。 202020 分钟过后，我把第一篇现代文阅读《戈壁花开》做完了，写的满满当当的应该没问题✌️ 又用了 282828 分钟做完第二篇阅读，写的更🈵（bushi） 我差点没写完作文，感觉写的一般，描写比较少但生华直接对标梵蒂冈教宗发言稿，但不敢写为党和人民做贡献了因为上次这么写说是涉政扣了 101010 分呜呜呜…… 以上内容为 2026 年 7 月 2 日编写，编写进度不足 15% 居然上榜了 生物 10:20~11:20 监考老师依旧大发慈悲 10:1610:1610:16 就发卷了，时间一共有 121212 面。 然后 (Ta's Ma)'s 居然严禁我们作答，还说这是抢答。我没办法就等他们说完在看题的时候把答案记在脑子里一会儿写上去。 一打铃，我立刻把我做的四个选择题写了上去。第 555 题挺难的我看了好长时间，（转折点）结果突发恶疾，哮喘不断。我也不敢老咳出声音来（学校有规定考试如果突发哮喘多次持续发出噪音，考生一律到厕所，不得过多影响考试纪律，监考老师必须同意）就打报告去厕所了。然后就是一直咳嗽感觉都喘不上气了温馨提示：我还活着 回来一看 10:3510:3510:35 了，赶紧写，在 10:5810:5810:58 写完了选择题（一共 777 面仅耗时 171717 分钟） 31 题又是一个难题（大题），里面的一个小问有点猎奇： 移栽幼苗：移栽时要带土坨，目的是（保护幼根和根毛），尽量选择阴雨天或傍晚移栽成活率高，蕴含的生物学原理是（） 第二个空我懵了，我记得生物老师过我们什么只要看到...就写“功能与结构相适应”，可是这填进去对吗？！ 我选择相信自己，填进去了（bushi） 写完一看就剩 999 分钟收卷了，我直接炸了💥 （OS：到现在就算全对才 404040 分，更何况我前面半蒙半写） 最后 999 分钟我狂写 4 面大题，还剩一面，当场力竭…… 历史 正在写…… 结尾 未完待续……

13团暑期竞赛(有奖,邀请码:8554)

最新通知🔔： 已发现有 16\COLOR{RED}1616 个人使用 AI ， 13 个未承认， 3 个已承认，请这些人自觉找我私信承认就当只取消奖励，不告诉他人，否则这些人将拉入小黑屋 31 天、取消奖励并发帖公示！ 因为参加人数少，所以奖项 升级\COLOR{RED}升级升级！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 邀请码纯数字，好记！ 已报名 49\COLOR{GREEN}4949 人，参赛者 39\COLOR{LIME}3939 人。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 竞赛链接1(ACGO.CN)：13团暑期竞赛（邀请码：8554） 竞赛链接2(ACGO.XIAOMAWANG.COM)：13团暑期竞赛（邀请码：8554） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、竞赛说明 本次竞赛以国内十大热门暑期旅行城市为故事背景，试题由浅入深完整覆盖入门至 NOI 全梯度难度。 题目场景选用购物、景区游览、导航路线、自然景观规划等生活化趣味素材，避免枯燥纯数学模型，提升选手读题兴趣与建模代入感。 整套试卷分层考察：基础语法、数组模拟、前缀和、枚举计数、动态规划、搜索算法、字符串、数据结构优化 DP、高阶图论差分约束系统，全面检验选手代码实现、算法优化、复杂问题建模三大核心竞赛能力，为备战 CSP、省选、NOI 提供高质量专项训练素材。 二、竞赛规则 （老规矩！） 1.参赛选手需遵守竞赛纪律，禁止抄袭（AI也算）、作弊等行为（惩罚：拉入团队小黑屋3~31天、发帖警示并取消奖励）。 2.竞赛期间可使用编程语言：C++、PYTHON。 3.禁止与他人交流或使用非公开代码。 三、主办方（13个团） 由 ACGO之星、植物大战僵尸团、武汉大学、北京大学、华中科技大学、登山之旅、AC && C++语言 创码魔方、ACGO重点①大队、中国科技大学、凤凰织梦、MLE之团、CHINA编程组、星辰怪谈出版社 合作承办。 四、奖项设置\COLOR{RED}四、奖项设置四、奖项设置 (1)主要奖项： AK选手可自行选择 任意10个团队的一个月的管理员 或 3个团队的 永久管理员 或 2个空白团队。 除AK选手以外，第一的人选手可自行选择 任意5个团队的一个月的管理员 或者 自行选择 任意5个团队的一个周的管理员。 除AK选手以外，第二的人选手可自行选择 任意3个团队的一个月的管理员。 除AK选手以外，第三的人选手可自行选择 任意2个团队的一个月的管理员。 除AK选手以外，第四~第五的人选手可自行选择 任意1个团队的一个月的管理员。 (2)部分团队额外奖项： ACGO之星：只要答对8题及以上给永久管理员，5题及以上给一个月的管理员。 植物大战僵尸团：答对6题及以上给永久竞赛、题库管理员。 登山之旅：答对4题及以上给一个有限飞行器（团队虚拟）可飞 500M~2000M（随机） 。 凤凰织梦：AK 给一年管理员。 AC && C++语言 创码魔方：AK 给永久管理员。 > 获奖时间：9月1日00时00分00秒~10月8日00时00分00秒。 奖项可以攒着，前提跟码农爱历史说。 五、讨论规则 可以在 ACGO之星团队交流群 （QQ群号：1046185597）\COLOR{BLUE}（QQ群号：1046185597）（QQ群号：1046185597） 中问相关问题。 禁止说脏话、引战，说了的话拉入团队黑名单并一律删除评论。 （这次不加题目说明，不然没有神秘感 不然有人已经把题目猜出来了） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ACGO之星话题#1 依旧团贩子二人

依旧团贩子二人

1. 举报：ID:5005510 芜湖起飞 此人在短时间内将 160\COLOR{RED}160160 多人移出HΔCKΞRDΩMINIӨN团队 部分图片： 自己最后还退出了 更多资料： 关于黑客之都的这件事#官方发言 HΔCKΞRDΩMINIӨN团队出事了 实名举报——团贩子！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 举报：ID:5715499 超级大合莫 此人直接将我的合作团给全端了除队长 更多资料： 团炸了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以前的团贩子2人：团贩子2人(码农爱历史已经气炸了) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 请看完帖之后务必将 移出成员 和 管理角色权限给每个人去掉（如果还怕的话把删除题目、题单、竞赛、文件权限也去了）

绝版的东西别再上架了行吗？？？

求赞，让官方看见 事情是这样的，我最进看见有些东西是限量的，于是我就买了一些，结果，我发现过了几天以后那些绝版的东西有重新上架了，这真的很损罐头知道吗？写个限量，别人高高兴兴抢到，结果发现过几天又上架了岂不是瞬间“开心”了？希望官方不要骗人，说限量就限量，不要过几天又上架了可以吗？

天梯能力怎么弄到100%啊？

防透视 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 目标是CSP-J天梯能力怎么弄到100%啊？ 我天梯40层都到了 为什么只能48% 除非目标是GESP 一级： 好多人问为什么我要攒这么多罐头，因为在13团暑期竞赛(邀请码:8554,有奖)中AK奖是送空白团队，我怕送不起 更希望有人参加，目前只有49人报名😭 ACGO之星话题#1 依旧团贩子二人

和同学查成绩

本次考试除数学之外都很难啊 666同学红温乐 这个入还想向我炫耀 战绩 语文91.5 年级第二 数学100 英语92 666年级第8，英语太难了 科学95 好可惜

GESP 六级编程题题解

也许呢。 洛谷诚不欺我（提前交卷） T1 题目大意： 有一个长 nnn 的糕蛋（？），长度为 iii 的蛋糕块价值为 pip_ipi ，要求蛋糕长度均为整数，求分割成蛋糕块后所能得到的最大价值。 思路 完全背包板题，水完了。我在不会完全背包的情况下，在 01 背包基础上加了一层 111 到 nnn 的循环给我过了，？！强ccfcc强！？ 笑点解析：01 背包忘了然后翻选择题翻到代码了，应该不是作弊吧（ T2 题目大意： 你们 ccf 是没题出了吗，这题何意味。具体题目见P15801 [GESP202603 六级] 完全二叉树 ，其中把完全二叉树改为满二叉树。 思路： 树形 dp，显然当左右孩子均为满二叉树且他们的深度相同时，该子树为满二叉树。注意叶子节点也为满二叉树。

官方题解 | 欢乐赛#76题解

官方题解 | 欢乐赛#76题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的动物园门票 入门 T2 皓仔的动物园参观 入门 T3 皓仔统一大小写 入门 T4 皓仔的森林施法 入门 T5 皓仔的进制求和 普及- T6 皓仔的三段数组 普及- T1 皓仔的动物园门票 题意简述 给定总票价 w 和参加活动的人数 n。 要求计算平均每张动物园门票的价格，并保留 222 位小数输出。 也就是计算： w÷nw \div n w÷n 解题思路 这是一道简单的实数除法题。 因为总票价 w 可能是实数，所以需要使用 double 类型存储。 读入 w 和 n 后，直接计算 w / n，再使用 printf("%.2f", ...) 输出保留 222 位小数即可。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T2 皓仔的动物园参观 题意简述 给定皓仔到达动物园的时间 t。 根据不同时间段输出能看到的动物： * 8≤t<108 \le t < 108≤t<10，输出 熊猫 * 10≤t<1210 \le t < 1210≤t<12，输出 猴子 * 12≤t<1512 \le t < 1512≤t<15，输出 大象 * 15≤t<1815 \le t < 1815≤t<18，输出 老虎 如果不在这些时间段内，输出 动物园已关闭。 解题思路 这是一道简单的条件判断题。 因为每个时间段都是左闭右开，所以判断时需要注意右端点不能取到。 按照题目给出的时间段依次使用 if else 判断即可。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T3 皓仔的统一大小写 题意简述 给定一个只包含英文字母的字符串 s。 每次可以修改一个字符，目标是让字符串变成以下两种情况之一： 所有字母都是大写字母； 所有字母都是小写字母。 输出最少需要修改的字符数量。 解题思路 统计字符串中大写字母的数量 cnt1，以及小写字母的数量 cnt2。 如果要全部变成大写字母，就需要修改所有小写字母，次数为 cnt2。 如果要全部变成小写字母，就需要修改所有大写字母，次数为 cnt1。 答案就是两者的较小值。 时间复杂度为 O(∣s∣)O(|s|)O(∣s∣)。 参考代码 T4 皓仔的森林施法 题意简述 有一个 n×nn \times nn×n 的森林，最开始每棵树高度都是 000。 接下来有 mmm 次施法，每次给出 a、b、x，表示第 a 行第 b 列的树长高 xxx 米。 同一棵树可能被多次施法，高度会累加。 最后输出最高的树所在的位置，题目保证最终最高的树唯一。 解题思路 用二维数组 h 记录每棵树当前的高度。 每次读入一次施法操作后，执行： 然后判断这棵树的高度是否超过当前记录的最大高度。 如果超过，就更新最高树的位置。 由于 xxx 最大可以到 10910^9109，并且同一棵树可能多次累加，所以高度要使用 long long 存储。 时间复杂度为 O(m)O(m)O(m)。 参考代码 T5 皓仔的进制求和 题意简述 给定 nnn 个数字，每个数字由字符串 s 和进制 b 表示。 需要把每个数字从 b 进制转换成十进制，然后求出所有数字的总和。 数字中可能出现： 0 到 9 表示 000 到 999； A 到 F 表示 101010 到 151515。 解题思路 对于每个字符串 s，从左到右依次处理每一位。 假设当前已经转换出的十进制值为 num，当前字符对应的数值为 x，那么更新方式为： num=num×b+xnum=num\times b+x num=num×b+x 这样就可以将整个 b 进制数字转换为十进制。 由于答案最大不超过 101810^{18}1018，所以总和以及每个转换后的数字都要使用 long long 存储。 时间复杂度为 O(n×∣s∣)O(n\times |s|)O(n×∣s∣)。 参考代码 T6 皓仔的三段数组 题意简述 给定一个长度为 nnn 的正整数数组。 现在需要选择两个分割位置，把数组分成连续的三段，并且每一段都不能为空。 对于每一种分法，分别计算三段元素和 s1、s2、s3。 要求最小化： max⁡(s1,s2,s3)−min⁡(s1,s2,s3)\max(s1,s2,s3)-\min(s1,s2,s3) max(s1,s2,s3)−min(s1,s2,s3) 输出这个最小值。 解题思路 因为 n≤500n \le 500n≤500，可以直接枚举两个分割位置。 设第一个分割位置为 i，第二个分割位置为 j，那么三段分别是： 第 111 段：111 到 i 第 222 段：i + 1 到 j 第 333 段：j + 1 到 n 为了快速求每一段的和，可以先预处理前缀和数组 s。 这样每一段的和都可以 O(1)O(1)O(1) 求出。 最后枚举所有合法分法，更新答案即可。 时间复杂度为 O(n2)O(n^2)O(n2)。 参考代码

如何获得时空双修

在此帖内请勿刷罐,否则一律拉黑\COLOR{RED}{在此帖内请勿刷罐,否则一律拉黑}在此帖内请勿刷罐,否则一律拉黑 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 由于帖主退站闲的没事干于是就突发恶(奇)疾(想)来写一篇100%获得时空双修的方法造福人类 本篇文章主要分为3个部分介绍,分别是正常思路与离谱的思路 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、减少时间复杂度与空间复杂度 获得时空双修的方法是一道题中时间复杂度和空间复杂度优化超过99%的用户 所以在写完代码后可以先计算出时间复杂度与空间复杂度,再不断修改代码优化 可以看看这个帖子,时间复杂度越简单越好;空间复杂度同理,这个帖子参考 二、找到没有人通过的题目并AC 现在ACGO题库里有好多0通过的题目,如果有编程能力强的可以去试一下 为什么需要编程能力强的？因为要是这题目简单就不会0通过了啊！(别问我怎么知道的,去年11月对着一道0通过的题目死磕,做了两个小时后来崩溃了) 三、做刚创作的题目 这个思路就有点投机取巧了,不过整体思路与第二大思路相似,都是完成没有人做过的题目 如果你在比赛过后提交就100%获得时空双修,因为比赛过后上传的题目提交量会很少,此时你提交就会超越其他用户,就肯定能拿时空双修了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 创作不易,感谢大家的关注与点赞

ACGO之星话题#1

7月ACGO之星团队话题#1:你们班的"老规矩"是什么？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我先来： 语文老师轻顿笔尖，淡淡开口：“我方才觉察，尚有一件紧要事宜未能记起。” 29 号同学立刻扬声，熟稔笑道：“老规矩！” 老师恍然颔首，眉眼带笑：“哦，原来是抽背环节，我竟险些忘了。今日公历六月八日，恰逢周一，便取六乘八加一，点四十九号同学作答。” 我（49 号）心头一沉，万般无奈，只得低头叽里呱啦将课文通篇背诵完毕。 老师抬眸瞧出我满心不情愿，话音一转：“下一位并非四十九加十的五十九号，咱们换个算法，今日农历廿三，二十三加六，就点二十九号。” 29 号同学当场垮下脸，哀嚎一声：“啊呀～！” （100%有人不信日期刚刚好匹配的上去看日历了，甚至有人不知道，“廿”是20的意思） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点赞前2（要与话题有关）团队管理员一周体验卡（如果一个人的总点赞量超过50直接安排永久管理员）。 你们的呢？ （不要说话时小学生味满满） 13团暑期竞赛（邀请码：8554）