浅谈高级数据结构

这新头像框太棒了

我去，跟我名字太搭了 我C，我K，我K我K，520的这一天，大约6:10 AC君竟然给我的帖子点赞了，细节反复确认，发现确实是真的AC君，嘿嘿，我不仅喜欢认真负责的AC君，还喜欢不摆架子的AC君 小广告

完了，总想说四维（标题改成这样开心了吧）

为了不占用您的时间，如果您已经能对有关多维数组代码上的错误进行自查,我就不建议您看这篇 用无大用 无用也无大无用 的蒟蒻文章了 这里不做过多介绍。 引入理解主题的前言 三维介绍 其实都知道，三维是有x、y、z三个量，其中肯定有人想着“x，y是二维也就是平面直角坐标系的两个量，所以三维只是将平面加了一个z而已”注意，这段说辞的意思一般来说就是一个水平平面多增了一个高叫“z”，但是这是错的！在讲平面直角坐标系前，我们对于长方形、正方形，准确来说叫矩形的几何图形计算面积时会说“长乘宽等于其面积”但在往其他地方走一下可知：三角形叫高，是不是因为其所谓的宽（长）没有在这几何图形上，从而换了说法？ 三角形的那个没有在自己身上却进入计算的那一条边叫“高”（直角三角形除外，其高可以算作在一条直角边上），平行四边形也叫“高”（特殊的，长方形的高可以算作在一条边上），甚至是梯形也叫“高”（依旧有特殊） 那...矩形能叫“高”吗？其实从我们接触矩形的时候就不叫“长”与“宽”了，叫“底”与“高”，所以并不是换了说法，而是为了我们自身的理解叫成了“长”与“宽”。当我们开始接触三维，也就是立体几何图形时，方便后续理解，改回正确叫法：“底”“高”。 了解完这些，你应该会知道为何“x，y是二维也就是平面直角坐标系的两个量，所以三维只是将平面加了一个z而已”这段话是错的了吧，知道就看下一自然段，不知道继续看：“z”是我们常说的高，但在三维运用中，“z”只是二维上的高，“x”是二维上的底，那不用多说，“y”是啥？（以免还有人不知道，“y”是二维在不考虑平面直角坐标系中不存在的，也就是三维上的高） 跟我一样玩MC的小伙伴，在按下键盘上F3时，可以看见所处坐标，当你在不跳跃，只按下“w a s d”时，就会发现“x”与“z”坐标变化了，但“y”坐标始终没有变化（开自动跳跃的可以再去过一次清明节了），现在知道为什么了吧。 重头戏 四维 有过这方面知识储备的小盆友应该会知道，四维包含三个空间维度与一个时间维度，三个空间维度就是上文的“x z y”，既已理解四维，看下一自然段，不知的继续看：想象一个房间，这个房间里有一个盒子，过了一个单位的时间后，盒子变成了糖果，又过了一个单位的时间后，有一个不愿意透露姓名的小盆友一个瞬移进来迅速吃掉了糖果，又瞬移出去了，房间里甚都没有。又过了一个单位的时间，房间里莫名多出一个卡片。好，故事结束，当我们把这个房间里的状态以一个数组（列表）a以1开始来存储，那便是：a[1]=“盒子”，a[2]=“糖果”，a[3]=“NULL”(代表空)，a[4]=“卡”。这就是时间维度的存贮，一个单个单个的个体组成的一维时间维度，相当于一个0维的空间维度（一个点）被一个当把每个时间单位状态都记录下来的数组（列表）存了起来。若这个房间不再是一个一个的存，像第一个时间单位，不再只有一个盒子，而同时拥有一个盒子，一个袋子，设存储盒子这个位子的单独变化（盒子->糖->NULL->卡片）的数组（列表）为a1，若是袋子这个位子也在单独变化，则有一个a2数组（列表）来存储这个位子的变化，这就是两个时间线的变化量存储，但这里两个数组（列表）所表述的的都是这个房间里的变化，并且所记录位子也不重复，所以这里理应合并为一个数组（列表），一个2 * 4二维的数组（列表），但是表述的是一个时间维度与记录每个时间的两个位子状态的维度，而非“x”与“z”的维度。此时我们再延伸，这些位子有固定摆放顺序，不在只有两个位子，而是有四个位子摆成了2*2的样子，且每个位子与上述描述相同，那么这个a数组便改为三维数组（列表），同样是一个时间维度与一个“x”还有一个“z”组成的3维，而非“x”“z”“y”。最后，4个位子变成了8个，摆成了2 * 2 * 2的立体位子，且位子记录描述上同，就会是一个时间维度，与一个“x”和“z”还有一个“y”。再...我们第一次说的记录为a[时间]，则第二次为a[时间][x]，第三次a[时间][x][z]，第四次便是a[时间][x][z][y]。这就是我们的四维数组（列表）。恭喜你理解啦！（没理解？重看这一自然段“:(”） 别说了，ACgo网站是个编程网站，且c++用户居多（据我了解），所以四维空间该如何在DP代码中去进行理解呢？ 仔细看这四个数组（此乃c++数组，学P的理解成列表） 第一个相当于将一个 一个 的点变成一个 十个 的点，且这十个点连续； 第二个在第一个基础上，将每个 一个 的点变成每个 十个 的点，且这 每个 十个点连续； 第三个再在第二个基础上，将每个 一个 的点变成每个 十个 的点，且这 每个 十个点连续； 第四个同理。 简的来说第四个就是一个10 * 10 * 10的点阵，变成10 * 10 * 10的 长度为20的数组 阵 用处呢？ 在记忆化搜索中兴许有用 主要还是在DP（动态规划）上作每个状态量的记录。 ====================== ====================== ====================== 这里就举了理解四维的方法，这里再举5维的理解例子 （标题是“四维与自查多维DP代码的方法与理解”没说不能拓展） 简的来说 五维就是一个立体的点阵，变成立体的 面 阵， 前三个中括号代表10 * 10 * 10点阵，后两个中括号代表每一个点变成了20 * 20的面，所以这里来说就是“一个用20 * 20的面（不是吃的那个面）摆成的 10 * 10 * 10的立体阵列”（由于评论区搁那里讨论四维究竟是啥，我这里就不说五维是啥了，免得又起风波）（你这么理解，不再担心脑子在自查有关多维数组代码上错误时抽了。没懂？ 把这句话给AI，AI给你解释） ====================== ====================== ====================== 草草结束 希望这篇来自我自己的投稿能帮助到你理解四维空间转三维的原理来推论自己多维DP的代码原理以防报错后急着找不到从何下手 最后说一个东西，由于内容价值太小，就不单独发讨论了 在m=2时 与 其实是不等价的（不考虑时间复杂度，只考虑代码运行后的效果） 感谢您抽出时间观看完此文，若有错误，欢迎您在评论区留言，我会抽空回复的，谢谢

六一互动｜原来我从小就是个逻辑控？

🎈六一特别企划｜不是吧！原来我从小就是个逻辑控？ hi，AC狗友们 ，不是只有写代码才叫编程🧠 小时候玩过的那些游戏/玩具 ，可能早就偷偷给你种下了 逻辑思维的种子🌱 🕹️ 看到这些DNA动了没 🥇 Scratch小猫跳一跳 👉 原来“碰到边缘就反弹”就是if语句啊喂！ 🥈 Minecraft红石电路 👉 第一次手动实现“与门”，比数学课还早 🥉 Lightbot点亮灯泡 👉 用函数调用那关，脑子直接“叮”一声通了 …… 🎁 换你了！！！ 👉 你小时候玩过哪个 游戏/玩具 让你觉得“这好像在玩逻辑”？ 👉 有没有一个瞬间，让你突然觉得“我脑子转得快是因为它”？ 评论区直接写👇 格式不限，一句话or小故事都行～ 🎁 福利时间 活动截止后：符合活动要求的评论 * 点赞前6名 → 罐头 × 60 * 随机抽6人 → 罐头 × 20 ⏰ 即日起 至 2026.6.8 💬 评论区交出你的启蒙游戏～ 往期互动

语文默写的尽头竟然是数学！！！

rt。看到这张数学纸的神秘之处了吗？ 哎不是，你数学得统计哪来的南朝是宋齐梁陈？ rt。熟悉我的都知道（不熟悉的熟悉一下去），我们那个默写很难，老师会加非常多的东西进去，更何况是他的抄二默一！更是史诗级作业，给我整服了 那么，我们就没有什么办法了吗？（凹凸工坊除外） 最近！好的好兄弟陈遇舟告诉了我方法！他说只要准备其他科目的东西！混进去一点神秘的东西就好！老是问你，你就说掉出来了之前放的，最多叫你整理一下，你说摸完之后再整理就好了 然后！今天我试了一下，老师看了一下，问都没问就给我塞回去了，我也喜提过关，nice 推荐大家用乐谱搞，因为这样可以参杂的内容密度更多一些，不像数学写多了一眼发现，就算老师看出来了，你乐谱也可以说是这个主题的艺术，但是数学的话，只能说祝你好运 推荐大家也这么做一下，分享一下 地点：宁波市广济中心小学世纪院小区 班级：603 貌似有的人更喜欢旧版素材，我贴一下

CSP-J各年难度排行（补档失败QAQ）

紧急通知！我现在任何关于CSP-J的补档全会失败，计划紧急叫停！！！ 深表歉意，辜负大家的期望，虽遗憾，但是确实做不了 =( 我补了三次档，每一次都会变成null，明明提高组都好好的，但是普及就是不行，开了新帖子也没用 SO： 之后可能不会再做关于J组的排行了，但我依然会尝试重发，直到成功 我会将之后的重心大多数放在粉丝投稿（因为我自己确实也没有灵感了） 最后： 希望ACGO放过我，不然我真的要转到洛谷了=( 其他作品传送门： 其他作品点这里！椰丝CO的枢纽

AC商店

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这咋出了一个新头像？感觉有点糖啊 一天一个小广告

粉丝投稿/国内的编程网站排行

没错这里是鸽了5天才发的粉丝投稿，国内的编程网站排名！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本帖子为@雪提供灵感，感激不尽！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 观前提醒： 1. 粉丝也是把我当日本人整，这个真的是我目前做过最难的排名，无论是收集资料还是打分还是评价，每个都很费时间，因此资料疏漏很多，请谅解（若有补充可以告诉我awa） 2. 本次对比之前的排名AI使用量略有增加，因为资料含量太大，所以借助了AI帮助搜集和说明，但整个排名仍有85%为我独自完成 3. 出于长度上限和我的肝考虑，本次仅录入了前30名，并非全录入 4. 参与投稿必须先关注喵！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次耗时：58小时 肝炸了求点赞QAQ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 关注@椰丝CO，不错过任何一个排名帖子！ 资料来源：谷歌 夸克 博客园 CSDN Python中国社区 百度 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下面是我的其他作品传送门！： 椰丝CO的枢纽 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排名 平台 注册用户量 日活/月活等关键指标 题目/教程质量 适配人群 评分说明 1 GitHub ~1.8亿 日均约1400万访客 10 所有开发者、开源爱好者、学生、架构师 全球开发者总库，开源生态与个人技术品牌建设的核心，无可替代 2 Stack Overflow ~2900万 月访问量约5500万，社区活跃度受AI冲击有所下降 10 初中高级开发者、遇到具体Bug/技术难题的程序员 曾是最权威的“程序员维基”，近期受AI工具冲击，社区活跃度下降明显 3 MDN Web Docs 贡献者超4.5万 月活跃用户约1620万 10 Web前端开发者、需要查阅权威技术文档的程序员 Web技术的权威“圣经”，文档质量、准确性和用户体验均为顶级 4 GeeksforGeeks 超7500万 日独立访客约179万 9 计算机科学学生、编程初学者、求职面试者 计算机科学知识宝库，体量庞大，用户超7500万，是求职和打基础的好帮手 5 Kaggle 超2300万 月访问量约1280万 9 数据科学家、机器学习工程师、AI从业者、数据分析师 数据科学竞赛实战平台，核心理念是“以赛代练”，直接对标企业需求 6 CSDN 5100万 日活跃用户约235万，月访问量约9380万 6 中文开发者、编程初学者、大学生、初中级程序员 中文IT内容巨擘，流量巨大，用户达5100万，但内容质量......貌似参差不齐awa 7 知乎(科技板块) 暂无公开数据 月均订阅会员1430万，月活5000万+关注科技内容 8 各阶段开发者、关注技术深度讨论与行业趋势的人 高质量深度讨论的沃土，常有行业专家“出没”，适合系统化理解技术 8 LeetCode 全球估算超1200万(中国区超500万) 年代码提交量超1亿次 9 求职面试者、算法竞赛爱好者、想提升算法能力的学生 求职面试“刷题神器”，全球超1220万用户，程序员必备练兵场 9 Reddit (r/programming) 暂无公开数据 版块订阅数约686万 8 初中高级开发者、关心技术动态与全球开发者交流的人 全球开发者“茶水间”，讨论自由、信息前沿但氛围较松散 10 W3Schools 暂无公开数据 月访问量约7000万，年页面展示超30亿次 8 Web开发初学者、需要快速查阅教程的人 网页开发入门必读“活字典”，基础用户量极大 11 掘金 暂无公开数据 月访问量约1080万 9 前端/后端/AI开发者、关注前沿技术的中级程序员 国内高质量技术文章标杆社区，面向初中级开发者，内容前沿 12 freeCodeCamp 暂无公开数据 月访问量约1590万；GitHub Star超43.1万 9 编程自学者、转行人士、预算有限的学生 全球最大的免费编程实战社区，通过项目驱动学习 13 V2EX 75万 日活跃用户约4万 7 极客、创意工作者、全栈开发者、追求“Hacker”文化的人 中文极客创意乌托邦，专注于非典型技术话题的深度探讨 14 CodeWars 超300万 月访问量约180万 8 编程初学者、想通过游戏化方式练习编程的人、算法爱好者 游戏化编程挑战平台，通过“Kata”闯关，趣味性和用户体验很好 15 开源中国 (OSChina) 社区用户超2000万 Gitee平台开发者1350万，日独立访客约150万+ 7 国内开源贡献者、想寻找GitHub中文替代方案的人 国内开源生态核心枢纽，可替代GitHub的中文备选方案 16 洛谷 (Luogu) 超200万 题库超1.5万道题，累计评测超2.5亿次 9 信息学奥林匹克竞赛（OI）选手、ACM爱好者、算法竞赛初学者 国内信息学奥林匹克竞赛（OI）的核心根据地 17 牛客网 超900万 暂无公开数据 8 国内求职者、校招学生、需要笔试面试练习的人 国内求职一站式平台，校招神器，硕士以上学历用户占比超53% 18 Dev.to 超389万 月访问量约583万，日页面浏览量约50万 8 喜欢阅读/撰写技术文章、注重社区氛围的开发者 国际版友好写作社区，体验流畅，氛围包容 19 HackerRank 超1100万 月访问量约604.5万 7 求职者、面试官、企业HR、想评估自己技能水平的人 企业技术评估行业标准，服务于招聘场景，学习属性偏弱 20 思否 (SegmentFault) 近700万 暂无公开数据 8 喜欢技术问答的中文开发者、遇到具体中文技术难题的人 中文版“Stack Overflow”，专注于纯粹的技术问答 21 51CTO 1500-2000万 暂无公开数据 6 IT运维、网络工程师、想考取IT认证的传统IT从业者 老牌IT职业成长平台，内容偏向传统IT技能培训 22 SoloLearn 超3000万 暂无公开数据 7 零基础入门者、想利用碎片化时间学习编程的人、学生 移动端入门神器，课程轻量，适合非系统碎片化学习 23 CSS-Tricks 暂无公开数据 月访问量约174万 9 前端开发者、UI/UX设计师、想深入掌握CSS的人 CSS领域权威技术博客，内容极具深度，月页面浏览量达700万 24 Smashing Magazine 暂无公开数据 月访客超106万 9 前端开发者、网页设计师、UX工程师 专注于网页设计与前端开发的高质量杂志 25 博客园 注册用户超4万 日活跃用户超15万，百万级DAU(推测) 8 喜欢纯粹技术交流、想撰写/阅读深度技术博客的资深开发者 中文技术博客“净土”，以高质量文章著称 26 Hashnode 超200万 月访问量约39.4万 7 个人技术博客写作者、想建立自己技术品牌的开发者 免费博客托管平台，写作体验流畅，全球开发者使用。 27 SitePoint 约28.35万(免费用户) 月访客约60万 8 Web开发者、想通过电子书/付费课程系统学习的人 老牌Web开发与设计资源站，以高质量电子书和付费课程为主 28 AcWing 暂无公开数据 算法基础课参与人数超8.3万 9 算法竞赛选手、想系统学习算法与数据结构的人、面试准备者 算法竞赛备战利器，用户小众但质量高，付费课备受好评 29 CodeProject 近1000万 日独立访客约12.4万 6 有经验的开发者、想寻找特定代码示例/解决方案的人 历史悠久的开发者社区，资源略微陈旧 30 ACGO 暂无公开数据 社区约11.4万人讨论，竞赛参与人数>8232 7 中小学生、信息学竞赛入门者、初学者 新兴小众信息学竞赛OJ，用户体量较小 （ACGO牛B） 别忘了点赞！！！！

官方题解 | 挑战赛#31

挑战赛31题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 小午历险记之能量调节 入门 T2 小午历险记之宝石解密 普及- T3 小午历险记之古籍卷轴 普及- T4 小午历险记之星核碎片 普及- T5 小午历险记之蜂巢信标 普及/提高- T6 小午历险记之沙漠信标 普及/提高- T1 小午历险记之能量调节 题目大意 在一个大小为 MMM 的环形刻度盘上，刻度从 000 到 M−1M-1M−1，当前位置为 xxx，目标位置为 yyy，每次可以顺时针或逆时针移动一格，求最少需要多少次操作才能从 xxx 走到 yyy。 题解思路 由于刻度盘是环形的，从 xxx 到 yyy 只有两种走法：顺时针走或者逆时针走。顺时针的步数就是从 xxx 增加到 yyy 的距离，如果中途越过 M−1M-1M−1 就从 000 继续；逆时针则是从 xxx 减少到 yyy，如果减到 000 以下就从 M−1M-1M−1 继续。这两种距离都可以直接用取模来计算，分别是 (y−x+M) mod M(y-x+M)\bmod M(y−x+M)modM 和 (x−y+M) mod M(x-y+M)\bmod M(x−y+M)modM。实际最优方案一定是两者中较小的那个，直接输出最小值即可。整个过程只涉及常数次运算，时间复杂度为 O(1)O(1)O(1)，即使 MMM 非常大也完全没有问题。 参考代码 T2 小午历险记之宝石解密 题目大意 有 NNN 颗宝石，进行了 MMM 次解密仪式，每次仪式会同时激活若干颗宝石。需要判断是否对任意两颗不同的宝石 (u,v)(u,v)(u,v)，都存在至少一次仪式使它们同时被激活。 题解思路 由于 NNN 的范围很小，只有 100100100，可以直接用一个二维数组记录宝石之间是否“共现”过。初始化一个 N×NN \times NN×N 的布尔矩阵，表示任意两颗宝石是否在某次仪式中一起出现。对于每一次解密仪式，把其中所有宝石两两配对，在矩阵中标记为 truetruetrue。最后再枚举所有 1≤u<v≤N1 \le u < v \le N1≤u<v≤N，如果存在某一对没有被标记过，说明它们从未同时激活过，答案就是 No；如果所有宝石对都满足条件，则输出 Yes。这种做法直接模拟题意，复杂度在数据范围内完全可以接受。 参考代码 T3 小午历险记之古籍卷轴 题目大意 小午一开始有 NNN 本卷轴，编号任意。在开始研读前，可以反复进行“卖两本换一本”的操作。之后他要从第 111 卷开始，按顺序连续研读，问最多能连续研读到第几卷。 题解思路 可以把问题理解成：我们关心的是哪些编号的卷轴最终能被凑出来，而不是它们具体是怎么来的。只要某个编号最终能有一本，就可以用来研读。 先用一个布尔数组记录当前手中是否已经拥有某个编号的卷轴。读入初始卷轴时，如果编号已经出现过，或者编号大于当前可能用到的范围，这些卷轴都不可能直接用于研读，就当作“多余卷轴”，计入一个变量 sold，表示可以拿来卖掉的数量。 接下来用两个指针维护当前状态： L 表示当前最小缺失的编号，也就是下一本想要研读的卷号； R 表示当前最大的、已经拥有的编号，用来在必要时拆掉换资源。 循环中有两种操作方式： * 如果手里有至少 222 本多余卷轴，就可以直接“卖两本换一本”，把缺失的 LLL 号卷轴补出来； * 否则，只能从当前已有的最大编号 RRR 中拆掉一本，把它变成一份多余卷轴，再继续尝试。 当既无法合成新卷轴，又无法继续拆已有卷轴时，说明已经无法补出下一个连续编号，研读过程结束。此时 L−1L-1L−1 就是最多能连续研读到的卷号。 整个过程每本卷轴最多只会被处理常数次，时间复杂度是 O(N)O(N)O(N)。 参考代码 T4 小午历险记之星核碎片 题目大意 给定一个非负整数 NNN，把它看成一个二进制集合，要求输出所有非负整数 xxx，使得 xxx 的二进制中为 111 的位置全部包含在 NNN 的二进制为 111 的位置中，并按升序输出这些 xxx。 题解思路 把 NNN 的二进制中所有为 111 的位看成若干个可选的“位置”，题目要求的所有 xxx，本质上就是从这些位置中任选一些（也可以一个都不选）组成的所有子集。因为 NNN 中为 111 的比特位数量最多只有 151515 个，所以一共最多只有 2152^{15}215 种情况，可以直接枚举。 具体做法是先把 NNN 中所有为 111 的位的位置取出来，存到一个数组里。设这些位置一共有 kkk 个，那么用一个从 000 到 (1<<k)−1(1<<k)-1(1<<k)−1 的掩码来枚举所有子集。对于每一个掩码，如果第 jjj 位为 111，就把对应的位置加到当前数中，最终得到一个合法的 xxx。把所有生成的 xxx 存下来，排序后依次输出即可。由于总数很小，这样做时间和空间都完全没问题。 参考代码 T5 小午历险记之蜂巢信标 题目大意 在一个无限的六边形网格中，有 NNN 个被激活的单元，每个单元有一个整数坐标。如果两个激活单元能通过若干次“走到相邻的激活单元”互相到达，则它们属于同一个信标网络。要求统计这些激活单元一共能形成多少个互不连通的信标网络。 题解思路 这道题本质上就是在一个特殊邻接关系的网格图中统计连通块数量。每一个被激活的蜂巢单元都可以看成一个点，若两个点的坐标满足题目给出的六种相邻关系之一，就在它们之间连一条边。最终问题就变成：给定一个无向图，求连通块个数。 由于 NNN 只有 100010001000，可以先把所有激活单元的坐标存下来，再用一个哈希表把坐标映射到编号，方便快速判断“某个相邻坐标是否也是激活状态”。之后用 DFS 或 BFS 遍历图：维护一个访问数组，从每个尚未访问的点出发，搜索所有能到达的点，并标记为已访问，每启动一次搜索，就对应发现了一个新的信标网络。遍历结束后，搜索的次数就是答案。整体复杂度是 O(N)O(N)O(N) 级别，完全可以通过。 参考代码 T6 小午历险记之沙漠信标 题目大意 给定一张 n×mn \times mn×m 的网格地图，从起点 S 出发走到终点 T，可以上下左右移动。. 可以正常通过，# 不能通过，G 是检查点，整条路径中最多只能进入 一次 G，求最少步数，若无法到达输出 -1。 题解思路 这是一个带状态限制的最短路问题。普通的 BFS 只能记录位置，但这里还需要关心“是否已经用过一次进入 G 的机会”。因此把状态扩展为三维：当前位置 (x,y)(x,y)(x,y)，以及是否已经经过过 G。 用 d[x][y][k] 表示到达 (x,y)(x,y)(x,y)，且已经经过 kkk 次 G（k=0k=0k=0 或 111）时的最短步数。用 BFS 从起点开始扩展，每次尝试向四个方向走，如果遇到 # 就跳过；如果遇到 G，只有在当前还没用过（k=0k=0k=0）时才能走，并把状态转为 k=1k=1k=1；普通格子则直接走，状态不变。 最终答案是到达 T 的两种状态中较小的步数，只要有一种能到达即可。整个 BFS 过程中每个格子最多进队两次，时间复杂度是 O(nm)O(nm)O(nm)。 参考代码

谁懂拍毕业照的苦……

我真服了，昨天我们全年级拍毕业照，然后学校给我们整了一个空心的铁架子，就是那种用铁棍支撑起来的空心台阶(还必须横着走，不然就会掉下去)然后那摄影师还让我们在那架子上站半小时，腿都疼死了，自己在那发微信，然后稍微有一点声音就在那里吹哨子，搞得跟教官一样 大家有拍过毕业照的木

浅谈高级数据结构

吉司机线段树/历史最值 (ps：之前写过线段树总结，现在觉得这块内容放这个板块较为合适。) 很久以前用一知半解态度过的模板题，现在重新学习了下，不算难。 我的文章风格可能都有点刨根问底的感觉，理解的层次至少会阐述正确性（而不是说做法然后直接放代码）。 阅读门槛是需要知道线段树，标记合并。其实很低，如果势能分析看不懂也没关系。 PART1 区间最值操作 吉司机这个东西是可以在对数平方时间内维护区间最值修改的，操作如同： * 对 [l,r][l,r][l,r] 中的所有数执行 ai→min⁡(ai,k)a_i \to \min(a_i,k)ai →min(ai ,k)，其中 kkk 是给定常数。 当然上面的 min⁡\minmin 换成 max⁡\maxmax 也是完全可以的，我们先来阐明一下解决思路，再考虑时间复杂度的具体分析。 针对取 min⁡\minmin 操作进行讨论，另外的取 max⁡\maxmax 操作是完全对称的。在此基础上如果只需要查询最值则可以简单做到 O(nlog⁡n)O(n \log n)O(nlogn)，但这只是单纯的利用最值标记实现的简单线段树，并不是我们今天所讨论问题。所以，我们同时还需要支持查询区间总和等相关问题。 我们先明白查总和相对查最值更难做的原因，其实在于总和信息和取最值是没有结合律等优良性质的，刚刚所谈论的最值好做是因为操作和查询本身就支持信息合并。 更简单的说，单次修改中总和的修改量不能快速通过标记合并快速维护。所以我们必须考虑转化问题，这是线段树维护复杂信息的常见思路。本质在于让原问题变成更常见的问题，然后就可以很轻松地处理原问题。 一个简单的优化是跳过最大值小于等于 kkk 的节点，然而是不好直接做修改的。将问题转化为最小值大于等于 kkk 就做区间推平，特判叶子节点的想法。其实是完全不行的，因为最坏情况所有区间叶子都会被修改一次，修改总量完全没有保证，和暴力没有本质不同。所以我们需要做一个相对合理的批量修改方法。 换另一个可能更好的想法：维护最大值 maxnmaxnmaxn，最大值个数 cntcntcnt，严格次大值 sesese。修改的时候同样跳过最大值小于等于 kkk 的节点，并且当可以修改的节点满足 se<k≤maxnse < k \le maxnse<k≤maxn 就直接打删除标记 mul=k−maxnmul = k-maxnmul=k−maxn。这里表示将最大值区间加 mulmulmul，实际上效果相当于把最大值改成 kkk。维护一个标记 tagxtag_xtagx 表示当前节点 xxx 的最大值需要加多少就可以了，更新总和的时候贡献就是 tagx∗cnttag_x * cnttagx ∗cnt。 这里其实我们可以发现一件事情：最大值被单独列出维护了一个标记。这意味着如果还需要支持其他操作：比如区间加。则我们必须要维护两套标记：一个是针对最大值的，一个是针对除最大值以外的所有数。 其实底层原因也很简单，就是因为最大值对于的区间加标记不会作用于其它数上，就导致最大值所需要考虑的信息更多，当然如果这些信息不会影响到某种标记合并也可以分开维护。 首先考虑两个问题：答案正确性和时间复杂度分析。答案的正确性是比较显然的，接下来考虑时间复杂度的分析。这里其实直接分析单次修改是很容易绕弯子的，事实上证明用了一个高级技巧：势能分析。 在这里我会尽量用文字阐述下证明思路和过程，这里我们引入一个概念函数 W(u)W(u)W(u)，其满足以下性质： * 当节点 uuu 的最大值不等于其父亲节点的最大值时，有 W(u)=1W(u) = 1W(u)=1。 * 否则都有 W(u)=0W(u) = 0W(u)=0。 因为我们访问节点 uuu 需要的代价实际上是还需要考虑深度，换句话说总势能在 O(nlog⁡n)O(n \log n)O(nlogn) 量级，也就是 ∑W(x)×depx\sum W(x) \times dep_x∑W(x)×depx ，这里一个节点的深度可以粗略的看做 log⁡n\log nlogn。 然后我们考虑分析修改操作对势能总和的相对影响，这个所谓的势能实际上可以简单认为它等于程序总运行次数（也就是时间复杂度总量）。 至于根本原因，完全可以这样理解： * 考虑一个节点 xxx 满足 W(x)=0W(x) = 0W(x)=0，我们发现此时必然满足 maxnx<maxnfxmaxn_x<maxn_{f_x}maxnx <maxnfx ，此时 maxnxmaxn_xmaxnx 只能贡献到 sefxse_{f_x}sefx 。又因为此时暴力递归必有 sefx<kse_{f_x} < ksefx <k，所以我们知道 xxx 这个节点不可能会被暴力递归访问到，访问它的时间复杂度是 O(log⁡n)O(\log n)O(logn) 级别的，所以我们就依据这个性质设计势能函数值为 W(x)×depxW(x) \times dep_xW(x)×depx 。 同时，只需要聚焦于因为值域问题暴力递归处理节点的情况。其他情况就是普通线段树的时间复杂度。 回到势能分析中，当节点 xxx 的次大值 sesese 大于等于 kkk 时，我们显然有： * 两个子节点 lsxls_xlsx 和 rsxrs_xrsx 的最大值一定大于等于 kkk。 * 其中一定有一个孩子（不妨设为 rsxrs_xrsx ）的最大值小于 xxx 的最大值，否则如果两个子节点最大值都等于 maxnxmaxn_xmaxnx ，则次大值不可能 ≥k\ge k≥k。除非子树内有更深的分裂，这会在继续递归的儿子中被讨论，这里直接认为就是满足条件的。 当我们在该子树执行完操作并向上回溯后： * lsxls_xlsx 和 rsxrs_xrsx 的最大值由于被 kkk 截断，现在全部变成了 kkk。 * 父亲节点 xxx 的最大值也更新为 kkk。 * 此时，由于 maxnrsx=maxnx=kmaxn_{rs_x} = maxn_{x} = kmaxnrsx =maxnx =k，原本不相等的最大值现在对齐了。于是，W(rsx)W(rs_x)W(rsx ) 从 111 变成了 000。 势能减少了，严格来说减小的势能实际上是 deprsx=depx+1dep_{rs_x} = dep_x+1deprsx =depx +1。 由于 xxx 是暴力递归节点，虽然我们在当前层花费了 O(1)O(1)O(1) 的常数时间，但我们成功让一个深度为 depx+1dep_x+1depx +1 的节点的 WWW 归零，释放了 depx+1dep_x+1depx +1 的势能。同时也可以通过这个方面说明每一次暴力递归都可以在后续递归中找到某个节点，让它势能 WWW 归零来为时间复杂度的开销买单。 同时还需要分析区间加操作带来的势能变化，一共会拆成 log⁡\loglog 个节点，最坏情况下每个节点 xxx 的父亲 fxf_xfx 的另一个儿子的势能由 000 变成 111，总变化量量级至多为 O(qlog⁡2n)O(q \log ^2 n)O(qlog2n)。并且加标记下传不会影响势能 WWW 变化，增减势能的情况就上面两种。 势能总量为 O((n+q)log⁡2n)O((n+q) \log^2 n)O((n+q)log2n) 量级，单次操作会增加或消耗 O(log⁡2n)O(\log ^2 n)O(log2n) 的势能，总时间复杂度自然为 O((n+q)log⁡2n)O((n+q) \log ^2 n)O((n+q)log2n)。 当时吉老师的论文如果我没记错的话是修改的势能分析错判为 O(log⁡n)O(\log n)O(logn)，并且其实势能增量卡慢其实不简单，所以实际表现和常数大一点的 O(nlog⁡n)O(n \log n)O(nlogn) 没什么区别。 PART2 历史最值 这块部分严格来说和最值修改完全没关系，一个位置的历史最值的定义是该位置上的数在所有时刻中的最值。相对吉司机要简单很多。 同样的，我们考虑历史最大值的做法，记 AiA_iAi 表示当前时刻位置 iii 上的值，BiB_iBi 表示所有时刻位置 iii 的最大值。实际上我们是在维护的历史最大值可以看做一个前缀时间内数的最大值。 首先我们要维护的区间历史最值显然只会被区间最大值更新，换到线段树上就是考虑标记的合并与迭代。只维护加标记 tag1tag_1tag1 的想法是错误的，原因在于标记可能经过多次合并，实际意义就是加了很多次数。我们一定会考虑维护 tag1tag1tag1 的历史最大值，记作 tag2tag2tag2,用它来更新答案。 由于标记下传后贡献已经清除，所以本质上我们只是在维护： * tag1tag1tag1 表示上一次下传标记后到现在的加标记。 * tag2tag2tag2 表示上一次下传标记后到现在的时刻中，tag1tag_1tag1 的最大值。 同时记最大值为 m1m_1m1 ，历史最大值为 m2m_2m2 。考虑下传节点 xxx 的标记： * tag1sonx→tag1sonx+tag1xtag1_{son_x} \to tag1_{son_x} + tag1_xtag1sonx →tag1sonx +tag1x ，加标记合并。 * tag2sonx→max⁡(tag2sonx,tag2x+tag1sonx)tag2_{son_x} \to \max(tag2_{son_x},tag2_x+tag1_{son_x})tag2sonx →max(tag2sonx ,tag2x +tag1sonx )，理由很简单，此时 xxx 标记对 sonxson_xsonx 的影响在于 tag1xtag1_xtag1x ，而由于我们维护的 tag1xtag1_xtag1x 实际上是一个时间点的加标记，换句话说是落在该节点的加操作之和。本质上我们应该遇到一个操作就直接下传儿子修改，但是为了复杂度我们选择了延迟下传，所以就会选择使用 tag2xtag2_xtag2x 更新。正确性只需要考虑 tag2xtag2_xtag2x 合法（一定是某个时刻的 tag1xtag1_xtag1x ）并且最优（根据定义它最大）。 然后依据历史最大值标记的最大贡献 tag2x+m1(x)tag2_x+m1(x)tag2x +m1(x) 取更新 sonxson_xsonx 的 m2m_2m2 即可。整个过程的设计思路比较自然。 PART 3 结合问题 模版题把两个问题合并在了一起，实际上做法还是依据上述思路维护线段树信息，之前在第一部分我也顺便提到过：由于吉司机把最大值单独考虑，所以要针对最大值和非最大值设计两种标记组。 什么意思，就是实际上我们需要维护四个标记 tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4，但是其实是因为 tag1,tag2tag1,tag2tag1,tag2 服务于区间最大值（定义同第二部分），其余的 tag3,tag4tag3,tag4tag3,tag4 服务于其余所有数，本质上只是迫不得已维护了两套一模一样的标记而已。 这段代码是在处理节点 xxx 加入的四个标记分别为 v1,v2,v3,v4v1,v2,v3,v4v1,v2,v3,v4 后的影响。首先更新和，考虑最大值个数和其余数个数（里面 clenxclen_xclenx 是节点 xxx 代表的线段树区间长度）和标记组合即可。剩下的都是刚刚推导里面就有的，注意这里需要判断次大值是否存在的情况。 然后考虑标记下传函数： 这段代码考虑了 W(sonx)W(son_x)W(sonx ) 的情况，也就是说我们需要考虑某个儿子的最大值是不是节点 xxx 的最大值，如果不是则不需要考虑最大值标记信息不同带来的影响。因为下传的 tagtagtag 是以节点 xxx 的视角设计的，下传到 sonxson_xsonx 需要变换成 sonxson_xsonx 的视角，也就是说如果 $son_x $ 本身对最大值没贡献则会被自动规约到 tag3x,tag4xtag3_x,tag4_xtag3x ,tag4x 的管辖范围。 关键代码如下： 当然如果操作需要支持取最大值或者最小值，维护思路完全一样。但是值得注意的一点是注意特判重复贡献。理论上维护三套标记的话其中两套分别是为最大值和最小值服务的，但是如果一个数同时是最大值和最小值需要特别判断。除此之外，也需要考虑最大值同时是次小值，最小值同时是次大值的情况（不然非最值标记会重复贡献）。 总而言之这是一个相对高级的线段树技巧，但是理解起来也不是特别困难。