题目不严谨，商不单是结果的整数部分

互动#25｜#1024吐槽节

💥 #1024吐槽节# 盛大开幕！ 嘿，AC狗友们！🧑‍💻 又到了一年一度，咱们程序员的专属节日——1024！ （没错，ACGO也有自己的小传统了，仪式感拉满 😎） 所以，我们决定如期举办那个 “让人又爱又恨” 的活动—— #1024吐槽节# 今年的规则，简单到令人发指： > 看ACGO哪里不顺眼？大胆开麦！ 是题库太阴间？测评机日常抽风？ 还是社区功能用起来像在考古？ 或者，你单纯想对我们AC君喊一句： “你们这个功能是祖传的吗？能不能动一动！” 没问题！今天你说了算！🫡 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 来来来，指条明路（欢迎自由发挥）： * 「功能篇」：题库、测评机、排行榜、编辑器… 哪个让你血压飙升？ * 「社区篇」：氛围、活动、推荐机制… 哪里让你想“原地退站”？ * 「运营篇」：希望我们多整活？多发福利？还是… 少整点烂活？🤣 一句话：今天我们不开夸夸团，专心 “Debug ACGO”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 参与姿势： 1️⃣ 带话题 #1024吐槽节# 发帖或直接评论本帖 2️⃣ 尽情输出你的“血泪体验” + 你心目中的完美改进方案 3️⃣ 支持各种形式：小作文、段子、表情包、灵魂拷问… 越真实，越有力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 而我们，郑重承诺： * 所有高赞、走心的吐槽，我们保证逐字阅读，跪着回复！ * 那些闪闪发光的金点子，将直接进入 「ACGO优化清单」 （是真的会排期的那种！） * 被我们“盯上”的优秀吐槽官，还会收获一份 “忍住别哭” 的小惊喜 🎁 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 活动礼品： 高赞奖：点赞最高的前三位，送上ACGO钥匙扣盲盒 金点子奖 ：我们将选2-5名，送上AK吧唧 优秀吐槽官奖 ：我们将选选2-5名，送上ACGO周边定制笔 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🗓 活动时间：10月14日 至 10月26日 💬 活动主旨：吐槽是门手艺，进步需要勇气。 毕竟—— ACGO的bug或许会迟到，但我们想修好它的心，永不缺席！ 🛠️ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

#创作计划#学术计划VOL.2 双指针！

双指针！ 前言： > 这是Stars_Seeker推出的学术计划系列的第二期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句作者语文不好（，只有透彻又不完全透彻的知识awa。 > 写的这么差的帖子肯定是AI（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 双指针是什么 双指针可以看做对于枚举的一种优化。 对于两个指针如果分别从 1 到 n 枚举，那么两重循环嵌套，复杂度是 O(n^2), 但在一些具有单调性的题目中，可以使 i 指针和 j 指针都只需要从 1 到 n 遍历一次，复杂度分别为 O(n) , 总复杂度也是 O(n) 。 例题 1: P1147 连续自然数和 思路：构建前缀和数组，由于数字都大于 0，那么前缀和数组存在单调性，可以考虑双指针 i 指针移动时候，为了使得区间和仍然接近 n，j 指针只会向右移动，因此 i 指针和 j 指针都只需要从 1 到 n 遍历一次， 复杂度分别为 O(n) , 总复杂度也是 O(n) 。 代码实现 例题 2: P1102 A-B 数对 思路： 先排序使得数组存在单调性， 然后 i 指针从 1 到 n 扫一遍，复杂度为 O(n) , 每次找到符合条件的最大的 j ，将对应的数量加入答案，为了了解当前的 j 是同类数字里出现的第几个数字，可以另外开一个 cnt 数组来记录。为了保持 j 指针尽量大并且满足 a[i] - a[j] >= c ，当 i 指针向右移动时候, j 指针只会不变或者向右移动，那么 j 指针的总移动次数也是 O(n) 。 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 是的没错，你没有听错，第二期结束了！ 比第一期稍微长了一点，因为加了2道例题。以后字数不够的时候凑字数就这么写 ））） 本篇文章中“代码的注释”部分内容是作者它询问了它的教练，所以会看起来很权威。 如果文章中出现质量问题或者还有其他思路,欢迎在评论区讨论 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ <-上一篇学术计划

非常猎奇的名字评价N2：kkksc03

破10更新 破30更新远征 1. 风格与感觉：极客/宅文化风 这个名字带有浓厚的 “屏幕另一侧”的真实感。它不像“北大西洋公约”那样宏大和概念化，而是非常个人化，更像是某个特定用户在某个时期根据自己的喜好创造的ID。 非正式与亲和力：这个名字没有官方或商业气息，显得很随意，容易拉近与其他社区成员的距离。 匿名性与个人标识：它不直接暴露用户的真实姓名或身份，符合网络社区的常态，同时又通过独特的字符组合形成了个人标识。 2. 结构与可能的含义 这个名字可以拆解为两部分，我们可以做一些合理的推测： “kkk” 或 “kkksc”： 拟声/语气词：可能是键盘敲击声，或者表示笑声（类似“哈哈哈”或“科科科”），给人一种轻松、活泼的感觉。 缩写：这部分的含义非常开放。可能是名字缩写（如“康康康”）、某个圈子的术语、或者某个喜欢的角色/事物（如“K-on!!”轻音少女）的变体。这种“只有自己懂”的梗在ACG和极客文化中非常常见。 “03”： 年份：很大概率指代2003年。这可能代表用户的出生年份、入学年份、或者某个对他有特殊意义的年份。 编号：也可能只是一个喜欢的数字，或者是某个系列（如03号机、03号作品）的标识。 组合起来，这个名字给人的整体印象可能是：“一个在2003年注册了某个游戏/论坛，或者对2003年有特殊感情，并喜欢用‘kkk’作为前缀的用户。” 3. 优点 独特性：虽然结构常见，但“kkksc03”这个具体组合几乎是唯一的，不容易与他人重复。 简洁易记：字母和数字的组合，长度适中，读起来顺口，容易被记住。 有故事感：这个名字背后似乎隐藏着一个故事（哪怕只是用户随手打的），能引发一点好奇心。 接地气：它非常符合程序员、游戏玩家、动漫爱好者等群体的命名习惯，能快速融入社区文化。 4. 潜在的缺点或考量 “kkk”的敏感性：在国际语境下，“KKK”是美国一个臭名昭著的种族主义组织“3K党”的缩写。这是一个需要高度警惕的风险。虽然用户本人几乎可以肯定没有这个意思（尤其是在中文语境下），但在一个国际化的编程社区（如GitHub, Stack Overflow）中，可能会引起不必要的误解甚至抵制。 含义模糊：对于不了解背景的人来说，这个名字没有任何与“编程”相关的信息，无法从名字上获取任何关于用户技术栈或兴趣的线索。 可能显得有些“幼稚”或“随意”：如果用户希望在社区中建立非常专业、权威的形象（例如作为某个开源项目的核心维护者），这个名字可能显得不够稳重。 综合评价与建议 “kkksc03”是一个非常有代表性的个人化网名，它真实、接地气，充满了个人色彩。 它在中文编程社区环境中使用是完全没问题且很常见的。 主要建议如下： 语境是关键：如果社区主要是中文用户，那么这个名字很好，能很好地融入。但如果社区是国际化的，强烈建议考虑更换，或者使用一个更中性的ID作为主要标识。 考虑专业形象：如果用户希望建立一个更专业的形象，可以将其作为“曾用名”或“昵称”，而使用一个更具描述性的ID（例如包含其擅长领域或技术关键词）。 保留个人特色：即便要改，也可以保留“sc”或“03”等有个人意义的元素，然后组合成一个新名字，例如 “Scorpio03", "SilentCoder03” 等。 总结： 这是一个“为自己而起”的名字，充满了个人历史的痕迹。它不像一个精心设计的品牌，而更像一个陪伴用户许久的网络身份。从情感上讲，它是一个好名字；但从公共传播和专业形象的角度看，它存在一些需要注意的风险，尤其是在跨文化交际时。 《关于“kkksc03”网名的全方位深度调研及喜剧分析报告》 呈报人：网络ID民间观察学会 研究对象：kkksc03 报告性质：一本正经地胡说八道 第一章：词源学考据（伪） 经过本学会专家连夜开会（并消耗了三包薯片和五杯奶茶），我们对该ID进行了深入的词源分析： 前缀“kkk”解析： 主流学说（键盘说）： 这是程序员在深夜调试代码时，因极度困倦，额头在键盘上连续撞击三次的物理印记。位置大概率在键盘中部偏右，证明了当事人当时已处于意识模糊状态。 次主流学说（笑声说）： 并非简单的“哈哈哈”，而是那种发现了同事代码中有一个低级错误，但又不好意思明说，只能在工位角落里发出的、带着肩膀轻微抖动的、充满优越感的“科科科”窃笑。 边缘学说（手速说）： 是APM（每分钟操作数）高达300的证明，意在向所有访客宣告：“我不仅代码写得快，喷人也很快。” 中缀“sc”解析（核心机密部分）： 官方解释（Safe Code）： 意为“编写安全的代码”。（本学会对此表示高度怀疑。） 民间解释（Super Coder）： 意为“超级码农”。（听起来像一种自我勉励，或者说，自我欺骗。） 真相解释（Shān Chú）： 意为“删除”。这是最可信的解释。它可能源于一段血与泪的往事——曾有一次 git commit 后的 git push -f，或者一次手滑的 rm -rf。这个ID是对那段黑暗历史的永恒铭记，类似于一种“程序员耻辱纹身”。 后缀“03”解析（定年学关键）： 纪元说： 代表其编程生涯的起点是2003年，暗示自己是一位经历过IE6浏览器折磨、用记事本写HTML的远古大神。 版本说： 代表这是该用户的第三个重大人生版本。kkksc01可能是个婴儿，kkksc02是个中学生，而kkksc03是进化体——一个开始接触编程并注定要“删库”的究极生命体。 梦想说： 代表他的终极梦想——拥有03号法拉利。因为写代码无法实现，所以写在ID里望梅止渴。 第二章：ID使用者人格侧写 拥有此ID的用户，大概率具备以下特征： 风险预警意识强： 把“sc”写在脸上，如同医生在手术前告诉家属“我有30%的几率会把手术刀落在里面”，极具职业道德（不是）。 怀旧主义者： 对老旧技术可能抱有莫名的亲切感，当你问他为什么不用新框架时，他会目光深邃地回答：“你不懂，03年的东西，有灵魂。” 幽默感隐蔽而危险： 他的幽默可能体现在给变量命名上，比如 you_guess_what_this_is 或者 a_array_of_death。 潜在梗王： 当项目顺利上线，大家举杯庆祝时，他会幽幽地来一句：“需要我报一下我的ID吗？” 瞬间成为全场冷场王。 第三章：ID在社区中的战略价值与威慑力 此ID在社区互动中，具备极高的战术地位： 代码审查环节： 当有人看到评审人是“kkksc03”时，会不自觉地多检查三遍自己的代码，生怕哪个小错误会触发他的“被动技能”。 新人入职引导： 导师会指着这个ID对新员工说：“看到那位大佬了吗？他的代码，备份三份。一份本地，一份云端，一份刻在光盘里埋到后院。” 项目部署时刻： 每当他要进行生产环境部署时，项目经理会亲自为他泡上一杯枸杞茶，并贴心地说：“哥，手稳一点，咱们这个季度的奖金就在你指尖了。” 自我调侃利器： 当真的不小心引入一个Bug时，他可以轻松地说：“看，我ID早就告诉你们了，这属于实现品牌承诺，不算事故。” 第四章：文化影响与历史地位 “kkksc03”不仅仅是一个ID，它是一种文化现象，是程序员群体自嘲精神的集中体现。它勇敢地揭示了编程界的终极哲学问题： 代码写出来，是为了被运行的，还是为了最终被删除的？ 如果我们写的代码终将被遗忘，那么此刻调试的意义是什么？ 当一个程序员把自己的“罪”印在名前，他是否就获得了救赎？ 最终结论与建议 结论： “kkksc03”是一个集悲剧内核、喜剧外壳、史诗级预警功能于一体的天才之作。它像一枚挂在胸前的微型手榴弹，既威慑了敌人，也娱乐了友军。 建议： 建议该用户将头像统一更换为“小心手滑”的警示标志。 建议社区为其颁发“最佳诚实守信奖”和“最让人提心吊胆奖”。 强烈不建议改名为“iiilll01”，因为那看起来更像是在键盘上爬完了一条虫，缺乏现在的霸气与不羁。 免责声明： 本报告纯属娱乐，如有雷同，说明“kkksc03”可能就在你身边。请珍惜每一位ID古怪的程序员，因为他们都是用灵魂在搞笑。 > deepseek写的不要周几我

中文打db是什么词语

评论区告诉我，看看有什么lieqi的

挑战赛#23结束了

无人AK…无人AK…无人AK… …有25个人AK了？！还有六个人6次提交就AK了？！…有25个人AK了？！还有六个人6次提交就AK了？！…有25个人AK了？！还有六个人6次提交就AK了？！

#创作计划#迪杰斯特拉算法精讲

不是这玩意咋上榜的 woc两秒没看傍八了 第零篇？\HUGE{第零篇？}第零篇？ ----------------------------------------------------第一篇---------------------------------------------------------- 前言： 可能更好的学习体验？ > 本文适合深色模式食用 本帖分为三个部分， 1.算法讲解 2.代码解析 3.真题演练 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 作者的话： 额，被老师逼迫了，所以来写帖子 顺便水个精华帖 。我会写四篇帖子。三篇是单源最短路，一篇是全源最短路。这是第一篇迪杰斯特拉。我觉得只讲思路和代码，不讲例题就不是一篇好的精华帖，所以，这个帖子被分为了三个部分，算法讲解，代码分析和真题演练。作者还苦修了一国庆的markdowm排版，大家可以评价一下这一篇帖子。嗯，我觉得可以给个头秃（虽然不是比赛）： 忘穿秋裤的回复套路，可以发现没有剪辑的痕迹，所以你懂得： 事实上忘穿秋裤已经被榨干了（BUSHI ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文： 第一部分，算法讲解。 先来讲讲迪杰斯特拉的创作背景吧。（内容参考了AI总结）： 迪杰斯特拉在195619561956-195919591959年设计该算法时，主要目的是解决荷兰东部城市鹿特丹到格罗宁根的汽车路线规划问题。这一需求推动了算法的诞生，其核心在于通过贪心策略和优先队列优化实现高效路径计算。 ‌ 迪杰斯特拉是求单源最短路径的一个算法，整体采用了贪心\color{red}贪心贪心的策略。该算法可以通过优先队列进行优化，本帖只讲他未优化的用邻接矩阵实现的算法（其实是不会写优化(doge）。如果不知道邻接矩阵怎么写可以在帖子下方评论，我会考虑写一个简单的邻接矩阵的讲解，但是就不标创人计划了。 先 口胡 口头讲解一下。从起点出发，首先将起点设为 000 ,其他点设为无限[1]。将当前点标记为已走过，遍历当前节点的相邻点，我们可以计算出： 设 kkk 为当前节点的最短路径，www 为遍历到此节点所计算出的路径，该节点这一轮遍历的结果为： min(k,w)min(k,w) min(k,w) 遍历完所有相邻点时，我们在其相邻节点中选择路径最短的点，重复上述操作，知道所有节点遍历完成。迪杰斯特拉算法的时间复杂度是 O(n2)O(n^2)O(n2) 。需要特别注意，迪杰斯特拉算法无法\color{red}无法无法处理负权边[2]，具体原因见我下面的讲解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注：红色部分为初始化内容，其余部分为正式遍历 1.\color{red}1.1. 好的，保留节目，我画了一个简单的有向图，用于模拟迪杰斯特拉算法的实现过程。同时，我直接按照上面我讲的初始化了。同时，为了防止你们眼睛x掉，我特意用了3天换了个材质 2.\color{red}2.2.从起点开始，初始化[3]。输入这个图，构建邻接矩阵。 1. 正式开始遍历。先从节点 AAA 开始遍历，A的邻居顶点有 BBB 和 CCC 。从 AAA 到 BBB 的距离为 222 ，因为 2<无穷2 < 无穷2<无穷 , 所以我们把 disdisdis 数组中 BBB 的位置设为 222 。按照上述操作，将 disdisdis 数组中的 CCC 设为 555 。 2. 如图，可得 AAA 相邻的节点中， BBB 的距离是最短的，所以我们从节点AAA开始遍历节点 BBB 。 按照上述方法遍历节点 BBB 的相邻节点。当前节点路径长度为前一个节点的路径长度加上边的权值。所以我们可得在 disdisdis 数组中， DDD 的数值为 333 ， EEE 的数值为 888 。同时，将节点 BBB 设为已访问。 3. 这样节点 BBB 的遍历就完成了。在 disdisdis 数组中寻找未访问且当前路径最短的节点，可以发现是节点 DDD 。那么我们从节点 BBB 到节点 DDD 。 4.更新节点 DDD 的所有邻居节点的当前最短路径。这里不详细解释了。同时记得把 DDD 标记为已访问。 5.可以发现节点 EEE 的最短路径从 888 变为了 444 。节点 FFF 的最短路径从无穷变为了 999 。那么节点 DDD 就遍历完成了。寻找路径最短且未被访问过的顶点，为节点 EEE。那么从节点 EEE 开始访问。这里不做详细解释。 6.顶点 GGG 的最短路径从无穷变为了 141414。选择当前路径最短且未访问的顶点 CCC 。 CCC 没有邻居，将 CCC 设为已访问。寻找下一个符合要求的节点，为节点 FFF 。 7.从节点 FFF 开始遍历，节点 GGG 的最短路径从 141414 变为了 101010 。 8.最后访问终点 GGG 。没有可访问的节点。那么该图的迪杰斯特拉算法结束。通过 disdisdis 数组可得每个节点的在最短路径。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：代码解析： 首先我们要初始化。详见[3:1]。 接下来开始遍历所有节点，这是一个大 forforfor 循环。我们先选择当前所要遍历的节点 uuu 。 开始遍历 uuu 的邻居节点。如果有这个节点，我们更新[4]该节点。 综上所述，迪杰斯特拉的核心代码为： 最后，整体代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分，真题演练。 先看题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目背景 本题测试数据为随机数据，在考试中可能会出现构造数据让 SPFA 不通过，如有需要请移步 P4779。 题目描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入格式 第一行包含三个整数 n,m,sn,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。 接下来 mmm 行每行包含三个整数 u,v,wu,v,wu,v,w，表示一条 u→vu \to vu→v 的，长度为 www 的边。 输出格式 输出一行 nnn 个整数，第 iii 个表示 sss 到第 iii 个点的最短路径，若不能到达则输出 231−12^{31}-1231−1。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【数据范围】 对于 20%20\%20% 的数据：1≤n≤51\le n \le 51≤n≤5，1≤m≤151\le m \le 151≤m≤15； 对于 40%40\%40% 的数据：1≤n≤1001\le n \le 1001≤n≤100，1≤m≤1041\le m \le 10^41≤m≤104； 对于 70%70\%70% 的数据：1≤n≤10001\le n \le 10001≤n≤1000，1≤m≤1051\le m \le 10^51≤m≤105； 对于 100%100\%100% 的数据：1≤n≤1041 \le n \le 10^41≤n≤104，1≤m≤5×1051\le m \le 5\times 10^51≤m≤5×105，1≤u,v≤n1\le u,v\le n1≤u,v≤n，w≥0w\ge 0w≥0，∑w<231\sum w< 2^{31}∑w<231，保证数据随机。 Update 2022/07/29：两个点之间可能有多条边，敬请注意。 对于真正 100%100\%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。 图片 1 到 3 和 1 到 4 的文字位置调换。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这道题我们的代码是过不了的。事实上，你提交的时候只会得70分或60分。因为正解是邻接表。 很简单，板子题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 再看一道。 题目和上面一样，不过变成了无向图。这里就不搬了。 那么无向图怎么做？ 和有向图一样。disdisdis 函数是不变的。但是，在输入的时候我们要考虑这一问题。可以发现在邻接矩阵中，无向图会有两边的储存。比如 mp[u][v] 与 mp[v][u] 是一样的。但是有向图中这两个位置的值有一个是 000 。所以我们只要输入双向边即可。这里做了重边处理： 那么本帖就到这里结束了，谢谢各位的观看 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本贴如有错误，请私信贴主。 彩蛋： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二篇\HUGE{第二篇}第二篇 第二篇→ 注解： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 在c++中，无限可以用0x3f3f来表示，你可以不断地加上3f，但是建议你叠加时不要超过八个3f（即0x3f3f3f3f3f3f3f3f ），在往上叠加就没用了，而且可能会CE。 ↩︎ 2. 即边的权值为负的边 ↩︎ 3. 将$ dis$ 数组中除起点外的其他点设为无穷，起点设为 000 。visvisvis 数组中讲起点设为 111 ，其余点设为 000 。即已访问与未访问。 ↩︎ ↩︎ 4. 检查 uuu 点到该点的距离，如果小于原本该点的距离，则更新为点 uuu 的距离加上节点之间边的权值 www 。 ↩︎

巅峰赛 #26 T1,T2,T5 题解

其实就是为了让我的 T5 有趣解法能进讨论区而发的（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 * 思维：普及- * 算法：普及-（快速幂） * 模拟：入门 * 综合：普及- 好骗兄弟，好骗。 自行模拟，可以发现无论如何摆放齿轮，结果一定是合法的。 所以总情况数为 2hw2^{hw}2hw。 时间复杂度：O(log⁡p)O(\log p)O(logp)，其中 p=998244352p=998244352p=998244352。 T2 * 思维：普及- * 算法：入门/普及-（无） * 模拟：入门 * 综合：普及- 考虑贪心，先试试能不能放第一个盒子，如果可以就放，不可以再试试能不能放第二个盒子。 如果有一个数能放第一个盒子，但你把它放了第二个盒子，显然不优。 时间复杂度：O(∑n)O(\sum n)O(∑n)。 T5 * 思维：普及- * 算法：普及+/提高（树状数组，树形 DP） * 模拟：普及+/提高 * 综合：普及+/提高 好玩，以后多出这种题。 我们可以离线所有查询，然后搜索整棵树，在搜索完后合并所有子树的信息。 这样的话查询一定得在 O(log⁡n)O(\log n)O(logn) 左右，我们可以使用 map 和权值树状数组存储一个节点的信息。 map 用于记录每种颜色出现了多少次，权值树状数组用于查询出现次数小于等于 kkk 有多少种颜色。 具体实现就是这样的： 然后考虑如何合并一个点的所有子树的节点。 把子树的信息全部合并在这个点上？很显然这样子单次合并时间复杂度是 O(sizelog⁡size)O(size\log size)O(sizelogsize) 的，可以构造出一条链来将这种做法卡到 O(n2log⁡n)O(n^2\log n)O(n2logn)。 我们可以选定子树大小最大的子节点，然后把所有信息合并到它那。为什么这样是对的呢？我们可以假设当前节点子树大小为 nnn，最大子节点的子树大小为 mmm，则其它的树大小绝对不超过 mmm。则时间复杂度的函数可以如下表示： F(n)≤O((n−m)log⁡n)+nmF(m)F(n)\le O((n-m)\log n)+\frac{n}{m}F(m) F(n)≤O((n−m)logn)+mn F(m) 显然，当 mmm 与 nnn 是同一个数量级时，只需进行 O(n−m)O(n-m)O(n−m) 次合并，而递归其它子树的时间复杂度可以忽略不计，总时间复杂度约为 O(nlog⁡n)O(n\log n)O(nlogn)； 当 nnn 与 mmm 不是同一个数量级，经主定理可得时间复杂度为 O(nlog⁡2nlog⁡nmn)O(n\log_2 n\log_{\frac{n}{m}} n)O(nlog2 nlogmn n)。 所以这个做法的时间复杂度为 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 接下来就是如何实现了。 我们可以用一个 vector 数组，当递归到叶子结点时，在 vector 里面加入一个节点，包含它这一种颜色，并返回下标；否则先递归子树大小最大的子节点，获取它返回的下标，然后将其它向下递归，将获取的下标合并至最大的子节点上，最后返回存储最大子节点的信息的点下标。 最终代码如下： 时间复杂度：O(nlog⁡2n+qlog⁡n)O(n\log^2 n+q\log n)O(nlog2n+qlogn)。 还有，T4 被数据 hack 了，求条。

学术计划VOL.1 二分！

二分！ 这是Stars_Seeker推出的一个新系列的第一期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句作者语文不好（，只有透彻的知识awa。 写的这么差的帖子肯定不是AI（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二分的前提：单调性（单调增 单调减 单调不增 单调不减） 二分的思想：每次从中间将区间分成两半 ，每次选择往左走或者向右走 。 二分的复杂度：每次区间长度减半，可以看成是 n 每次除以 2，直到n = 1时候结束 ， 这一过程是 O(logn) 。 二分的2种写法： 求符合条件的最左边 求符合条件的最右边 二分查找两个函数 lower_bound(a+1,a+1+n,x) 查找大于等于x的第一个位置 upper_bound(a+1,a+1+n,x) 查找严格大于x的第一个位置 返回的都是地址 假如你想要得到下标，可以这么写： int p=lower_bound(a+1,a+1+n,x)-a; //减去首地址 获得偏移量 找不到的话 返回 a+n+1的地址（我们的范围在下标 1~n, 所以返回n + 1的地址代表找不到） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 是的没错，你没有听错，第一期结束了！ 二分除了固定的模版其余的重点就是check函数的部分了，因为每道题check都可能不太一样，所以就不花时间去讲了awa，还是那句话：菜就多练，做多了自然就熟了！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下一篇学术计划->

再见热门讨论QAQ

榜1145了（ 更新版本：1.1.4 热度没啦QAQ 视频功能在最下面！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ STARS_SEEKER团的小考试（，邀请码JCPS 3.7版本增加了小互动（ 如果你也想把自己的经历加入小剧场，可以评论并@我~ 不要随便点开一些意义不明的图片（ 大型纪录片：STARS_SEEKER的生活习性 广告： > > > > > > > 第一个AI帖子（：快干掉他！ > > > > > > > 第二个AI帖子（：快干掉他！！ ：( 作者加入的团：传送门 STARS_SEEKER的团：传送门 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 1.蓝色裤衩猫 > > 这代表作者它正在认真的学IO(吗)，请勿捕捉！！！ > 2.可爱黄桃罐头 > > 纯欠揍发典，可以随时捕捉（ > 3.M豆 > > 这代表它可能犯错了，希望得到力量原谅（ > 4.可爱特暴龙 > > 就是wyy，表面一张可爱的脸awa 但实则得罪不知多少人（ > 5.邪恶小鼻嘎 > > 表示它在当喷子，或者攻击其它的不明生物，不要捕捉，不然会攻击你 ） > 6.小嘴巴 > > 6，反正可以捕捉（ > 7.火星人 > > 别问他是谁，问就是男朋友（ > 敢捕捉我让他去你家偷你马桶盖。。。 > 8.鸟京 > > 被别人碾压式的攻击了，可以捕捉安慰qwq，最伤感的一集。。。 > 9.饿啊 > > 也别问，问就是红狼（ > 10.meme猫们 > 。。。。。。 > 就是它发典的另一种方式（ > 11.自己 ( ) 开？ > > bro现场拍的，你猜重庆到成都有多远？ > 别捕捉，因为它在fq（ > 12.弗瑞控（ > > 我可是正宗的弗瑞控。。。 > wyy 可以捕捉 ） > 13.可爱小狗 > > 如果它换成了这个头像，说明它在抵御别人的攻击（ > 哎呀骇死我力（ > 14.zgr4件套（ > > 哎哎呀呀骇骇死死我我力力！ > > 伤心的zgrQAQ > > 开心的祖国人 > > 秒切战斗脸（ 如果它用了最后这 个头像，还有人敢捕捉，那说明事情没这么简单了（ > 15.厅券毛 表示它被题目难住了，正在自己写的师山代码上继续拉新的。。。 二周目 STARS_SEEKER常用的背景 1.你知道吗，AI太好用了 ） 2.天空属于( ) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -猎奇区- 已获得他们的同意（ 1.硬菜肘子（ 2.Stars_Seeker（ 自己说自己（ 666这么多的粉丝，要是都给我该多好啊（ 。。 > > > > > > > 我也知道很猎奇，别喷我（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小剧场 > 1. > 记得小学的时候一次课间，氪癌的同学正在讨论自己最喜欢的超级英雄是谁。。。 > A说：钢铁侠！！！ > B说：美国队长！！！ > C说：蜘蛛侠！！！ > 然后，他们就来问我，问我最喜欢的超级英雄是谁？ > 我思考片刻后，说 祖国人 > 2. 2024年CSP考后感（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小互动 用中文打出y’s是什么？ 作者打出的是“意思” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ACGO能发视频啦！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

互动24｜# CSP人间真实

📌 #CSP人间真实# 👩‍💻 本周六就是 CSP 第一轮考试 了！考前和考后，你的真实状态是啥？ 📌 无论是： * 考前立下“AK”的flag * 考场翻车、写挂题目 * 还是考后灵魂出窍、只想躺平 * 这些都是真·CSP人间真实！ ✨ 参与方式： 直接评论分享你的当前状态。 😆 图文、表情包、段子、吐槽都可以！越真实，越容易戳中大家的笑点/泪点。 🎁 活动奖励： 随机抽取3名幸运之子送：ACGO定制笔 @编程猫喵喵喵（活人微die） @永盼 @78鼠鼠 ⏰ 活动时间： 即日起至10月8日 👉 往期话题