结构体

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

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

二分笔记

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数对 递增三元组 放学人潮

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

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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部分 开始时间：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，锻炼自己编程水平吧！ 至竞赛完毕则发布作弊&获奖名单 赛事答疑帖 点击跳转

有没有在小码王牢房的（小码王地狱）

> 这个帖子大家一定爱看 > > > > > > > 这个帖子顶一下 点点赞 评论一下 > > > HTTPS://WWW.ACGO.CN/DISCUSS/REST/87081这个是抄袭的帖子 招收广告位 有没有什么给acgo下令营的建议 在评论区发出来吧 我会at老师的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 网页：(借鉴百团大战 @💩💩百大游戏解说官💩💩) 网页MC： https://play.mcjs.144449.xyz/1.8.8/ poki: https://poki.com/zh crazygame: https://www.crazygames.com/ florr: https://florr.io/ 应用： 植物大战杂交版： https://www.32r.com/soft/104602.html 像素火影： https://www.ddooo.com/softdown/211529.htm 植物大战僵尸融合版 + 二创植物 + MOD： https://www.32r.com/soft/141555.html PCL2: https://soft.3dmgame.com/down/323041.html ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ HTTPS://WWW.ACGO.CN/APPLICATION/1943212557337006080加一下吧 https://www.acgo.cn/application/1940677638216290304有兴趣看一下 > 进来了每天分享作业和比赛答案

小作坊自研赌罐头教程

榜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，难道就不值你们的一个赞吗？ > > 7.24 终于，出399辣！！！！！！也变相证明了第2条 不妨我们可以总结出一下几点 1.199 十分不吉利\color{red}{ 十分不吉利}十分不吉利，常常会带来66、99、199这些对我们不利的数字\color{red}{ 对我们不利的数字}对我们不利的数字。 2.开完399，888立刻收手，应为可能下一个就是199、66\color{red}{ 199、66}199、66。 3.66经常伴随199一同出现。 4.199出现频率极高！！！！ 5.66会带来66\color{red}{ 66}66和199\color{red}{ 199}199，与199一样不吉利\color{red}{ 一样不吉利}一样不吉利 有补充的可以评论区留言或私信。 稀有的1999目前还没遇见，所以不知道有什么规律。其他还是要靠玄学。 > AC之神的祝福属于一种高风险，低收入（个别高收入）的东西，没有足够本事的还是老实做题，打天梯，慢慢攒比较好。 以后我会更新这条帖子，尽量将40次，60次，80次，甚至100次做出来。 接个广子 内容制作不易，请大家多多支持,蟹蟹了

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

竞赛链接1：【大师主宰×ACGO之星】2026暑期算法巅峰联赛（邀请码：8BAA） 竞赛链接2（其他的竞赛，推荐！！！）：13团暑期竞赛（邀请码：8554） 竞赛链接3（新的）：13团暑期竞赛附加赛(邀请码:YZZX) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 已报名44人，参与14人，作弊嫌疑2人。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、竞赛背景 这是一个为备战 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）。 六、讨论规则 禁止说脏话、引战，说了的话拉入团队黑名单并一律删除评论。

官方题解 | 欢乐赛#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)。 参考代码

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)，解方程即可得到上面的结论。

官方题解 | 巅峰赛#36

巅峰赛36 题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的传话游戏 普及/提高- T2 午枫的教室路线 普及/提高- T3 午枫的数字替换 普及/提高- T4 午枫的课堂笔记 普及/提高- T5 午枫的自习时间 普及+/提高 T6 午枫的涂色方案 普及+/提高 T1 午枫的传话游戏 题意简述 有 nnn 个同学，每人有一个数字 aia_iai 。若两数绝对差为 111 则可直接传话，传话关系具有传递性。求最少添加多少对直接传话关系，使得整个图连通（任意两人可互相传话）。 解题思路 将数字视为节点，值相等的同学共享同一节点（他们之间差值为 000，需要额外处理）。先对数组排序去重分析连续段：如果两个相邻数值相差为 111，则它们天然有边相连；若相差 >1>1>1，则这两段之间需要添加一条边来连通。因此，数值轴上会形成若干个由差值为 111 的连续段构成的连通块。 对于同一数值有多人的情况：这些人内部没有直接边（差值 000），他们必须借助相邻数值才能连通。如果一个连通块中只有一个数值（左右均断），那么该数值内的 ttt 个同学需要 t−1t-1t−1 条边才能内部连通，并且还需与外部块连接。当连通块有多个数值时，块内的所有同学可通过链式结构自然连通，只需向外连边时添加一条边。 边数最少为 max⁡(0,连通块数−1)+∑(孤立数值内部人数−1)\max(0, \text{连通块数} - 1) + \sum(\text{孤立数值内部人数} - 1)max(0,连通块数−1)+∑(孤立数值内部人数−1)。 参考代码 T2 午枫的教室路线 题意简述 有一个 H×WH \times WH×W 的网格，从 (1,1)(1,1)(1,1) 走到 (H,W)(H,W)(H,W)，每次只能向下或向右。给定一个长度为 H+W−2H+W-2H+W−2 的字符串 SSS，其中 D 表示这一步必须向下，R 表示必须向右，? 表示可以自由选择向下或向右。对于每一种合法的路径，我们把该路径经过的所有格子（包括起点和终点）标记为已访问。问在所有合法路径中，最多能有多少个不同的格子被至少一条路径访问到。 解题思路 令必须向下的步数为 DfixD_{fix}Dfix ，必须向右的步数为 RfixR_{fix}Rfix ，自由步中需选 n=H−1−Dfixn = H-1-D_{fix}n=H−1−Dfix 步为向下、m=W−1−Rfixm = W-1-R_{fix}m=W−1−Rfix 步为向右。问题等价于求有多少格子 (i,j)(i,j)(i,j) 存在一种 ? 的赋值，使得路径经过该格。 考虑格子 (i,j)(i,j)(i,j)，到达它需要 k=i+j−2k = i+j-2k=i+j−2 步，其中向下 i−1i-1i−1 步。设前 kkk 步中必须向下 dkd_kdk 步、必须向右 rkr_krk 步、自由 sks_ksk 步。后 L=H+W−2−kL = H+W-2-kL=H+W−2−k 步中必须向下 dL′d'_LdL′ 步、自由 sL′s'_LsL′ 步。存在合法路径经过 (i,j)(i,j)(i,j) 当且仅当存在整数 xxx（前 kkk 步中选择向下的自由步数）满足： * i−1=dk+xi-1 = d_k + xi−1=dk +x，即 x=i−1−dkx = i-1-d_kx=i−1−dk * 0≤x≤sk0 \le x \le s_k0≤x≤sk ，且 x≤nx \le nx≤n * H−i=dL′+(n−x)H-i = d'_L + (n-x)H−i=dL′ +(n−x)，即 n−x=H−i−dL′n-x = H-i-d'_Ln−x=H−i−dL′ * 0≤n−x≤sL′0 \le n-x \le s'_L0≤n−x≤sL′ 消去变量后，固定 kkk 时 iii 的取值范围为： max⁡(dk+1,  k−min⁡(sk,m)−rk+1)≤i≤min⁡(min⁡(sk,n)+dk+1,  k−rk+1)\max(d_k+1,\; k - \min(s_k, m) - r_k + 1) \le i \le \min(\min(s_k, n) + d_k + 1,\; k - r_k + 1) max(dk +1,k−min(sk ,m)−rk +1)≤i≤min(min(sk ,n)+dk +1,k−rk +1) 其中 n=H−1−Dfixn = H-1-D_{fix}n=H−1−Dfix ，m=W−1−Rfixm = W-1-R_{fix}m=W−1−Rfix 。每个 iii 对应格子 (i,k+2−i)(i, k+2-i)(i,k+2−i)。 遍历 k=0k = 0k=0 到 H+W−2H+W-2H+W−2，累加每个 kkk 对应的合法 iii 的个数，即为答案。起点 k=0k=0k=0 和终点 k=H+W−2k=H+W-2k=H+W−2 自动包含在内。 参考代码 T3 午枫的数字替换 题意简述 给定一个长度为 NNN 的数字串 SSS 和一个长度为 MMM 的数字串 TTT，按顺序进行 MMM 次操作，第 kkk 次操作可以将 SSS 的任意一个位置替换为 TTT 的第 kkk 个字符。每次替换会覆盖原有数字。问经过全部 MMM 次操作后，得到的 SSS 作为整数值最大是多少，输出这个字符串。 解题思路 我们依次进行 MMM 次替换，每次可以选任意位置。最后一次操作特别重要，因为它不会被后续操作覆盖。如果我们把某个数字放在最后一次操作中，它就会永远留在最终字符串的那个位置上。 为了使得最终字符串的字典序最大，我们希望前面的字符尽可能大。因此，一个直观的贪心策略是：除了最后一次操作的数字以外，前面的 M−1M-1M−1 次操作我们可以自由选择用哪些数字去替换哪些位置。我们把这 M−1M-1M−1 个数字从大到小排序，然后从左到右扫描 SSS 的每个位置，如果当前最大的可用数字比 SSS 这个位置上的数字大，就进行替换，然后这个数字被消耗掉，继续看下一个位置。这样可以保证在前面的位置上尽量使用大的数字。 接下来考虑最后一次操作的数字 TMT_MTM 。它必须被用到某个位置上。如果在前面的贪心过程中，TMT_MTM 已经被当作一个较大的数字使用过了（即它已经被换到了某个位置上），那就不用再额外处理。如果没有被使用过，说明 TMT_MTM 比 SSS 中所有未被替换过的位置上的数字都小（因为贪心过程中只有遇到更大的数字才会替换）。此时，我们只能把它放在某个位置上，为了对整个字符串的字典序影响最小，应该把它放在最后一位。因为放在任何更前面的位置都会使得那个位置变小，从而让整个字符串变小，而放在末尾只会影响最后一位，前面的大数字结构保持不变。 这样操作后，得到的字符串就是最大的可能结果。 参考代码 T4 午枫的课堂笔记 题意简述 按顺序处理 NNN 个数，对每个数必须恰好执行一次操作：要么写入到笔记板末尾，要么删除笔记板末尾的一个数（板为空时不能删除）。操作结束后，笔记板中剩余数的和即为结果。求最大可能和。 解题思路 定义 f[i][0]f[i][0]f[i][0] 表示处理完前 iii 个数且第 iii 步执行删除操作时，当前栈中数字和的最大值；f[i][1]f[i][1]f[i][1] 表示第 iii 步执行写入操作时的最大值。 若第 iii 步是删除，则它必须删除上一步刚写入的数，因此第 i−1i-1i−1 步必须是写入，删除后状态回到第 i−2i-2i−2 步之后的状态，故 f[i][0]=max⁡(f[i−2][0],f[i−2][1])f[i][0] = \max(f[i-2][0], f[i-2][1])f[i][0]=max(f[i−2][0],f[i−2][1])。 若第 iii 步是写入，则直接加上 AiA_iAi ，可以从第 i−1i-1i−1 步的任意状态转移来，即 f[i][1]=max⁡(f[i−1][0],f[i−1][1])+Aif[i][1] = \max(f[i-1][0], f[i-1][1]) + A_if[i][1]=max(f[i−1][0],f[i−1][1])+Ai 。 初始条件 f[1][0]f[1][0]f[1][0] 不合法（第一步不能删除），设为负无穷；f[1][1]=A1f[1][1] = A_1f[1][1]=A1 。最终答案为 max⁡(f[N][0],f[N][1])\max(f[N][0], f[N][1])max(f[N][0],f[N][1])。 参考代码 T5 午枫的自习时间 题意简述 给定一个长度为 NNN 的字符串 SSS，由 o 和 x 组成。将 SSS 重复 MMM 次得到字符串 TTT（长度为 N×MN \times MN×M）。你可以将 TTT 中恰好 KKK 个 x 改为 o。问修改后最长的连续 o 子串长度最大是多少。 解题思路 设 SSS 中 x 的总数为 cntcntcnt。由于 MMM 可能很大（10910^9109），不能直接构造 TTT。考虑分情况讨论。 首先，如果 M=1M = 1M=1 或 M=2M = 2M=2，可以直接构造出 TTT（长度最多 2N≤6×1052N \le 6\times 10^52N≤6×105），然后用双指针（滑动窗口）求最多包含 KKK 个 x 的最长区间即可。 当 M≥3M \ge 3M≥3 时，考虑在完整的若干个 SSS 块中，每块有 cntcntcnt 个 x。设 num=⌊K/cnt⌋num = \lfloor K / cnt \rfloornum=⌊K/cnt⌋，即可以完全填满的块数。分三种情况： * 若 num≥Mnum \ge Mnum≥M，则所有 MMM 个块都可以完全填成 o，答案为 N×MN \times MN×M。 * 若 num=M−1num = M-1num=M−1，则前 M−1M-1M−1 个完整的块可以全部填满，剩下 K′=K−(M−1)×cnt+cntK' = K - (M-1) \times cnt + cntK′=K−(M−1)×cnt+cnt 次调整机会（注意这里 STD 中写的是 k = k % cnt + cnt，相当于先消耗掉 M−1M-1M−1 个整块，剩下的 kkk 可能小于 cntcntcnt，但为了充分利用，实际上是在两个块中寻找最长的区间，最后加上 (M−2)×N(M-2) \times N(M−2)×N 作为中间已填满的块的长度）。 * 若 num≤M−2num \le M-2num≤M−2，则中间有 numnumnum 个完整填满的块，剩下的 K′=K%cntK' = K \% cntK′=K%cnt 次调整机会用于在前后两个块中跨越拼接。同样用双指针在 S+SS+SS+S 上找最多包含 K′K'K′ 个 x 的最长区间，然后加上 num×Nnum \times Nnum×N 作为中间完整块的长度。 关键点在于：当 MMM 很大时，最优解一定由若干完整填满的 o 块加上两端部分块内扩展得到的连续区间组成。通过在 S+SS+SS+S 上运行滑动窗口（最多包含 K%cntK \% cntK%cnt 或 K%cnt+cntK \% cnt + cntK%cnt+cnt 个 x），可以求出跨越两个块边界时的最大长度，再加上中间完整块的总长度即可。 参考代码 T6 午枫的涂色方案 题意简述 一排 NNN 个座位，初始状态第 iii 个座位上的数字为 i mod 2i \bmod 2imod2，即 1,0,1,0,…1,0,1,0,\dots1,0,1,0,… 交替。每次操作可以选择两个位置 lll 和 rrr 满足 l+1<rl+1<rl+1<r，且 lll 和 rrr 上的数字相同，而 (l,r)(l,r)(l,r) 内的所有数字都与 lll 不同，然后将 (l,r)(l,r)(l,r) 内所有数字改为 lll 上的数字。给定目标状态 A1,…,ANA_1,\dots,A_NA1 ,…,AN ，问有多少种不同的操作序列（操作次数不同或某一步的 (l,r)(l,r)(l,r) 不同都算不同）能从初始状态变成目标状态，答案对 998244353998244353998244353 取模。 解题思路 首先无解条件：A1A_1A1 必须为 111（位置 111 永远不会被修改），ANA_NAN 必须等于 N mod 2N \bmod 2Nmod2（位置 NNN 也不会被修改）。否则答案为 000。 将初始序列视为 NNN 个长度为 111、颜色交替的连续段。一次操作选择三个连续段（左、中、右），其中左右颜色相同、中间相反，操作后三段的中间段变为左右颜色，三段合并为一段。因此操作只合并相邻的相同颜色段，且每次减少两个段。 最终目标 AAA 划分成若干连续同色段。每个段的长度必须为奇数（因为每次合并三个奇数长度段得到奇数长度段，从 111 开始只能得到奇数）。若任何一段长度为偶数，答案为 000。 对于长度为 L=2k+1L=2k+1L=2k+1 的段，它由 2k+12k+12k+1 个初始段合并而成，需要 kkk 次操作。其内部合并方案数为 f(k)=(2k−1)!!=∏i=1k(2i−1)f(k) = (2k-1)!! = \prod_{i=1}^{k} (2i-1)f(k)=(2k−1)!!=∏i=1k (2i−1)。 设最终有 ccc 个段，半长度分别为 k1,…,kck_1,\dots,k_ck1 ,…,kc （即段长为 2ki+12k_i+12ki +1），总操作数 K=∑kiK = \sum k_iK=∑ki 。不同段之间的操作可以任意交错，穿插方案数为多重组合数 K!∏ki!\frac{K!}{\prod k_i!}∏ki !K! 。 因此总方案数为： (∏i=1cf(ki))×K!∏ki!\left(\prod_{i=1}^{c} f(k_i)\right) \times \frac{K!}{\prod k_i!} (i=1∏c f(ki ))×∏ki !K! 预处理阶乘、逆元及 f(k)f(k)f(k) 即可 O(N)O(N)O(N) 计算。 参考代码