背包DP(一)

关于AC君的年龄

黑哥又来了~ 大家觉得AC君几岁了捏喵？ 在评论区打出来叭~ @AC君如果你觉得这没有侵犯你的隐私，欢迎公布答案喵~ 评论区点赞最多的人可获得作者送的团队一个~ 截止时间：10月15日 12:00 以下是作者的辉煌战绩： （给点不要钱的点赞、评论、关注呗喵~）

关于某些发了n遍退站帖但是吊着不死的人

对于我反复发送此帖的行为感到抱歉，反复发送是因为之前帖子被NULL覆盖毫无秩序的样子令人心生厌恶，忍不住反复修改更新，至此， 该贴修改完毕 此帖结2026−10−05−11:15此帖结2026-10-05-11:15此帖结2026−10−05−11:15 以下内容均根据按回忆重写QWQ 你永远不能低估acgo沙子的数量你永远不能低估acgo沙子的数量你永远不能低估acgo沙子的数量 所以呢，是你狗环境太好，令你恋恋不舍;还是网友太笨，让你忍不住慢慢戏耍呢，我们无从知晓，但是，据我所知，此人已有先例 > 请输入文本，谨防对号入座.... *注:滚木滚木滚木滚木滚木 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感觉呢，这种人的退站，就像商场门口挂的“清仓甩卖”的横幅挂了一年，货架却越清越满。 第一次发退站帖，别人还递上纸巾，满是不舍。第二次发，大家还问一句“出什么事了”；第三次发，评论区基本已经修炼成老观众了：有人搬好椅子，有人递上瓜子，有人提前鼓掌，有人问“下次是哪天”，甚至有人能把他的退场词背下来。 真正想走的人，关门声很轻；天天喊走的人，嗓门很大，恨不得全站都知道他退站的消息。说到底，他离不开的并不是那些恋恋不舍的网友。他真正贪恋的，是聚光灯打下来的那束目光。。。未完待续还不如直接发《我不退站了🤡》呢，至少标题和事实握手言和了。。 等到哪天没人理他的退站帖了，他才会发现，自己早就不是舍不得你们，是舍不得那个每次告别都能涨粉的自己。所以，别再搞什么“假死”了，天天“狼来了”，狼都嫌你通告太烦 *以上内容使用Chat PPT润色--特别鸣谢:工具大全 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 矛盾的来了，我之前说过 > 谨防对号入座 但是，还是请你们自觉的对号入座吧，也许你们自以为很高明，但是，在一些人看来，你们的行为幼稚得可笑 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ nul 写了好久的帖子被null覆盖了，为acgo点赞 由于刚入站，先前并不知道null会吃帖子，希望有方法可以找回，求求求

举报

@wcqk @日历午后‮ 该用户在私信中多次对我进行恶意辱骂和人身攻击，反复发送“你个**，全家都死了”“*****”“你家里空空的”“你全家都si了”等极端侮辱性及诅咒家属的言论，并发送垃圾字符刷屏、挑衅“有本事来踢我呀”，还在聊天列表备注/预览显示“你全家死光”。其行为严重违反社区文明交流规范，构成骚扰辱骂与网络暴力，影响恶劣。请台核实聊平天记录（截图已保留），对该账号“日历午后”予以处理（禁言/封禁/限制私信等），谢谢。 @AC君

最浪漫的一集

我跟你们这些人拼了

谁能告诉我天之神为什么这么多人退了？

谁能告诉我天之神为什么这么多人退了？！！！

给你两千小时，学文化课还是学 OI？

为什么在学校一直上课、一直刷题一点用处都没有？ > 很多人都觉得自己在学校刷题、学文化课有多厉害，甚至带着一股优越感，就开始在那猛刷题、报课外班。但你想想，在这学文化课到底有什么用？ > 很多人甚至开始在这里提前学，觉得小学会初中数学就很成功了。说实话，初中数学一点用处都没有，哪家公司是用一元二次函数搞开发的？当然，我们数学课很多压轴题不是一元二次函数，而是几何和三角函数。 那为什么我说 WHK 也没用，学校是个没用的机构？首先来看看在学校上课的人到底是为了干啥： 如果你学 whk 是为了以后搞开发、创业，或者进谷歌、苹果这些大公司，甚至是单纯为了提升自己未来的能力，那学这些逻辑可能只有一点点用。不过，与其刷应试教育，它的用处难道还比得上你学用 AI 或其他实用信息学技能吗？我觉得更重要的反而是去学会信息学奥赛。现在的 AI 能干的事情比书呆子多得多，你在这里单纯学习又有什么用？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 很多人可能会觉得学这个是为了升学 觉得万一考个仲元广雅就能送进清华北大，或者高考提升很多分。但你想靠这个提分，先看看自己投入了多少成本： * 在学校几年杂项器材花了多少钱？ 刷题、学答题技巧、考学校测试花了多少时间，费了多少心思和精力？ 而且这种路线的反脆弱性极差。 万一来个黑天鹅事件，高考一旦滑档，这些年的努力不就全白费了？我不是说滑档的概率很大，可一旦发生，所有付出就直接打了水漂。这就像把全副身家都押在一件事上，哪怕成功率再高，只要有微小的失败概率，后果就很惨。更何况你还没精力去干别的事情。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 退一步说，就算分数不变，考进 211 甚至进入清华北大，难度有多大？能有几个人真正走通这条路？更何况，你就算去了清华北大，那你出来的时候也要干事吧？你去了清华北大，如果你不学东西，你就会 whk，那也一样没人要你 真不如现在去学学 OI，学学信息学，这些东西远比一直刷 WHK 有用得多。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 更扎心的一点是，很多在学校猛学习的同学，别自己骗自己了。你们天天坐在桌子前跟家长说：“妈，我在学校天天上课呢，我在为名校努力，别打扰我！” 家长一看满纸看不懂的题目，还觉得这孩子真懂事、真高级。其实呢？你们心里最清楚：每日上课只是你们逃避生活社交劳动、逃避自我锻炼、光明正大摸鱼混饭的最高级借口。 遇到不会的题，直接把技巧背下来，或者让别人啪啪一教，提交上去看个高分的数字，就觉得自己是个学霸巨星了。这种虚假努力换来的多巴胺，和打赛马娘不充钱、不会非传统进了弱省省队迎战 NOI 有什么本质区别？ 很多人觉得去大厂要有成绩，所以从小学各种拓展培优。醒醒吧！现在是 2026 年了。 大厂现在面试看的是什么？是你的开源项目经验、你用 AI 搭建自动化系统的能力、你解决实际业务高并发的能力。 > 你面试的时候跟面试官说：“我 12 岁就能全级第一！哈哈哈！你要不要，不要别的地方一大堆要的。”（这样大概他会把你赶出去）你要是跟他说你会数理化，面试官只会问你：“哦，那你会设计这个零件吗？你懂不懂迭代学习？你能不能给我们带来新的创意？” 如果你都不会，你只是一台比 DeepSeek 和 GPT 慢了一万倍的低配中文房间自动机。在真正的工业级开发面前，只会刷考试题的人连拧螺丝的资格都没有。 或者，你觉得自己挺牛，觉得自己可以，那就来晒晒自己的成果？ 实在不行，你在评论区晒晒自己的作品？你注册了什么 OJ，拿到什么排名？你有多有能耐，打了 wc、打了 apio、会真正提出一种启发式的方法？来，甩出你的 OIerDB 链接，或者甩出你其他竞赛的硬实力。让我看看你除了跟死板的题目对脑回路，还会不会做一点学历没你高的人会做的东西？ 你别看着这么多进国企、先进科技型企业的大佬，你觉得大佬多吗？还是这些企业招人招这么多？让你觉得全是铁饭碗，很简单。别被洗脑了。 如果你什么都拿不出来，却还在天天跟着别人瞎卷、自我感动、做着当做题家就能保送清华北大的春梦。那你不是牛娃，你只是教育系统选择和资本镰刀下，一个可怜的智者。 别自我感动了，多看看真实的科技世界吧！

神秘线上课

陈贝豪，冯辰晔和徐溶 最下面有惊喜

一场跨越浙江和新疆的千里之约

山海万里相连，文脉双向共生。这是一场跨越四千公里的东西对话，也是浙江与新疆携手联动的合作出版共创项目。两地以影像为媒、以文字为介，融合江南风雅与西域壮阔，共同编撰专属两地的图文合集，让相隔千里的山河人文，在一纸书卷中温柔相逢。 前四帧画面，留给温润江南浙江。青山绕碧水，江海纳流云，浙江的山水自带温婉清雅的气韵。烟雨浸润千年文脉，街巷沉淀人间烟火，兼具秀丽自然风光与深厚人文底蕴。细腻的山河肌理、悠远的书香底蕴，勾勒出独属于江南的温柔风骨，为本次联合出版注入细腻、灵动、温润的东方诗意。 后四帧光景，赠予辽阔西域新疆。雪山耸云端，旷野接星河，新疆的大地尽是磅礴坦荡的风光。无垠草原、澄澈湖泊、巍峨雪山串联成壮阔画卷，天地辽阔、风物纯粹，自带自由洒脱的塞外气质。雄浑壮丽的山河风光、淳朴厚重的西域人文，为作品集赋予了大气、恢弘、开阔的山河格局。 一半江南温婉，一半西域辽阔。浙江的细腻文脉碰撞新疆的壮阔山河，千里相隔，却岁岁相依。本次浙疆合作出版，不仅是一次图文作品的联合创作，更是两地文化的交融、山海风光的双向奔赴。以书为契，赴千里之约，让南北山河之美、两地人文之韵被长久珍藏。 联合出品署名和版权必究他的帖 @懒大王（互关） 必须火！

【投票】给你两千小时，刷OI还是做项目？

> 如果给你两千小时，你选： > > 1. 刷OI，刷题，刷2000h题。 > 2. 学习ai自动化，争取1周可以做出一个项目，进行真实项目AI实操 请在评论区说出你的观点...... ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 附属贴 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 为什么在 ACGO 上一直刷 OJ、一直刷题一点用处都没有？ > 很多人都觉得自己在 ACGO 上刷题、学编程有多厉害，甚至带着一股优越感，就开始在那猛刷题、学 OJ。但你想想，在这学 OJ 到底有什么用？ > 很多人甚至开始在这里学 SCRATCH，觉得用 SCRATCH 做个东西就很成功了。说实话，SCRATCH 一点用处都没有，哪家公司是用 SCRATCH 搞开发的？当然，我们这里很多人不用 SCRATCH，用的是 C++。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 那为什么我说 OJ 也没用，ACGO 是个没用的社区？首先来看看在 OJ 刷题的人到底是为了干啥： 如果你学编程是为了以后搞开发、创业，或者进谷歌、苹果这些大公司，甚至是单纯为了提升自己未来的能力，那学这些逻辑可能只有一点点用。不过，与其刷算法，它的用处难道还比得上你学 HTML 或其他实用语言吗？我觉得更重要的反而是去学会 Vibe coding。现在的 AI 能干的事情比人多得多，你在这里单纯刷题又有什么用？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 很多人可能会觉得学这个是为了升学 觉得万一考个 CSP-J / CSP-S 就能保送清华北大，或者降很多分。但你想靠这个降分，先看看自己投入了多少成本： * 上小码王的课花了多少钱？ * 刷题、学算法、打竞赛花了多少时间，费了多少心思和精力？ 而且这种路线的反脆弱性极差。 万一来个黑天鹅事件，政策一旦变了，这些年的努力不就全白费了？我不是说政策改变的概率很大，可一旦发生，所有付出就直接打了水漂。这就像把全副身家都押在一件事上，哪怕成功率再高，只要有微小的失败概率，后果就很惨。更何况你还没精力去干别的事情。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 退一步说，就算政策不变，靠竞赛降分甚至保送清华北大，难度有多大？能有几个人真正走通这条路？更何况，你就算去了清华北大，那你出来的时候也要干事吧？你去了清华北大，如果你不学东西，你就会 OJ，那也一样没人要你 真不如现在去学学 AI，学学 AI 自动化，这些东西远比一直刷 OJ 有用得多。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 更扎心的一点是，很多在 ACGO 上猛刷题的同学，别自己骗自己了。你们天天坐在电脑前跟家长说：“妈，我在 ACGO 上刷 C++ 算法题呢，我在为国家集训队努力，别打扰我！” 家长一看满屏幕看不懂的代码，还觉得这孩子真懂事、真高级。其实呢？你们心里最清楚：刷 OJ 只是你们逃避学校作业、逃避背英语单词、光明正大摸电脑的最高级借口。 遇到不会的题，直接在评论区复制一份代码，或者让 AI 啪啪一敲，提交上去看个"AC"的绿色标志，就觉得自己是个科技巨星了。这种虚假努力换来的多巴胺，和打王者荣耀、刷短视频有什么本质区别？ 很多人觉得去大厂要考算法，所以从小刷 OJ。醒醒吧！现在是 2026 年了。 大厂现在面试看的是什么？是你的开源项目经验、你用 AI 搭建自动化系统的能力、你解决实际业务高并发的能力。 > 你面试的时候跟面试官说：“我 12 岁就能手写线段树！哈哈哈！你要不要，不要别的地方一大堆要的。”（这样大概他会把你赶出去）你要是跟他说你会C++，面试官只会问你：“哦，那你用 C++ 独立开发过高并发的 Web 服务器吗？你懂不懂 Docker 容器化？你会不会用大模型 API 做 Agent 自动化流程？” 如果你都不会，你只是一台比 DeepSeek 和 GPT 慢了一万倍的低配计算器。在真正的工业级开发面前，只会刷 OJ 题的人连拧螺丝的资格都没有。 或者，你觉得自己挺牛，觉得自己可以，那就来晒晒自己的成果？ 实在不行，你在评论区晒晒自己的作品？你上线了什么网站，带来多少收入？你有多有能耐，会 ai 自动化、会高并发、会真正让项目变现？来，甩出你的 GitHub 链接，或者甩出你独立开发的 App 上线地址。让我看看你除了给死板的OJ交代码，还会不会做一点能让普通人用的东西？ 你别看着这么多ACGO上的大佬，你觉得大佬多吗？还是火的帖子都是大佬发的？让你觉得全是大佬，很简单。别被洗脑了。 如果你什么都拿不出来，却还在天天跟着别人瞎卷、自我感动、做着考级就能保送清华北大的春梦。那你不是牛娃，你只是资本和流量镰刀下，一个可怜的智者。 别自我感动了，多看看真实的科技世界吧！ > 感谢大家支持！🙏我们的帖子位列榜首，希望大家多多评论，多多引流，帮助更多的人！也支持大家和我私信获得最新AI资讯学习如何VIBE CODE！假期时间有限，仅限 10 位，先到先得！👇 > 同时希望大家顶一下这个帖子，有关ACGO加入帖子推荐算法：HTTPS://WWW.ACGO.CN/DISCUSS/DEPOT/92440

CSP J 复赛游记

这个区忘了 ST 表，导致 S 初赛被周飞，所以只有 J 打了。 标题何意味. 由于和上一篇训练目的不同，所以单开。 9.24 拜谢 FM 大佬，开始刷题单棍母和棍母 P7909 时候不早了，随便挑个橙玩玩。 因为要找到最大的 kmod  nk \mod nkmodn，如果 l,rl,rl,r 除以 nnn 的商下取整相等，则在满足 L≤k≤RL \le k \le RL≤k≤R 的情况下 kkk 越大越好，于是我们取 k=Rk=Rk=R。否则，kmod  nk \mod nkmodn 最大值明显为 n−1n-1n−1，直接输出 n−1n-1n−1 即可。 代码 复杂度分析 略 9.25 中秋快乐各位。 13 天假期必须好好补一补 whk 了，也（打算）报了洛谷的课程。但先玩几天（ 在酒店看一会 J/S 的题目讲解 9.26 是谁写了一沙滩的毕导。 晚上帮 cchu 调代码，顺便讲一下吧。题目是今晚 ABC 的 D。 这种类型的题目 ABC 似乎出烂了，AtCoder 你只是怕了。 显然 lazy tag 优化，直接线性创飞了。 然后你会收到 AC18，WA13 的好成绩。 下面给一组 hack： 相信大家都知道错在哪了，如果直接去判断当前格子的染色状态会很麻烦，复杂度也会炸。也就是说正着维护很难。 触发关键词了。 没错，正难则反。我们反着去处理查询，每次只要找到这个格子最后一次的有效染色即可。 代码 略 复杂度分析 略 9.28 florr 玩破防了，老实滚回来写题。 P1182 唔，一个简单的二分答案，所以我们确定三个点： 1. check 函数 2. 二分边界 3. 二分内容 二分内容不难想，题目要求我们求最小最大值，所以我们二分这个值。边界也比较简单，显然当我分为 n−1n-1n−1 段时答案最小，为 max⁡(a1,...,an)\max(a_1,...,a_n)max(a1 ,...,an )；不分段时最大，为 ∑i=1nai\sum_{i=1}^{n} a_i∑i=1n ai ，那么边界就没问题了。 来看 check 函数。我们要在保证答案为 midmidmid 的情况下，所分段数不超过 mmm。考虑 O(n)\mathcal{O}(n)O(n) 求分段数，若当前这一段大小超过 midmidmid，则划分新的一段。由于我们需要 O(1)\mathcal{O}(1)O(1) 维护静态区间和，所以使用前缀和数组。 那就做完了。 代码： 复杂度分析 比较简单的分析，二分复杂度 O(log⁡k)\mathcal{O}(\log k)O(logk)，check 函数复杂度 O(n)\mathcal{O}(n)O(n)，总复杂度 O(nlog⁡k)\mathcal{O}(n \log k)O(nlogk)。其中 kkk 为 ∑i=1nai−max⁡(a1,...,an)\sum_{i=1}^{n} a_i -\max(a_1,...,a_n)∑i=1n ai −max(a1 ,...,an )。 P14247 好神奇的题。 乍一看感觉条件三很难，尝试找规律。 看了一眼样例，没有给我们不合法的情况，猜测都是可以的。 从 n=2n=2n=2 开始看，发现随便填都符合条件，当时推到这就开智了。 显然我们构造的这个矩阵中只要包含一个 2×22\times 22×2 的由 1,2,3,41,2,3,41,2,3,4 组成的子矩阵即可满足条件三。 发现条件 333 要满足“恰有”，看看怎么放可以不出现第二个如上的子矩阵。我们假设 n=3n=3n=3，在上述条件下，我们可以在右侧与下侧全部填 555，右下角填 666，构造出来的矩阵是这样的： 那怎么往下扩展呢，看看 n=4n=4n=4 的情况，按照上述方法构造，矩阵如下： 发现，若 (n−1)×(n−1)(n-1) \times (n-1)(n−1)×(n−1) 是一个合法的构造，考虑在其右，下侧最后一列（排）放入 2x−12x-12x−1，最右下角放 2x2x2x。不管怎么圈，除了最左上角的子矩阵外，总是有且只有两个数重复。这样就满足了“恰有”这个条件，进而满足了所有条件。 代码 略 复杂度分析 显然为 O(n2)\mathcal{O}(n^2)O(n2) 10.1 P17288 高速上写的，脑子不清醒写了个石山。 直接模拟即可，思路不讲诗人都会吧。 代码 复杂度 O(max⁡(∣a∣,∣n∣))\mathcal{O}(\max(|a|,|n|))O(max(∣a∣,∣n∣))，证明略 10.5 P10722 看看怎么维护一个节点的翻转次数。 思考一下节点翻转的情况。思考发现这个节点的实际翻转数等于他父节点的翻转数加上他本身的翻转数。我们发现需要维护父节点翻转数。 令当前节点为 xxx，fa(x)fa(x)fa(x) 与 f(x)f(x)f(x) 分别为求父节点与求自身翻转次数。则当前节点翻转次数为 f(x)+f(fa(x))f(x)+f(fa(x))f(x)+f(fa(x))。对于 fa(x)fa(x)fa(x)，其翻转次数为 f(fa(x))+f(fa(fa(x)))f(fa(x))+f(fa(fa(x)))f(fa(x))+f(fa(fa(x)))。以此类推。我们发现需要从根节点向下一步一步维护翻转次数，考虑 dfs。 用三个数组 dp,func,fadp,func,fadp,func,fa 维护。funcfuncfunc 为当前节点作为根节点的翻转次数。则每次搜索转移为 dpi=funci+dpfaidp_i=func_i+dp_{fa_i}dpi =funci +dpfai 。那就做完了。 代码 略 时间复杂度 O(n)\mathcal{O}(n)O(n)，证明略