听说津津为课程烦恼 金明一家住进了新房 听说丁丁玩数字游戏 火柴棒能搭出新天地 听说校门外正在砍树 大家一起做靶形数独 听说旅行者在赚差价 潜伏者正在破译着密码 只有无尽的代码知道 津津摆脱了学习的烦恼 金明开心地走进商店 挑选着书桌和电脑 总有一种算法能够让你成功拿到分 无论是贪心还是动规 或者将答案二分 思如泉涌掀起波涛 又汇成一个新的算法 让所有TLE 所有MLE 激励着我们前行写代码 听说同学们在玩推理 小Z的袜子总配不齐 听说两人在挑选客栈 火星上有条能量项链 听说陶陶在采摘苹果 一只青蛙要从河边过 听说推销员走入胡同 杰瑞爬进了奶酪的小洞 只有无尽的代码知道 同学们男女配对练起了舞蹈 小Z把他的袜子找到 AK了无数机房 屏幕在深夜微微发亮 思想在那虚树路径上彷徨 *面的向量交错生长 织成 忧伤的网 剪枝剪去我们的疯狂 SPFA 告诉我前途在何方 01 背包装下了忧伤 笑颜 洋溢脸庞 键盘微凉 鼠标微凉 指尖流淌 代码千行 凸包周长 直径多长 一进考场 全都忘光 你在 OJ 上提交了千百遍 却依然不能卡进那时限 双手敲尽代码也敲尽岁月 只有我一人 写的题解 凋零在 OJ 里面 Tarjan 陪伴*连通分量 生成树完成后思路才闪光 欧拉跑过的七桥古塘 让你 心驰神往 队列进出图上的方向 线段树区间修改求出总量 可持久化留下的迹象 我们 伏身欣赏 数论算法 图论算法 高斯费马 树上开花 线性规划 动态规划 时间爆炸 如何优化 我在 OI 中辗转了千百天 却不让我看 AK 最后一眼 我用空间换回超限的时间 随重新编译 测完样例 才发现漏洞满篇 原来 CE 是因选错语言 其实爆零 只因忘写文件 如果标算太难请坚定信念 不如回头再看一眼题面 以那暴力模拟向正解吊唁 蒟蒻的蜕变 神犇的出现 终将与 Au 擦肩 屏幕在深夜微微发亮 我心在考场 评测姬状态 CE Compile Easily 轻松通过编译 RE Run Excellently 完美地运行 TLE Time Limit Enough 时间充裕 MLE Memory Limit Enough 内存充裕 OLE Output Limit Enough 输出充裕 UKE United Kingdom Error 英国错误 WA Wonderful Answer 好答案 AC Answer Coarse 粗劣的答案

我往城堡更深处走着，有一条很长的走廊，里面被黑暗笼罩着，显现出一种恐怖与诡异。走廊的窗户被黑布照着，透不进来一点灯光。我慢慢地走着，走廊好像永无尽头，我很疲倦，但我知道，我要报仇，我要希望。我的朋友们不都是丧命在恶魔之手吗？他们的命不是命吗？我更加坚定向前走着……我不敢往边上看，闪耀的金色墙壁在黑暗的走廊中也会暗淡，呈现出一种死气沉沉的感觉。 不知过了多久，我看到了光亮，它像一把犀利的宝剑一样刺向黑暗的走廊，我看到了一个极其华丽的大堂：各种宝石砌成的墙壁反射着灯光，金色的地板闪耀着我很久都没有看见过的金光，像是晌午的阳光……一把很大的椅子上坐着一个人，他的左右都有侍卫，他睁开眼睛“你是谁？你为什么” “我是杀手四号，我认为我有新的任务。“ “行，你是想要彻底灭除人类吗？” “不是，我希望，我能拯救人类！我看不惯为了你而惨死的人。” “你以前一直同意和我一起消除人类，你忘了吗？” “我没有说过，也永远不会说，我 正是你一直要追杀的人——狗狗！” 我看到窗外灰蒙蒙的天，映衬这宫殿里闪着金光的墙壁，和恶魔充满畏惧的眼神。我直直地站在宫殿的中央，凝视着恶魔和他的侍卫：“我 就是你们一直要追杀的人——狗哥，今天我就要实行我的使命，让人类的太阳破云重现！” 我用力冲向恶魔，我身上没有利剑，但是我知道，只要有着一颗复仇的心，就一定能胜利。正在我接近恶魔的一瞬间，他的眼睛慢慢变小，身子缩成一坨，变成一只老鼠逃了。 我打量着四周，这个宫殿里空无一人，但是我听到了一点声音：他们像是地底下最深处的力量在嘶吼，每一声都拉着我的心弦。我像一个小小的门走去…… 我打开了门，里面放着一个大笼子，笼子的银色柱子在窗外微弱的灯光下反射着，里面一个个人都在尽力的嘶吼着，他们像地底下最深层的力量在震动：他们就是那些被清除的同学！我要拯救他们，他们是无辜的，可恶的恶魔，居然把他们关起来了。我看着笼子门上的那把锁，上面写着一行字：**如果你是狗哥，请用你的生命还他们自由！这行鲜红的字，深深的刻在我脑海里，刻在我的心里，是的，我会去做的！ 我慢慢按下了确定按钮，银白色的笼子慢慢打开，里面的同学像蜜蜂一样奔跑出来，那一刻，我感觉到了我在这个世界上存在的意义，那是一种非凡的感觉，一种快乐的感觉，一种无法描绘的感觉…… 我看到恶魔的城堡像一阵风一样慢慢消失，消失在那云朵的尽头里，那一刻我看到了世界上最美的景色：同学们正欢快地在操场上玩耍。我的心充满了一种不可描绘的感觉，它像火炉一样温暖着我的内心，我微笑这，看着这属于我们最美丽的阳光：对，那是人类的夕阳啊，是属于我们的夕阳。我躺在操场上，在我生命的最后一刻沐浴着这许久没有见到的阳光……对，阳光不再遥远，梦想不再缥缈，我第一次与世界感觉那么近，我的心柔软了，我的梦实现了……但是我的身体慢慢透明，像烟雾一样，随着风飞去…… 夕阳豪迈地吧周边的云彩染的火红，像是一幅画。太阳慢慢地落下去，我不伤心，因为它明天还会升起来的…… 已完结，下一期：远征

ACGO备赛专区的GESP C++ 202506 7级，题目抄录有误，分别为内存限制及样例，如下图： 下面为官网原题截图： 望AC君更正！

你说得对，但是 CSP-J/S 2025 是由 CCF 草台班子委员会开发的一款报错游戏，玩家需要在游戏中猛击 kkk 次以 cnt_broken eggs\mathtt{cnt\_broken\ eggs}cnt_broken eggs，并且避开重复两个第 33 题的风险。你需要判断谁是精明谁是糊涂，并且若你没有 have no egg\mathtt{have\ no\ egg}have no egg 便会在游戏最后三分钟提示你 solve\mathtt{solve}solve 函数没有传参和没有定义 nnn 和 kkk 变量（没有分号）。意识到这一点玩家都会想起来家里斥巨资开的工厂有一个生产线有缺陷，只好花了一个无符号 32 位整数能存的钱并做了道黑题才修复了生产线。

谁能告诉我GESP四级荒地开垦怎么做！！！求解，请问AAA混泥土批发ppl哥（ACGO）/pipilong（洛谷）你会做吗

acgo有人看凹凸世界吗，有的就和我互关吧。不看的就赶紧入坑

在寂静的夜里，少女的哭泣声十分十分明显。她的眼眶通红，头发凌乱，眼泪如断了线的珠子滴了下来。眼泪滴到一张合照上，慢慢浸透。不知不觉中，她睡了过去。 三年，那个吵吵闹闹的班级已经毕业了，温祁对姚弋的暗恋被埋藏在了心里，一句“我喜欢你”或许这辈子都说不出去了。不知过了多久，温祁在恍惚间被一个很吵的电子音吵醒了，她以为自己是伤心过度所以幻听了。 欸！醒醒！快醒醒！......

欸！醒醒！快醒醒！...... 温祁缓缓睁开有些肿的眼睛，面前有一个蓝白相间的小机器人。那个小机器人像个长了四肢的球，在温祁面前蹦蹦跳跳，嘴里不断的叨叨着什么。 ”你终于醒了！我是你的系统。“这个自称系统的东西高兴道。 ”系统？骗人的吧。“温祁疑惑道。 ”才没有！除了我的主人以外没有人能看到我，不信你就去试试。“ 温祁看着这个”系统“，出门走到大街上。 大街上人来人往，没有人注意到温祁，温祁见状又试探道”他们真的看不到你？" "哼，见识到本系统的厉害了吧。“系统骄傲道。 看了看周围人的反应，温祁思考了一下，问道：“既然除了我以外没有人能看见你，那我和你说话别人应该也听不到吧。” “准确来说，绑定后我们可以用意念交流，这样就没有人能听到了。所以......” 温祁没有回答系统，转身回到了家里。至少，她现在相信了这个系统是真实存在的。 -- 家里，温父温母对自家女儿的行为感到担心。他们自然也知道温祁喜欢的人出国了，可是这件事，他们也无能为力。 良久，温父叹了一口气默默回房了。 -- 脱离了悲伤的情绪后，温祁的脑子清醒了很多，面对系统她还有很多问题。 回到房间，温祁锁上房门，眼神晦暗的问”你的目的是什么。” ”啊？目的？哦！我想起来了！现在你应该相信我了吧！只要你和我绑定我就可以帮你实现一个愿望，前提是你要帮我攻略一个人。“ ”愿望吗....."

C++ 快速输入方法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 序章、目录 > 第一部分：总领全文 > > > 第二部分：方法详解 > > > 1. 优化标准输入流CIN > > > > 2. 使用 C 语言的 SCANF 函数 > > > > 3. 批量读取缓冲区 > > > > 4. 使用快速 IO 库 > > > > 5. 使用自定义函数 > > > 第三部分：速度对比 > > > 第四部分：注意事项 > > > 第五部分：后记 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、总领全文 感谢北大西洋公约 · NATO，没有他就没有这篇文章。 因为我看不懂他的一篇题解。 @北大西洋公约 · NATO 众所有周知，在做某一些题目或比赛中经常爆TLE，结果换了个更快的输入方法就解决了（比如我） 我真的服了，花的时间直接从3000ms变成几百ms。可见输入的重要性。 后续还有增加。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、方法详解 1. 优化标准输入流（CIN） 原理 > 1.cin并非独立的输入工具，它组合了各种其他的东西和繁琐的步骤。 > 它只是为了兼容 C 语言的scanf 和getchar()，就与 stdio 共享同一个底层输入缓冲区，它每次读取都需要进行“同步效验”，同步效验的过程如下： > > * 当调用cin>>n 时，cin首先会检查底层输入缓冲区中是否有 scanf/getchar() 未读取完的数据？ > * 如果有，先将底层输入缓冲区的数据同步到 cin 自己的临时缓冲区（避免数据重复读取）； > （典型先为别人考虑，不考虑自己，值得表扬） > * 如果没有，再从输入设备读取数据到底层输入缓冲区，然后同步到 cin 临时缓冲区； > * 同步完成后，cin才能从自己的临时缓冲区解析数据到变量n。 > > 离谱就离谱在你没有使用scanf 和getchar()它也要执行这几步（死脑筋） > > 2. 然后还有，你连续输入的话也会消耗时间，举个例子，就比如你一直开灯关灯开灯关灯...那灯丝不会烧坏啊。 > > 3. 它还与cout绑定，cin 和 cout 默认是 “绑定（Tied）” 关系，这是为了保证 “输出提示语” 和 “输入操作” 的顺序正确性。例如： > > 默认绑定机制下，执行 cin>>n前，会强制触发 cout.flush()（刷新 cout 的输出缓冲区），确保 “请输入数字：” 先显示在屏幕上，再等待用户输入。 > 但不需要的时候还是会检查。 > > 4. 接着，scanf有格式控制符不用考虑类型，而cin还要判断输入的数据符不符合类型。 > 不仅如此，它还维护了状态位，有两个缓冲区…… > 啊这…… 代码 优缺点 优点 缺点 无需修改原有 cin 使用习惯 无法完全消除底层开销 兼容性好 - 代码简洁 - 2. 使用 C 语言的 SCANF 函数 原理 > scanf 是 C 标准库输入函数，简洁的如同期末时的大脑，因此比未优化的 cin 快。 实现代码 优缺点分析 优点 缺点 速度稳定 需记忆不同类型的格式控制符 代码简洁 类型安全性低 兼容性强 读取字符串需人工设置大小，容易溢出 3. 批量读取缓冲区 原理 > 一次性将大块数据从输入设备读取到内存缓冲区，再从缓冲区中逐字符解析数据。 > 想象你在超市买零食，需要把零食从货架搬到购物袋里： > > * 普通读取（如scanf或cin）就像：拿一个零食，跑回购物袋放下，再跑回货架拿下一个... 来来回回跑很多趟，效率很低。 > * 批量读取缓冲区就像：推一辆购物车到货架前，一次把能装的零食零食都装到购物车里，推回购物袋旁再慢慢整理，大大减少了来回跑的次数。 前方高能，请小心食用\color{red}{前方高能，请小心食用}前方高能，请小心食用 代码 优缺点分析 优点 缺点 速度极快，IO 次数最少 代码复杂 适合超大量数据 缓冲区大小需手动调整 可灵活输入其他类型 若输入数据格式异常，会导致解析错误 4. 使用快速 IO 库 原理 部分算法竞赛常用的 “万能库”（如 bits/stdc++.h）或第三方快速 IO 库（如 fastio.h），已预实现优化后的输入函数（如 read()、readint()），底层基于 “批量缓冲区” 或 “getchar() 逐字符读取”，开箱即用。 代码 > 小熊猫2.21不支持（我试过了，不包含） 优缺点分析 优点 缺点 开箱即用 依赖特定库（部分编译器不支持） 支持多种类型，兼容性强 离开特定编译器可能无法运行 底层已做极致优化 不同库的函数名、参数可能不同，需适应 5. 使用自定义函数 某人的题解 代码 inline 是一个关键字，用于建议编译器对函数进行内联展开优化。 内联展开的含义 通常情况下，函数调用会有一定的开销（如保存现场、跳转、恢复现场等）。而内联函数在编译时，编译器会尝试将函数体直接 "嵌入" 到调用它的地方，而不是生成常规的函数调用指令。 比如，如果有这样的内联函数： 当你调用 f(3, 5) 时，编译器可能会直接替换为 3 + 5，而不是生成调用 f 函数的代码。 使用 inline 的要点： * 提高程序运行速度：消除函数调用的开销，适合频繁调用的小型函数（比如你代码中的 input() 函数，可能会被多次调用）。 * 不增加额外内存开销：如果没有内联，多次函数调用会重复执行相同的调用流程；内联展开后，虽然可能增加代码量（代码膨胀），但避免了重复的调用开销。 注意点 * inline 只是编译器的建议，不是强制命令。如果函数体过大或包含复杂结构（如循环、递归），编译器可能会忽略 inline 关键字，按普通函数处理。 * 内联函数通常需要在头文件中定义（而不是只声明），因为编译器需要在调用点看到完整的函数体才能进行内联展开。 * 过度使用内联可能导致生成的可执行文件变大（代码膨胀），反而影响性能。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、速度对比 1. 速度排序（从快到慢） 1. 批量缓冲区读取（自定义）：IO 次数最少，内存解析效率最高，速度极致； 2. 自定义 getchar() 逐字符读取：逐字符处理，无批量缓冲区的指针管理，但仍比流操作快； 3. 优化后的cin：消除同步开销，接近 scanf 速度； 4. scanf：C 标准输入，速度稳定但略慢于优化后的 cin； 5. 未优化的 cin：同步开销大，速度最慢，不适合大量数据。 2. 实际测试数据（参考） 在 “读取 100 万条随机整数” 场景下，不同方法的耗时（单位：秒）如下（数据因硬件、编译器不同略有差异）： 输入方法 耗时（秒） 相对速度（以 “未优化 cin” 为基准） 批量缓冲区读取 0.08 ~ 0.12 约 10~15 倍快 自定义 getchar() 0.15 ~ 0.20 约 8~10 倍快 优化后的 cin 0.25 ~ 0.30 约 6~8 倍快 scanf 0.30 ~ 0.35 约 5~6 倍快 未优化的 cin 1.2 ~ 1.5 1 倍（基准） 四、注意事项 1. 批量缓冲区读取：需注意缓冲区大小（过小可能需多次 fread，过大浪费内存），且需处理 “缓冲区数据读完” 的补充读取逻辑（本文示例为简化版，实际需判断 it 是否超出缓冲区）； 2. scanf 格式控制符：严格匹配变量类型（如 long long 必须用 %lld，而非 %d），否则会导致数据错误； 3. 优化后的cin：解除绑定后，cin 与 printf/scanf 不可混用（可能导致输出顺序混乱）； 4. 快速 IO 库：bits/stdc++.h 非标准库，在 VS 等编译器中需手动配置，移植时需注意兼容性。 五、后记 > 我没用AI写了，就查了下资料以自己的理解写的，与真实的可能有差异，希望大家反馈。 > 第一次写，希望点个赞，生活不易，点个赞吧QwQ

挑战全ACGO团队最多的人 666 竟比我还多 比AC是最好的更多的发在评论区 本人要去睡觉玩游戏写作业了 评论要晚上再回 评论区惊现滚蛋吧C++大佬 6666果然滚蛋吧C++大佬名不虚传 复仇者_摆烂崽

各位Minecraft大佬，谁知道怎么制造刷铁机啊？ 各位Minecraft大佬，谁知道怎么找到林地府邸啊？ 各位Minecraft大佬，谁知道怎么找到海洋神殿啊？

这个fw做题的时候突然想总结一下毒瘤数据结构（持续更中，于是就有了这篇文章... 你别急，我保证一定在CSP-J/S之前更新完，给大家一览！ Ps:本文不再介绍STL中有的数据结构。这里仅介绍NOI大纲1~8级的数据结构 目录一览： 1.并查集 2.ST表 3.线段树&树状数组 4.主席树 黄题 黄题 绿题 蓝题 一，并查集（模板黄题 有时候，我们要处理一种“帮派”问题，大概是这样的：a加入b的帮派，a的帮派和b的帮派结合...类似这样的操作。为了更好的解决这样的问题，我们用并查集来表示。 基本思想：用一个pre数组表示这个人的上级，那么查询a和b食不食再同一个帮派里，只需要比较他们的终极上司食不食一样就行。如果每次都这样查询的话，效率太低。可以使用记忆化搜索。下次找的时候直接返回即可。查询复杂度为O(log2n)O(log_{2}n)O(log2 n)（大概） 干讲不行，上例题： 1.(模板)并查集 题目中有查询和加入操作，按照上面的分析来。 一定要初始化pre[i]=i！！！！！！每年都有人忘记这个东西。 2.修复公路 并查集板子题。 先按照时间排序好开通路线的时刻，然后按顺序枚举：将此公路两端的城市x,y加入集合中（如果不相同），那么只要加n-1次所有城市就都在一个集合中了。此时最早通车时间就是当前这条路的开通时间。 ps:此类想法会与后面一个算法不约而同 3.食物链 这道题给我的印象超级深刻，当时老师让我们尝试新的做法，我尝试了八个小时也没有试出来，最后老师说，这个算法是错的... 此道题也可以用 带权并查集 解决，这里介绍普通做法。 定义一个三倍空间的并查集，其中n是同类并查集，x+n是猎物，x+2*n为天敌（题目中的关系满足三角形） 根据逻辑即可求解。 （代码找不到了，用别人题解上的吧，反正思路都一样） 二，倍增——ST表 ST表是解决RMQ问题的不二之选。他可以把单次静态查询变为O(1)O(1)O(1)，也就是说，它是离线算法。预处理复杂度为O(nlogn)O(nlogn)O(nlogn) 基本想法：为了把区间查询想树一样降到O(logn)O(logn)O(logn)级别的复杂度，不难联想到二进制优化。 设dp[i][j]dp[i][j]dp[i][j]为以i为起点，长度为2j2^{j}2j中的最值，那么 dp[i][j]dp[i][j]dp[i][j]=min/max/...(dp[i][j−1],dp[i+2j−1][j−1])min/max/...(dp[i][j-1],dp[i+2^{j-1}][j-1])min/max/...(dp[i][j−1],dp[i+2j−1][j−1]) 于是就可以建表，初始值设dp[i][0]=初始值dp[i][0]=初始值dp[i][0]=初始值 1.BALANCED LINEUP G RMQ板子题。 由于n过大，可以用ST表预处理。 (dp表示最大值的st表，pd表示最小值的st表) 2.策略游戏 一道巨恶心的题目，恶心值1100/1500，仅次于时间复杂度。 第一步，把csp语言转化成中文： 两个人在A数组的[l1,r1]区间里面选x，B数[l2,r2]区间里面选y，一个人要使xy最小，一个人要使xy最大。 请看图。 于是代码里就有6个st表，分别求，然后按照上面的思路来就行。 三，线段树&树状数组（模板绿 线段树是区间动态修改&区间动态查询的不二之选。 可能我们普通枚举，时间复杂度达到了O(nq)O(nq)O(nq)，再来一个大数据&卡常让你喜提TLE。 众所周知，使用 树 这种结构 可以让查询&修改操作降到O(logn)O(logn)O(logn)。下面以[模板]线段树1为例来分析。 先来一个求左儿子，右儿子的函数，方便以后使用。 然后，我们需要一个重要的东西——tag标记。又称lazytag。每次都一个一个修改太麻烦，我们可以先标记，再统一修改，也就是说，它可以传递式记录这个节点的改变，充分利用树的特征。于是，修改一个区间就变成了修改这个区间的LCA，再传递。 按照这样，我们可以建树了。 具体解释见注释。 1.[模板]线段树2 加上一个乘法，不会有人要抄题解了吧 还是同样的，加上一个tag，表示乘法tag。 再下传操作中，我们需要更新一下乘法和加法的顺序。 再pushdown中，tree=tree * 父亲的乘法tag+父亲加法乘上区间 cheng=cheng乘上父亲乘法 jia=jia*父亲乘法+父亲加法 再update中，与线段树1一样。 2.数据中心能耗分析 作为排位赛最后一题，出的还是太水了，为什么要放一个模板 本题要求立方和。 稍微推导一下。 定义sum1,sum2,sum3为1次，2次，3次立方和。在pushdown中修改即可。 代码我就不放了。 哎算了还是放一下吧 请我的机房朋友修改了一下，所以码风会和之前不一样。 四，主席树（权值线段树）（模板蓝 主席树就是在线段树上加上“权值”具体一点的说，主席树的每一个节点都在维护一棵线段树。 与线段树不同的是，每个节点代表的是[l,r][l,r][l,r]的范围。 干讲没用，上例题。 1.王老师的奇妙集合 主席树板子题。 数据比较大，使用主席树优化到O(nlogn)O(nlogn)O(nlogn)，而删除操作就是把元素交换到一个不为人知的地方。 具体解释看代码。 具体的请读者自己练习。 最后祝大家明天CSP RP+++!!!

谁能教教我这道题该怎么解啊

不是ACGO啥时候背着我们更新的？ 目前看到的更新内容： 1.深色浅色模式，不得不说深色模式真的好看，似乎加了一点美化诶，啊下面的队长指的是在北京cos我的滚蛋吧c++@‮༺དༀ༒∞░∞༒ༀཌ༻： 2.题单变成学习了，还搞了一个图，甚至这个图是可以点的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 话说那个用户分享题单咋搞啊 @AC君 3.丰富了题目种类，现在有各种类型了。这里是在团队题单里看见的： 以下是一些类型： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 重大更新啊，对了现在隐藏字搞不了了AWA @AC君这是什么时候更得啊。 大家点点赞，让更多的人看见。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 提个建议： 希望ACGO可以让这种↓图标与深色模式的兼容性更好：

原神理事会团队招新,玩原神的小伙伴们有兴趣可以加入 https://www.acgo.cn/application/1776484607864774656

赛时代码： AC 代码：

你居然发现了我的素材！！！回去吧

1.前言 如果想知道我国的人口数量，就需要进行人口普查。让每一个省份都去统计本省有多少人， 然后将各省人口累加起来，就可以获得全国的人口数量。而要想知道某一个省的人口数量，可以 让省里的每一个城市统计本市有多少人，然后将各市人口累加起来，就可以获得这个省的人口数 量……以此类推，层层细分，最后统计一个村子或者一个小区有多少人，这个任务就很简单了。 把一个复杂的问题细分成若干结构相同但规模更小的子问题，然后将每个子问题的解合并起来， 就得到了复杂问题的解，就是本文将会介绍的分治策略。 2.分治算法详解 (I) 递归方程 分治算法建立在递归数学理论的基础上，其核心思想是将原问题分解为若干个相互独立且结构相似的子问题。从计算复杂度角度看，分治算法通常遵循特定的递归关系式。设T(n)T(n)T(n)表示解决规模为nnn的问题所需时间，则典型的分治递归式可表示为： T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n) 其中aaa表示子问题数量，n/bn/bn/b为子问题规模，f(n)f(n)f(n)是分解与合并的开销。 (II)主定理 所谓主定理，就是用来解递归方程的一种方法，此方法可以用来求解大多数递归方程。（ 见(i) ） 主定理： 以下是主定理（Master Theorem）三种情况的公式表示： 情况1： f(n)=O(nlog⁡ba−ϵ)  ⟹  T(n)=Θ(nlog⁡ba)f(n) = O(n^{\log_b a - \epsilon}) \implies T(n) = \Theta(n^{\log_b a}) f(n)=O(nlogb a−ϵ)⟹T(n)=Θ(nlogb a) 情况2： f(n)=Θ(nlog⁡ba)  ⟹  T(n)=Θ(nlog⁡balog⁡n)f(n) = \Theta(n^{\log_b a}) \implies T(n) = \Theta(n^{\log_b a} \log n) f(n)=Θ(nlogb a)⟹T(n)=Θ(nlogb alogn) 情况3： f(n)=Ω(nlog⁡ba+ϵ)且af(nb)≤cf(n)  ⟹  T(n)=Θ(f(n))f(n) = \Omega(n^{\log_b a + \epsilon}) \quad \text{且} \quad a f\left(\frac{n}{b}\right) \leq c f(n) \implies T(n) = \Theta(f(n)) f(n)=Ω(nlogb a+ϵ)且af(bn )≤cf(n)⟹T(n)=Θ(f(n)) 其中 (ϵ>0)(\epsilon > 0)(ϵ>0) 是常数，(c<1)(c < 1)(c<1) 是常数。 简洁版主定理 {Θ(nlog⁡ba)if f(n)=O(nlog⁡ba−ϵ)Θ(nlog⁡balog⁡n)if f(n)=Θ(nlog⁡ba)Θ(f(n))if f(n)=Ω(nlog⁡ba+ϵ) 且 af(n/b)≤cf(n)\begin{cases} \Theta(n^{\log_b a}) & \text{if } f(n) = O(n^{\log_b a - \epsilon}) \\ \Theta(n^{\log_b a} \log n) & \text{if } f(n) = \Theta(n^{\log_b a}) \\ \Theta(f(n)) & \text{if } f(n) = \Omega(n^{\log_b a + \epsilon}) \text{ 且 } a f(n/b) \leq c f(n) \end{cases} ⎩⎨⎧ Θ(nlogb a)Θ(nlogb alogn)Θ(f(n)) if f(n)=O(nlogb a−ϵ)if f(n)=Θ(nlogb a)if f(n)=Ω(nlogb a+ϵ) 且 af(n/b)≤cf(n) 其实这三条定理都是搞f(n)f(n)f(n)与log⁡ba\log_b alogb a的大小问题，但是相当**的是，我们可以发现，这个比大小很明显比的是多项式大小，所以就有可能看似这个比那个大但是在多项式意义上这个却不比那个大，这就相当坑爸爸了...... 比如T(n)=2T(n2)+nlog⁡2nT(n) = 2T\left(\frac{n}{2}\right) + n \log_2 nT(n)=2T(2n )+nlog2 n，这个式子很明显就相当坑爹，虽然f(n)=nlog⁡2nf(n) = n \log_2 nf(n)=nlog2 n渐进大于nlog⁡ba=nn^{\log_b a} = nnlogb a=n，但是却不是多项式大于。这就是我纠结了很长时间。后来找到了一种证明 F(N)NLOG⁡BA+Ε=NLOG⁡2NN1+Ε=N−ΕLOG⁡2N\FRAC{F(N)}{N^{\LOG_B A + \EPSILON}}=\FRAC{N \LOG_2 N}{N^{1+\EPSILON}} = N^{-\EPSILON} \LOG_2 NNLOGB A+ΕF(N) =N1+ΕNLOG2 N =N−ΕLOG2 N ，而对于任意正常数εεε，没有可能使其等于111，这至少我还算可以接受。 (III)总结 分治算法的效率很大程度上取决于子问题的划分方式和合并操作的复杂度。理想的划分应保持子问题规模均衡，且合并操作应尽可能高效。在实际应用中，还需要考虑递归调用的系统开销和边界条件的处理策略。 3.分治的应用 (I)归并排序 归并排序是分治策略的典型应用之一。它的基本思想是：将数组分成两半，递归地对每一半进行排序，然后将排序好的两半合并。 具体步骤如下： 分解：递归地将原数组（原问题）划分为两个子数组（子问题），直到子数组只剩一个元素（最小子问题）。 解决：每个子数组只有一个元素时，自然是有序的，因此不需要再排序。 合并：从底至顶地将有序的子数组（子问题的解）进行合并，从而得到有序的原数组（原问题的解）。 归并排序的时间复杂度为O(nlogn)O(n log n)O(nlogn)，非常高效！ (II)快速排序 快速排序是另一种基于分治策略的排序算法。它的基本思想是：选取一个基准值，将数组分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。 具体步骤如下： 分解：选取一个基准值，将数组分成两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。 解决：递归地对这两部分进行排序。 合并：由于快速排序在分解的过程中已经实现了部分排序，因此不需要额外的合并步骤。排序完成后，整个数组就是有序的。 快速排序的平均时间复杂度也是O(nlogn)O(n log n)O(nlogn)，但在最坏情况下会退化到O(n2)O(n^2)O(n2)。不过，由于它的实现简单且大多数情况下效率较高，因此在实际应用中非常受欢迎。 (III) 二分查找 二分查找是一种高效的查找算法，它适用于在有序数组中查找特定元素。二分查找也基于分治策略。 具体步骤如下： 分解：将有序数组从中点索引分为两部分。 解决：根据目标值与中间元素值的比较结果，决定排除哪一半区间，然后在剩余区间执行相同的二分操作。 合并：二分查找旨在查找一个特定元素，因此不需要将子问题的解进行合并。当子问题得到解决时，原问题也会同时得到解决。二分查找的时间复杂度为O(logn)O(log n)O(logn)，非常高效！ (IIII) 矩阵乘法 矩阵乘法中的Strassen算法展示了分治策略如何突破传统复杂度界限。通过巧妙的子矩阵运算重组，它将888次乘法减少到777次，实现O(nlog27)≈O(n2.807)O(n^{log_2 7 }) ≈ O(n^{2.807})O(nlog2 7)≈O(n2.807)的复杂度。更先进的Coppersmith-Winograd算法进一步将指数降至约2.3762.3762.376，尽管实际应用受限。 4.分治的例题——快速幂 洛谷P1226 如果我们打算求aba^bab, 我们可能会写一个for循环，乘以bbb次aaa，时间复杂度为O(b)O(b)O(b) 当bbb比较小的时候还可以运用，但是当$b很大，此时时间复杂度就显然很高了，我们需要对其进行优化 ———快速幂 开始之前，先说两个前置知识： 1 二进制构成数字 众所周知，每个十进制数都可以由唯一的二进制数表示 我们不难发现，每一个十进制数都由其对应的二进制数，那么每一个十进制数都可以有$1 2 4 8 32 64 … $等这种二的次方数相加得到，并且每一种数只能取111个或000个 再例如 999，其二进制为100110011001 ，$ 8+1=9 $，即由111个888和111个111相加得到999 2 位运算 我们不难发现只有1&1才是1，根据这个思想，我们可以判断当前数字的二进制是否有1 其实不难发现，右移111就是除以222，>>n>>n>>n,就是除以2n2^n2n次方 结合&和>> 我们可以写个循环。逐渐判断每一位是否是111 3 快速幂算法(不取余版) 学完前面两个前置知识，我相信再学习 快速幂 将会很简单 首先假设我们要求5135^13513次方 131313的二进制为$1101 $所以13=8+4+113 = 8+4+113=8+4+1； 即513=51∗54∗585^{13} = 5^1 * 5^4 * 5^8513=51∗54∗58 ps: 幂运算可是初中数学学的 a(m+n)=am∗ana^{(m+n)}= a^m * a^na(m+n)=am∗an; 有这些知识我们就能直接看代码了 要是还有疑惑点，看代码注释也能看懂 4 取模版快速幂 快速幂只有五行代码，是不是很简单呢 不过别急，上面的快速幂是最原始版的，一般不是很常用，当aaa本身非常大时，如果a∗aa*aa∗a可能 long long 都给爆掉了，所以我们一般会采取取模的方式进行运算 前置知识 (a∗b∗c∗d)%p=(((a∗b)%p∗c)%p∗d)%p(a *b *c *d )\%p = (((a *b)\%p *c)\%p *d)\%p(a∗b∗c∗d)%p=(((a∗b)%p∗c)%p∗d)%p 即每次乘以下个数前可以先取模，这样最后答案不变，所以我们的代码可以进行优化了 5 完整代码 5.完结撒花 求置顶@AC君

我个人认为，ACGO可以增加个人公开赛，征求一下大家的意见

@李总（不加团队）我想跟你说一件事!!!!!!!!!!!!!!!!