MMOI Round 3 题解

二分笔记

1. 查找 X 是否存在 思路简介 数组有序时，可以用二分查找。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 手写 LOWER_BOUND：查找第一个 >= X 的位置 思路简介 要找的是第一个满足： 的位置。 二分时，如果： 说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以： 如果： 说明 mid 和左边都太小了，所以往右找： 如果不存在，输出 n + 1。 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. STL LOWER_BOUND：第一个 >= X 思路简介 lower_bound 的含义是： 写法： 返回的是地址。 要转成下标，需要减去数组首地址： 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. STL UPPER_BOUND：第一个 > X 思路简介 upper_bound 的含义是： 写法： 返回的是地址。 转成下标： 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5. 手写 UPPER_BOUND：查找第一个 > X 的位置 思路简介 要找的是第一个满足： 的位置。 二分时，如果： 说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以： 如果： 说明 mid 和左边都不满足，只能往右找： 如果不存在，输出 n + 1。 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结口诀 这几份代码的前提都是：数组必须是有序的。如果题目没保证有序，需要先写： 出现次数2 保龄球 出现次数1 和为 0 的 4 个值 最后一个等于X的元素 不同分的人数 学生信息查询 A-B数对 递增三元组 放学人潮

请打出文本（时间：7.16~8.1）

以下全部正确打出来即可获得空白团队5~10个 + 团队管理员1年！（时间：7.16.00.00.00~8.1.00.00.00） 见图片（防止有人直接复制）： 再加多个： 一个人2次机会 随机@一些人： @请输入文本.‎‎‎‎‎‎‎‎‎‎@wcqk@༺ད黯渊◈天蝎ཌ༻@AAA_Cheer_EndBet@终极主宰大神@Wemmbu（SMP）(MC)@MYJ888@EC-山茶‘猫老大@༺ཌༀཉི 斩神༒终焉 ༃ༀད༻@小冰果@AC是最好的@景梓萌（看猴常@）@哇！我传伞太准了Andy@Saturn@‌LLL✗shazi一只 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【大师主宰×ACGO之星】2026暑期算法巅峰联赛（邀请码：8BAA）

有奖：皮皮虾团队复活比赛

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PPX-复活赛 【PPX-复活赛】皮皮虾团队复活比赛 【邀请码 WrGj】 点击直达 本次比赛较为简单，适合 XP01-XP03A 的同学参赛 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 皮皮虾暑期赛2 【PPX-012】皮皮虾暑期竞赛2【邀请码 sdwW】 点击直达 本次比赛较为简单，适合 XP02-XP03B 的同学参赛 皮皮虾团队将在这个暑假复活一段时间，预计举办 5 场比赛，这是第 3 场。（不算 CXXP#2） 奖励可以商议，进行微调。 注意，如果你在本次比赛中使用了 AI 或者其他插件辅助答题，你将被设置为作弊者；如果你在团队之前有违规记录，你将直接被踢出团队。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ CXXP#2 CXXP#2 官方公开赛，有机会领取限定头像框以及大量罐头！ 适合 XP03A-XP05 参与 注意，如果你在 CXXP 中，有过违规行为，那么你在 CXXP#2 中不能获奖。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 皮皮虾暑期竞赛 【PPX-010】皮皮虾暑期竞赛【邀请码 7TJA】点击直达 适合 XP02-XP03B 参加 奖励内容见竞赛页面！

赢暑期活动 共赴团赛之约（有奖品）

一年一度的暑期活动在欢声笑语中走来啦！ > > 此次活动主办方@༺ད黯渊◈天蝎ཌ༻和支持方@AAA_Cheer_EndBet 活动主题（暂且不提团赛）入团才能参赛 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1·活动为字符打印赛（为@码农爱历史灵感，现在更新） ⚠如果发现抄者重罚，打字规则如下 1.只能私信打字（赢者会在8月15日宣布） 2.报名活动在讨论区输入“我是‘谁’，我参加打字比赛“ 3.禁止相互问，期间作者会查你到底怎么打的 4.上述表格粘贴不了 5.禁止辱骂他人行为 6.打字素材有ACGO部分 7.想要提示，那么先竞赛对2道 开始时间：2026年7月25日，现在可报名 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 共赴团赛！！！ > 本次团赛出题员及审题员 > 跳转团赛 出题员 审题员 @AAA_Cheer_EndBet @编程&神(互关) @码农爱历史 @Expected expr @景梓萌（看猴常@） @wcqk > 本次团赛赛时答疑员及赛后检察员 赛时答疑员 赛后检察员 @💩💩百大游戏解说官💩💩 @wcqk > 团赛奖励 名次 奖品 NO.1 神秘实物，地址考完发我 NO.2 空白团队1个 NO.3 可以让作者买人数增加 NO.4 40罐 幸运奖5位 20罐或者一个空白团队 > 团后发罐小组 组员 @国服武术家(互关） @景梓萌（看猴常@） 竞赛有问题？ 我们欢迎所有人来发问，一起追究题目问题 用AI处罚 但凡发现有用AI作弊，则去除该奖项，所以大家都不要用AI，锻炼自己编程水平吧！ 至竞赛完毕则发布作弊&获奖名单 赛事答疑帖敬请期待

小作坊自研赌罐头教程

榜5了?！ 先来段广告：点击查收 引入 这是我同学赌罐头的遭遇 点这里围观 ———————————————————————————————————————————— 正文 事先声明，本帖远不如 ༺ཌༀཉི༒白·羊༒༃ༀད༻的全网最详细赌罐头教程专业，如出现问题请不要来找我。 罐头数量 稀有度 1999罐头 稀有惊喜 888罐头 幸运馈赠 399罐头 超值礼遇 199罐头 常见好礼 99罐头 日常收获 66罐头 基础祝福 从上面这张表格可以看出赚的概率有三成，不亏不赚的有一成，亏的有两成，总共六成。 看似亏得概率都不高，但用大脚趾想都能明白， 事情绝对没有这么简单\color{red}{事情绝对没有这么简单}事情绝对没有这么简单 先看一组数据 注：本人是一个一个买的，并非一批一批买\color{yellow}注：本人是一个一个买的，并非一批一批买注：本人是一个一个买的，并非一批一批买 还有一个199没放出来 对于20次大概是 99:10%，199:50%，888:10%，66:30%，1999:0%，399:0% > 7.18日 连续出5个199也是脸黑成锅底了，又又又又证实了下文的第一条和第四条 7.18日资金（其中有刷题以及运势的成分）为 > 7.20-7.21，又又又又证明了下文第一条、第三条和第五条 今日资金 呜呜呜，大亏的一天，我为了你们，从857跌倒363，难道就不值你们的一个赞吗？ 不妨我们可以总结出一下几点 1.199 十分不吉利\color{red}{ 十分不吉利}十分不吉利，常常会带来66、99、199这些对我们不利的数字\color{red}{ 对我们不利的数字}对我们不利的数字。 2.开完888立刻收手，应为可能下一个就是199\color{red}{ 199}199。 3.66经常伴随199一同出现。 4.199出现频率极高！！！！ 5.66会带来66\color{red}{ 66}66和199\color{red}{ 199}199，与199一样不吉利\color{red}{ 一样不吉利}一样不吉利 有补充的可以评论区留言或私信。 稀有的1999和399目前还没遇见，所以不知道有什么规律。其他还是要靠玄学。 > AC之神的祝福属于一种高风险，低收入（个别高收入）的东西，没有足够本事的还是老实做题，打天梯，慢慢攒比较好。 以后我会更新这条帖子，尽量将40次，60次，80次，甚至100次做出来。 接个广子 内容制作不易，请大家多多支持,蟹蟹了

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

官方题解 | 欢乐赛#77题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔看时间 入门 T2 皓仔的铁人三项 入门 T3 皓仔找元音 入门 T4 皓仔截取数字 入门 T5 皓仔的进制回文数 普及- T6 皓仔的队伍排序 普及- T1 皓仔看时间 题意简述 给定当前时间的小时 h 和分钟 m。 要求按照 hh:mm 的格式输出时间。 如果小时或分钟不足 222 位，需要在前面补 000。 解题思路 这是一道格式化输出题。 小时和分钟都要固定输出 222 位，可以使用 printf 的格式控制： %02d 表示输出一个整数，并且宽度为 222 位，不足 222 位时在前面补 000。 所以直接输出： 即可。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T2 皓仔的铁人三项 题意简述 给定皓仔在铁人三项中三个项目的排名 a、b、c。 如果满足下面任意一个条件，就可以获奖： 三个项目都排在前 555 名； 至少有一个项目排在前 222 名。 如果可以获奖，输出 Award，否则输出 No Award。 解题思路 直接按照题意进行条件判断。 第一种获奖情况： 第二种获奖情况： 只要两个条件中有一个成立，就输出 Award。 否则输出 No Award。 时间复杂度为 O(1)O(1)O(1)。 参考代码 T3 皓仔找元音 题意简述 给定一个只包含小写英文字母的字符串 s。 需要找出其中所有元音字母，并按照它们在原字符串中出现的顺序输出。 元音字母包括： 如果字符串中没有任何元音字母，则输出 -1。 解题思路 从前往后遍历字符串 s。 如果当前字符是 a、e、i、o、u 中的一个，就输出这个字符，并记录已经找到过元音字母。 遍历结束后，如果没有找到任何元音字母，就输出 -1。 时间复杂度为 O(∣s∣)O(|s|)O(∣s∣)。 参考代码 T4 皓仔截取数字 题意简述 给定 nnn 次询问。 每次给出一个数字 x 和一个整数 m，要求输出数字 x 最右侧长度为 m 的部分。 注意截取结果中的前导零需要保留。 解题思路 因为题目要求保留截取结果中的前导零，所以适合把数字 x 当作字符串读入。 对于字符串 s，如果它的长度为 len，那么最右侧长度为 m 的部分就是从下标 len - m 开始一直到末尾的字符。 直接循环输出这一段即可。 时间复杂度为 O(n×∣x∣)O(n \times |x|)O(n×∣x∣)。 参考代码 T5 皓仔的进制回文数 题意简述 给定三个整数 l、r、x。 要求统计区间 [l,r][l,r][l,r] 中有多少个整数，在转换成 x 进制后是回文数。 回文数指转换后的表示从左往右读和从右往左读完全相同。 解题思路 因为 r≤106r \le 10^6r≤106，可以直接枚举区间 [l,r][l,r][l,r] 中的每一个整数。 对于每个数： 先把它转换成 x 进制； 然后判断转换后的结果是否为回文串。 进制转换时，可以不断对 x 取余： n % x 得到当前最低位； n /= x 去掉最低位。 因为判断回文时只需要比较两端是否相同，所以可以把每一位存入数组，然后用双指针判断。 时间复杂度为 O((r−l+1)log⁡r)O((r-l+1)\log r)O((r−l+1)logr)。 参考代码 T6 皓仔的队伍排序 题意简述 给定 nnn 名学生的信息，包括出生年月日、身高和姓名。 需要按照下面规则排序： 首先身高更高的排在前面； 如果身高相同，则年龄更大的排在前面，也就是出生日期更早的排在前面。 最后按排序后的顺序输出每名学生的姓名。 解题思路 用结构体数组保存每名学生的信息。 排序时按照题目规则写比较函数： 如果两名学生身高不同，则身高高的排在前面； 如果身高相同，则比较出生日期，出生年份更小的年龄更大； 如果年份相同，再比较月份； 如果月份相同，再比较日期。 题目保证不会有两名学生在同一天出生，所以不需要继续比较姓名。 时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。 参考代码

依旧是florr的问题

身为刚入坑几天的新手，如今也是在我的不懈努力下有了这个青玻璃， so 我又来请教各位大佬，那个玻璃轮到底是怎么弄？到怎么个程度可以了？ 还是献祭自己图片： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 7.16献祭图片

2026暑期算法巅峰联赛(8baa)

竞赛链接1：【大师主宰×ACGO之星】2026暑期算法巅峰联赛（邀请码：8BAA） 竞赛链接2（其他的竞赛，推荐！！！）：13团暑期竞赛（邀请码：8554） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 已报名28人，参与9人，作弊嫌疑1人。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、竞赛背景 这是一个为备战 CSP、省选、NOI 提供高质量专项训练比赛，试题由浅入深完整覆盖入门至 NOI 全梯度难度， 难度和 13团暑期竞赛（邀请码：8554）差不多(喃逸淀)。 二、竞赛规则\COLOR{RED} 二、竞赛规则二、竞赛规则 1.参赛选手需遵守竞赛纪律，禁止抄袭（AI也算）、作弊等行为（惩罚：拉入团队小黑屋3~30天、发帖警示并取消奖励）。 2.竞赛期间可使用编程语言：C++、PYTHON。 3.禁止与他人交流或使用非公开代码。 4.不准开多个小号竞赛。 三、主办方 由 ACGO之星、大师主宰级团队 合作承办。 四、奖项设置\COLOR{RED}四、奖项设置四、奖项设置 AK选手可自行选择2个团队的一年的管理员或1个团队的永久管理员或1个团队的一年的副队长或1个空白团队。 第一~第二的人可自行选择2个团队的永久的管理员或任意1个团队一年的副队长 或 1个空白团队 或 让 终极主宰大神 新创建一个团队并给选手很高的权限。 第三~第五的人可选2个团队的半年的管理员或1个团队的一年的管理员 或 让 终极主宰大神 新创建一个团队并给选手较高的权限 第六~第十的人选手可自行选择任意1个团队的三个月的管理员 或 终极主宰大神 新创建一个团队并给选手中等的权限 。 第十一~第二十的人可选2个团队的一周的管理员或1个团队的一个月的管理员 或让 终极主宰大神 和 码农爱历史 给你永久关注或 让 终极主宰大神 新创建一个团队并给选手较低的权限。 获奖时间：9月1日00时00分00秒~10月1日00时00分00秒。 奖项可以攒着，前提跟终极主宰大神说。 五、赛况 题目 用户名 8.FB 9.FB 10.FB 首AK 1st 注： 首 AK：第一个完成所有题目（All Kill）。 FB：第一个完成单道题目（First Blood）。 六、讨论规则 禁止说脏话、引战，说了的话拉入团队黑名单并一律删除评论。

“巴威”台风专辑竞赛 获奖名单

图例： ①AK选手 可获得本团永久管理员 或 3个空白团队 或 让 码农爱历史 新创建两个团队 并给选手较高权限。 ②除AK选手以外，第一的人选手 可获得本团 150天管理员 或 2个空白团队 或 让 码农爱历史 新创建 两 三个团队 并给选手较高权限。 ③除AK选手以外，第二~第五的人选手 可获得本团 60天管理员 或 1个空白团队 或 让 码农爱历史 新创建 一（“一”字划掉看不清楚？） 两个团队 并给选手较高权限。 ④除AK选手以外，第六~第十的人选手 可获得本团 15天管理员。 ⑤除AK选手以外，第十一~第二十的人选手 可获得本团 7天管理员。 获奖名单: 用户 奖项(序号见上方图例) @༺ཌༀ我要上科大ༀད༻ ① @码农爱历史 ① @AAA忘川秋库的秋裤批发哥 ② @【典狱长】迪克螺丝 ③ @死神永生 ③ @CALL of DUTY ③ @hopeless ③ @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ ④ @༺ཌༀཉི༒S·Z·T༒༃ༀད༻ ④ @༺ཌༀ我要上浙大ༀད༻ ④ @暴力出奇迹 ④ @priority_lisaike ④ @Sunny.简约 ⑤ @Sisdwits ⑤ @十赌有九输，不赌就是赢 ⑤ @终极主宰大神（求关注必回） ⑤ @꧁༺ཌༀ善ༀད༻꧂ ⑤ @Phantom ⑤ @florr--sftkFH.io ⑤ @APO-梦拟 ⑤ @学 ⑤ @异雷 ⑤ 请在评论区选择并@码农爱历史[@码农爱历史](/PERSON/3766406) 获奖时间：7月15日00:00:00~8月1日00:00:00 编辑中...... ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【大师主宰×ACGO之星】2026暑期算法巅峰联赛（邀请码：8BAA）

MMOI Round 3 题解

明天就是 NOI 2026 Day 1，在这里祝我以及参加 NOI 2026 的选手好运，NOI 2026 rp++！ 赛后总结帖也许要晚一些发布。 T1 矿车交通 这道题的灵感来源于一道小学数学题：在等车回家的时候，是往车的方向走早点遇到车更快、往家的方向先走一段距离更快，还是原地等待更快？答案是一样快，因为坐的都是同一辆车。 因此可以发现换乘是没有必要的——如果 Steve 最后乘坐的是某辆矿车到达终点，那么他可以选择一直在起点等着这辆矿车并一直坐到终点。因此对于每辆矿车计算乘坐这辆矿车会在什么时候到达终点，并取最小值即可。注意特判只靠步行到达终点和 x=yx=yx=y 的情况。 T2 轮回 考虑第 iii 天时 a0a_0a0 在原序列中所对应的下标 pip_ipi ，显然当 iii 不是 mmm 的倍数时，pi=(pi−1+1) mod np_i=(p_{i-1}+1) \bmod npi =(pi−1 +1)modn；否则 pi=pi−1p_i=p_{i-1}pi =pi−1 。将 ppp 中的元素分为两部分进行计算： * 对于 i>0i>0i>0 且 i mod m=0i\bmod m=0imodm=0 的 pip_ipi ，这些 pip_ipi 的值为 (m−1)−1,2(m−1)−1,…(m-1)-1,2(m-1)-1,\dots(m−1)−1,2(m−1)−1,… 模 nnn 意义下的值； * 剩下的 pip_ipi 值为 −1,0,1,2,…-1,0,1,2,\dots−1,0,1,2,… 模 nnn 意义下的值。 可以发现，这两部分每一部分每 nnn 个数都会形成循环，通过计算整个循环带来的贡献，并额外加上剩下的部分即可，时间复杂度 O(n)O(n)O(n)。 T3 奇迹 考虑将 nnn 个数排成一个环，此时最近的一对 111 之间的距离不超过 ⌊nx⌋\left\lfloor\frac{n}{x}\right\rfloor⌊xn ⌋。从小到大枚举两个数的距离 ddd，将环上所有距离为 ddd 的 nnn 对点加入猜测序列中，总猜测次数不超过 ⌊n2x⌋\left\lfloor\frac{n^2}{x}\right\rfloor⌊xn2 ⌋。 T4 游戏 记 C(x,y)=∑k=1n[sufk(x)=prek(y)]dkC(x,y)=\sum\limits_{k=1}^n[\text{suf}_k(x)=\text{pre}_k(y)]d^kC(x,y)=k=1∑n [sufk (x)=prek (y)]dk，其中 sufk(x)\text{suf}_k(x)sufk (x) 为 xxx 长度为 kkk 的后缀，prek(y)\text{pre}_k(y)prek (y) 为 yyy 长度为 kkk 的前缀，[P][P][P] 表示当 PPP 成立时为 111，否则为 000。则子问题一的答案为： C(t,t)−C(t,s)C(s,s)−C(s,t)+C(t,t)−C(t,s)\dfrac{C(t,t)-C(t,s)}{C(s,s)-C(s,t)+C(t,t)-C(t,s)} C(s,s)−C(s,t)+C(t,t)−C(t,s)C(t,t)−C(t,s) 计算 C(x,y)C(x,y)C(x,y) 是简单的：构造字符串 S=y+#+xS=y+\text{\#}+xS=y+#+x，SSS 的每一个 border 都对应一个满足 sufk(x)=prek(y)\text{suf}_k(x)=\text{pre}_k(y)sufk (x)=prek (y) 的 kkk，使用 KMP 算法计算出 SSS 的每一个 border 即可。 对于子问题二，一种可能的构造方案是先取 sss 为 ttt 的前 n−1n-1n−1 位，并在 sss 的最前方放上任意与 t2t_2t2 不同的字符，将 s,ts,ts,t 带入子问题一的公式中很容易证明这是一种合法的构造方案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下面对子问题一的式子给出证明：先只考虑一个目标串 xxx，假设有一种下注游戏，在每一轮抛硬币之前，都新来一个下注者，他下注从当前位置开始未来会出现串 xxx。具体地，他初始时拥有 111 元，下注当前字符为 x1x_1x1 ，如果猜中，则钱数变成原来的 ddd 倍，继续下注 xxx 的下一个字符；否则他的钱数直接变成 000，游戏结束。 不难发现这个游戏是公平的，即每回合结束后每个下注者的期望钱数都仍然是 111，因此若游戏进行了 TTT 回合，所有下注者拥有的钱数和的期望值也是 TTT，因此整个游戏所有下注者拥有的钱数和的期望值为 E(T)E(T)E(T)。 对于原问题，假设每一轮抛硬币之前，都会有两个下注者分别下注 sss 和 ttt。考虑计算游戏以 sss 结束时，猜 ttt 的所有下注者拥有的钱数和：想要结束时有一位连续猜中的 kkk 次的下注者，这要求 sufk(s)=prek(t)\text{suf}_k(s)=\text{pre}_k(t)sufk (s)=prek (t)，并会带来 dkd^kdk 的贡献，这就是式子 C(x,y)C(x,y)C(x,y) 的由来。 设 Steve 获胜的概率为 ppp，则 Alice 获胜的概率为 1−p1-p1−p，那么对于猜测 sss 的所有下注者，其拥有的钱数和的期望值为 pC(s,s)+(1−p)C(t,s)pC(s,s)+(1-p)C(t,s)pC(s,s)+(1−p)C(t,s)。类似地，对于猜测 ttt 的所有下注者，其拥有的钱数和的期望值为 pC(t,t)+(1−p)C(s,t)pC(t,t)+(1-p)C(s,t)pC(t,t)+(1−p)C(s,t)。 按照刚刚的结论，我们发现这两个式子都等于 E(T)E(T)E(T)，所以 pC(s,s)+(1−p)C(t,s)=pC(t,t)+(1−p)C(s,t)pC(s,s)+(1-p)C(t,s)=pC(t,t)+(1-p)C(s,t)pC(s,s)+(1−p)C(t,s)=pC(t,t)+(1−p)C(s,t)，解方程即可得到上面的结论。