广度优先搜索求最短路径 模板题

故事接龙-重开

以前那个没用了，全被他们的图片占了！ 这次来重新接龙！！ 如果发图片，联系AC君 另外禁止给评论点赞！ https://www.acgo.cn/application/1815726290803429376👈团队

互动# ：你最喜欢的动漫角色是？

🚀互动#10 ：你最喜欢的动漫角色是？ 😎二次元世界里，总有很特别的角色。如鸣人追逐梦想，如祢豆子温柔守护，如温迪洒脱编梦…… 🎤参与方式：在评论区留下你的本命角色名字，以及为什么？是其精神鼓舞，还是性格共鸣…… 🎁 话题奖励：随机抽取符合参与规范的三人获得随机周边奖。 ⏰ 话题时间：截止时间2025年1月13日

码上开聊VOL.4-陈家俊

码上开聊VOL.4 🎉 欢迎踏入「码上开聊」Vol.4！本期访谈，我们将走近一位满怀热忱、年仅初一的编程新星—— 陈家俊（社区昵称：🐱‍🚀）。自 2022 年 3 月开启编程学习之旅，短短两年间，他一路“披荆斩棘”，收获诸多荣誉。这位来自广州天河区的少年，不仅在 “ACGO竞赛排行榜”常年前10，还组织着一个超 300 人的强大团队——天之神团队！此刻，就让我们一同走进他拼搏奋进的编程世界，探寻背后的精彩故事吧！🐱‍🚀 初一少年征战 ACGO 🚀 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 🎉 个人档案 * 姓名：陈家俊 * 年级：初一 * 坐标：广州天河区 * 兴趣爱好：羽毛球、围棋、魔方、编程 * 入站时间：2024 年 4 月 * 社区好友：Charles Leclerc * 获奖经历： * 第一次考 CSP-J，复赛 315 分 * ACGO “飞翔杯”第一届季度赛（提高组）三等奖 * 围棋职业 4 段 * 社区主页：ACGO 个人主页 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 高能访谈 > 💻 编程经历 Q1：何时开启编程学习之路？至今坚持了多久？ 🐱‍🚀：2022 年 3 月踏上编程学习征程，到现在已经坚持 2 年啦。 Q2：你是通过校外机构还是校内信奥编程队学习编程的呢？ 🐱‍🚀：主要依托校外机构，像小码王就很不错。今年暑假参加了小码王的 X02、X03 夏令营，结识超多编程小伙伴，还学到海量知识，这对我 CSP-J 考出 315 分助力不少。 Q3：家人对你的编程学习持怎样的态度？ 🐱‍🚀：家人可支持我学编程啦！哪怕每天学业繁重，他们也会保证我至少有一个半小时投身编程。家人的这份支持，让我对编程的热爱愈发炽热。 Q4：ACGO 上哪道题让你印象极为深刻？原因何在？ 🐱‍🚀：A296.体育课。这可是我接触循环和判断素数的“启蒙题”，帮我开启新知识大门。 > ✍️ 学习方法 Q5： 在编程题目上遇到过哪些难题？又是如何攻克的？ 🐱‍🚀：我会精心挑选适合自己的题目，每天坚持做 10 题以上。 除了ACGO，给大家推荐几个刷题好去处，AtCoder，题目丰富、比赛众多，而且是纯英文界面，能顺便练练英语；还有力扣，界面美观、功能齐全。 Q6： 你编程的“内驱力”源自何处？ 🐱‍🚀：“内驱力”主要有以下几点： * 1. 好奇心和探索欲 - 我热衷于探索各式各样的题目及其背景，这股劲儿推着我不断深入学习编程。 * 2. 成就感 - 每攻克一道曾让我绞尽脑汁的难题，内心涌起的喜悦与成就感，都会让我对编程的喜爱更上一层楼。 * 3. 创造力 - 平日里，我喜欢动手制作小游戏，像现在正用 easyx 库捣鼓的贪吃蛇小游戏，创作过程中的欢乐，化为我内心深处的“内驱力”。 * 4. 社区与合作 - acgo 搭建了诸多与人合作的平台，让我学会与人交往，在题库中不断刷题，使我对编程的兴趣日益浓厚。 * 5. 个人目标与职业发展 - 我的梦想是成为一名卓越的编程员，这促使我在编程学习之路上奋力奔跑。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 🌟 关于天之神团队 Q7：快给大家介绍介绍你的团队吧！ 🐱‍🚀：天之神团队超自由的！目前有 312 人，旗下联盟和附属团队一共 38 个。我们每个月都会举办一场自创题竞赛，前三名能升职，只要参赛就有小奖励拿。 Q8：团队未来有啥规划呀？ 🐱‍🚀：打算把团队壮大到 500 人规模，组建完备的竞赛出题组、宣传组等，全力保障每次竞赛的高质量，还要进一步加强与其他团队的合作。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 📖 业余爱好与未来目标 Q9：除编程外，你还有哪些兴趣爱好？ 🐱‍🚀：我超爱羽毛球、围棋和魔方。围棋我已经达到职业 4 段水准，其他爱好就是课余放松的“良方”。 *图片由 AI 生成 Q10：对未来有什么规划呢？ 🐱‍🚀：学习上希望能冲进年级前五，编程能力也要持续“升级”，当然啦，要是生活里作业能少点就完美咯😂。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 访谈结语 如果你也钟情于编程，快来和陈家俊一起加入 ACGO 吧！在这里刷题、探讨、交流经验，携手在编程的奇妙世界里不断进阶！ 🎤 特别感谢 本次采访由 ACGO 外派记者 Popcorns_FMD 首度参与并圆满完成，采访对象的甄选与关键问题的拟定均出自其手，文章内容则由 AC 君 进行补充，润色与排版。👏 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往期访谈

反原联盟

官方网站 加入团队 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

互动#9｜2024结果清单

🚀本周互动：2024结果清单 😎2024 年的进度条即将拉满，这一年里你收获了怎样的结果清单呢？ 🎤成果剖析区 列出清单：列出清单：无论是友情、掌握的学识或技能、习惯养成、看过的书……皆可一一罗列。 🎁 话题奖励 抽取三人获得ACGO随机周边 ID 昵称 3250007 复仇者_—-开心超人.雪恨报仇 4038353 zsy 2166210 ༺ཌༀ赵云·卡布曲琦饼干ༀད༻ ⏰ 话题时间 截止时间 12月29日 获奖公布12月30日 快来晒出你的 2024 成果清单，与大家一同见证成长与收获！😎

巅峰赛 #16 全题解！！！

T4的题解有误，现已重写. 我们帅童玩家也是站起来了好吧（澄清一下，榜三不是我小号） 报一下个入难度：红 橙 橙/黄 黑蓝 绿 绿. T1 用 map 记录每个数字出现的次数，然后按题意判断. T2 每次取出第一个字符放到最后一个，判断是不是回文即可. string没有pop_front有点烦…… T3 我们可以用一种新型的记录方法，也可以记录到所有的子串. 例如 abcadcbabcadcbabcadcb： 遍历到第 111 个字符，l=1,r=1l=1,r=1l=1,r=1：将 aaa 加入字符串，并增加 111 个子串： aaa. 遍历到第 222 个字符，l=1,r=2l=1,r=2l=1,r=2：将 bbb 加入字符串，并增加 222 个子串：b,abb,abb,ab. 遍历到第 333 个字符，l=1,r=3l=1,r=3l=1,r=3：将 ccc 加入字符串，并增加 333 个子串：c,bc,abcc,bc,abcc,bc,abc. 遍历到第 444 个字符，r=4r=4r=4：由于已经出现过了 aaa，所以第 111 个字符就不能要了，令 l=2l=2l=2. 此时可新增 333 个子串：a,ca,bcaa,ca,bcaa,ca,bca. 遍历到第 555 个字符，l=2,r=5l=2,r=5l=2,r=5：将 ddd 加入字符串，并增加 444 个子串：d,ad,cad,bcadd,ad,cad,bcadd,ad,cad,bcad. 遍历到第 666 个字符，r=6r=6r=6：由于已经出现过了 ccc，所以第 2,32,32,3 个字符就不能要了，令 l=4l=4l=4. 此时可新增 333 个子串：c,dc,adcc,dc,adcc,dc,adc . 遍历到第 777 个字符，l=4,r=7l=4,r=7l=4,r=7：将 bbb 加入字符串，并增加 444 个子串：b,cb,dcb,adcbb,cb,dcb,adcbb,cb,dcb,adcb. ∴\therefore∴ 共有 202020 个不含有重复字符的子串. 翻译成代码如下： T4 为了方便表示，我将以 xxx 开头，yyy 结尾的子串数量称为 {x,y}\{x,y\}{x,y}，数组 aaa 中大于数 xxx 的个数称为 a.LB(x)a.LB(x)a.LB(x)，即lower bound. 个人认为本次巅峰赛最难的一题！ 认真读题，可发现题目实际让我们找的是如下的代码： 首先，我想到两个块合并只需要把左右两个块的 {x,y}\{x,y\}{x,y} 相加再加上第一个块内 xxx 的数量乘第二个块内 yyy 的数量即可. 于是我轻松地打了个线段树代码： 然后内存爆了. 后来我尝试用分块做，TLE了. 最后我使劲想想想，终于想出来了： 我们不需要维护整个线段树，真正需要维护的只是 676676676 个结果. 我们可以换个角度考虑，如aababbaababbaababb，将第 555 个字符改成 aaa： 先统计负贡献： 1. 在前四个字符与第五个字符的关系中，{a,b}−=3\{a,b\}-=3{a,b}−=3，{b,b}−=1\{b,b\}-=1{b,b}−=1. 2. 在第六个字符与第五个字符的关系中，{b,b}−=1\{b,b\}-=1{b,b}−=1. 再统计正贡献： 1. 在前四个字符与第五个字符的关系中，{a,a}+=3\{a,a\}+=3{a,a}+=3，{b,a}+=1\{b,a\}+=1{b,a}+=1. 2. 在第六个字符与第五个字符的关系中，{a,b}+=1\{a,b\}+=1{a,b}+=1. 我们发现，如果把这个字符串拆开，分为 aaa 字符串与 bbb 字符串： 那么贡献就与 555 在 aaa 字符串与 bbb 字符串的相对位置，即 ∑i∈ba.LB(i)\sum\limits_{i\in b} a.LB(i)i∈b∑ a.LB(i) 有关. 其它的字符串也有这个性质，自行验证. 可以亮代码了……吗？ 等等，还有两件事没讲清楚. 1.如何快速求 a.LB(x)a.LB(x)a.LB(x): 如果按正常的数组处理的话，修改时间复杂度就得退化至 O(n)O(n)O(n)； 而 setsetset 只会给你返回迭代器，转换成数值又得花费 O(n)O(n)O(n) 的时间. 怎么办呢？ 机智的我想到了用树状数组模拟数组！只要每次加入元素在该元素的下标增加 111，删除元素在该元素的下标增加 −1-1−1，那么查询某个下标的结果就是 a.LB(x)a.LB(x)a.LB(x)！ 使用这种方法也可以以 O(nlog⁡n)O(n\log n)O(nlogn) 的时间复杂度求得一个数组的逆序对. 2.初始化时间复杂度问题： 确实，通过上面的办法可以让修改变为 O(log⁡n)O(\log n)O(logn)，查询变为 O(1)O(1)O(1)，但是要初始化. 而如果按照上面的代码初始化，时间复杂度是 O(n2)O(n^2)O(n2)！ 没关系，稍微推导一下，就可以推出 {x,y}=∑i∈yx.LB(i)+(i∈x)\{x,y\}=\sum\limits_{i\in y} x.LB(i)+(i\in x){x,y}=i∈y∑ x.LB(i)+(i∈x). 该题代码如下： T5 模板题，参考区间根号题. 我们发现最多只会运算 350350350 次，所以 O(350n)O(350n)O(350n) 是完全可以的. 具体做法：维护一个线段树，记录区间内 111 的个数，修改时如果发现有一个子树内的元素都为 111 就不搜了；查询直接按普通线段树做. 由于这个算法是自顶而下的，所以就不能用重口味线段树了. T6 一开始没读题就0帧起手，写了个bfs找环+Floyd算法. 直到我看到了：不会重复经过同一个车站. 天塌了70+行的代码白写了 但是这个提示也带给我了一个好消息：消耗的时间最多也不会超过 151515. 这就让我想到了最短Hamilton路径的解法：状压DP. 巧了，在这题也同样适用！ 我们弄个dp，dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示从 iii 出发，第 kkk 个状态，最后一个点为 jjj 是否可能实现. 然后枚举每个时间和所有点，判断当时间为 iii，选取 jjj 点作为车站是否可行.

信奥系列直播第5期｜主讲人：胡扬帆

✨ 主讲人简介 本期嘉宾是西安交通大学在读的胡扬帆，她获得过国际大学生程序设计竞寒CPC杭州站 金牌，亚洲与太平洋地区信息学奥赛 APIO 金牌 等奖项。 ✨ 直播亮点 * 女生到底适不适合学信奥 * 女生在信奥中的独特优势 * 女生学信奥的策略和建议 直播时间为本周五（12月27日）19:00 - 20:30，扫描二维码关注公众号即可预约直播，快来参与。 点此了解信奥系列直播>>

COCR-Div.4入门赛#1预告

若有想要贡献题目给COCR组委会（代码修炼手册）的请填写这个表单。 > 团队排位申请（天之神&代码修炼手册团队需要填写）：这里 由代码修炼手册团队主办、天之神团队承办的COCR-Div.4入门赛#1将于2025年1月1日10:00开始，持续至2025年1月5日22:00，共5天。竞赛参赛网址如下：报名网址 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次竞赛题目为Div.4入门赛难度，主要考察的算法有：模拟枚举、二分贪心、素数筛优化、前缀和差分、中学数学、递推递归、深广搜、最短路、线性/背包动态规划、基础数据结构运用等。竞赛的目的是训练普及选手的代码实现能力、题目理解能力、处理问题能力，并巩固选手的基础算法知识，对学习过程中的易错点加重强调。 竞赛的奖励包括： 团队奖励： 1.【仅限代码修炼手册团队成员】获得代码修炼手册团队等级晋级 2.【仅限天之神团队成员】获得天之神团队等级晋级 3.竞赛成绩获得前 333 名的选手（任何团队）可获得由代码修炼手册团队颁发的电子版证书一份 官方奖励： 盲盒！ 快快报名吧！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 你网上冲浪了吗？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 因为数学，所以诞生了万物。数学，是科学之母。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 万物皆有它们的规律，只要能够找到规律，一切问题都能迎刃而解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 环境影响生物，生物也影响着环境。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 不要小看123456789，它们共同构建出了数学王国的天地。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 森林里有邪恶的大灰狼，小动物们快抓紧保护好自己啊！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ （以上图片均来源于AI作图及网络）

ACGO欢乐赛#36 题解

前言： 现在欢乐赛真的太水了。。。本人萌新都已经AK两次了 第一次写题解哈，如有不足请指出！ 实在不会搞链接，不好意思不能让大家立刻看到题目 贺上前十！ T1：求一个负数的绝对值 简单到爆炸，注意求绝对值的函数为abs() C++代码如下： T2：倍数问题 正常题，求一个数是否是4和6的倍数，用取余符号(%)即可,同时提供另外一种解题思路，4和6的最小公倍数为12，也可以用n%12==0来解。 C++代码如下： T3：数组元素和下标的和 这题算比较抽象的题反正我是不知道我怎么写对的，注意下标从1开始，输入和循环判断时都要把i的初始值定义成1，用a[i]加上i的值再依次输出即可，要加空格 C++代码如下： T4：交换字符 有一点难度，是奇数下标，解题思路就是输入两个字符串，遍历一下，i的值每次要加2，再用swap()函数进行交换即可不得不说这swap就是好用啊 C++代码如下： T5：二维数组问题 这题是真的良心啊，都把条件给我们了，不用多说了吧，记得定义一个sum变量存放边缘数组的和哈~ C++代码如下：（不知道为啥代码颜色成这样了@Macw07帮忙康康可以咩） T6：最大公约数 压台题也不过那样吧。。。需要运用辗转相除法，可以定义一个函数哈，最后先两两比较出两个最大公因数，最后用这两个数再辗转相除就可以了 C++代码如下： 我因为熬夜写题解已经被麻麻骂了，给个周边吧AC君大佬！！！

信奥系列直播第7期｜主讲人：李书润

点此了解信奥系列直播>>