水绿，拆位就行了，赛时20min切了

这也能黄题？？？，被震惊到了

前言： 本文涵盖KMPKMPKMP算法的详细步骤，大家有什么建议可以在评论区说哦！ 加精啦！！！感谢AC君赞助！！！ 竟然榜7了！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广告： 求加团！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 目录（CONTENTS）： > > > > 第一部分：导言 > > > > > > 第二部分：什么是 KMP 算法 > > > > > > 第三部分：KMP 算法的核心概念与预处理 > > > > > > 第四部分：KMP 算法的匹配过程与实现 > > > > > > 第五部分：刷题时光 > > > > > > 第六部分：常见踩坑点与避坑指南 > > > > > > 第七部分：常见问题与注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第一部分：导言: 在字符串处理场景中，我们经常需要解决 “模式匹配” 问题 —— 比如从一篇文章里找某个关键词、在日志中匹配特定指令，这时候最直接的思路是 “暴力匹配”：用模式串的每个字符依次对比主串的对应位置，不匹配就回溯主串重新开始。 但暴力匹配效率极低，比如主串是"AAAAA...A"（1000 个 A），模式串是"AAAB"，每次匹配到最后一个字符才失败，主串频繁回溯导致时间复杂度达到O(N*M)（N 为主串长度，M 为模式串长度）。 为此，我们需要更高效的算法 ——KMP 算法。它通过预处理模式串生成 “部分匹配表”（PMT），避免主串回溯，将时间复杂度优化到O(N+M)，是字符串匹配的经典高效方案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：什么是 KMP 算法： KMP 算法由 KNUTH、MORRIS 和 PRATT 三位科学家共同提出，核心思想是利用模式串自身的前缀后缀匹配信息，在匹配失败时让模式串 “少后退”，从而跳过不必要的对比步骤。 核心问题：为什么暴力匹配效率低？ 假设主串为S = "ABCABDABCAB"，模式串为P = "ABCAB"： > ·暴力匹配时，前 4 个字符 "ABCA" 均匹配，第 5 个字符 S [4] = 'X'（此处替换为与 'B' 不匹配的字符，如 'X'）与 P [4] = 'B' 不匹配，此时主串会回溯到 S [1]，模式串回到 P [0] 重新开始。 > ·但观察模式串"ABCAB"，其前 4 个字符"ABCA"的前缀"A"和后缀"A"是最长匹配的（长度 1）。这意味着主串中S[3] = 'A'（对应模式串P[3] = 'A'）其实可以直接与模式串的P[1]继续匹配，无需回溯主串。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分：KMP 算法的核心概念与预处理： 在学习 KMP 的实现前，必须掌握两个核心概念：前缀后缀和部分匹配表（PMT）。 3.1. 前缀与后缀： > ·前缀：字符串中除最后一个字符外，所有以第一个字符开头的连续子串。例："ABCAB"的前缀为["A", "AB", "ABC", "ABCA"]。 > ·后缀：字符串中除第一个字符外，所有以最后一个字符结尾的连续子串。例："ABCAB"的后缀为["B", "AB", "CAB", "BCAB"]。 > ·最长公共前缀后缀（LCP）：前缀和后缀中长度最长的相同子串。例："ABCAB"的 LCP 为"AB"，长度为 2。 3.2. 部分匹配表（PMT）： 部分匹配表（也称NEXT数组）是 KMP 的核心，它存储了模式串中每个位置的前缀子串的 LCP 长度。 > ·下标：模式串的字符位置（从 0 开始）。 > ·值：该位置前的前缀子串（即P[0..I-1]）的 LCP 长度。 如何构建 PMT（以模式串P = "ABCAB"为例）： 模式串字符 p[0] = 'A' p[1] = 'B' p[2] = 'C' p[3] = 'A' p[4] = 'B' 前缀子串 空串 "A" "AB" "ABC" "ABCA" LCP 长度 0 0 0 1 2 PMT 值 0 0 0 1 2 构建 PMT 的代码实现： 核心逻辑：用双指针I（指向后缀末尾）和J（指向前缀末尾）遍历模式串，通过对比字符更新 LCP 长度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第四部分：KMP 算法的匹配过程与实现： 有了 PMT，KMP 的匹配过程就非常清晰了：用两个指针分别遍历主串S和模式串P，匹配失败时通过 PMT 调整模式串指针，主串指针始终不回溯。 匹配步骤 1.初始化主串指针I = 0，模式串指针J = 0，并构建模式串的 PMT。 2.遍历主串： > ·若S[I] == P[J]：两个指针同时后移（I++，J++）。 > > ·若S[I] != P[J]： > > > ·若J > 0：通过 PMT 将J调整为PMT[J-1]（利用前缀后缀匹配信息跳过无效对比）。 > > > > ·若J == 0：主串指针后移（I++），模式串从开头重新匹配。 3.当J == P.SIZE()时，说明模式串完全匹配，返回匹配的起始位置（I - J）；遍历结束未匹配则返回 - 1。 完整代码实现： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第五部分：刷题时光： 例题 1：LEETCODE 28. 找出字符串中第一个匹配项的下标 题目大意：给你两个字符串HAYSTACK（主串）和NEEDLE（模式串），请返回NEEDLE在HAYSTACK中首次出现的下标。如果NEEDLE不是HAYSTACK的一部分，则返回-1。 解题思路：直接套用 KMP 算法模板，核心是构建 PMT 并执行匹配逻辑。 完整代码： 例题 2：查找模式串在主串中的所有匹配位置 题目大意：读入主串S和模式串P，输出P在S中所有出现的起始下标，若未匹配则输出 “无匹配”。 解题思路：在 KMP 匹配中，当J == M（匹配成功）时，不直接返回，而是通过 PMT 调整J（J = PMT[J-1]），继续查找后续匹配。 核心代码片段： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第六部分：常见踩坑点与避坑指南： KMP 算法的逻辑看似清晰，但在编码和理解过程中极易陷入细节陷阱，以下是高频踩坑点及解决方法： 1. PMT 构建：用 “IF” 代替 “WHILE” 回溯 J，导致 LCP 计算错误： 坑点描述： 构建 PMT 时，当P[I] != P[J]，新手常误用IF语句单次回溯J（如IF (J>0) J=PMT[J-1]），而非WHILE循环，导致无法找到最长的有效前缀后缀。 反例代码（错误） 问题分析： 以模式串P = "ABABAC"为例： > ·当I=4（P[I]='A'）、J=3（P[J]='B'）时，P[I] != P[J]，需回溯J到PMT[2] = 2（P[2]='A'）。此时P[4]='A' == P[2]='A'，J应更新为 3。 > ·若用IF，仅回溯一次就停止；若P[J]仍不匹配（如更复杂的模式串），会导致 LCP 长度计算偏短，后续匹配出错。 避坑方案： 必须用WHILE循环回溯J，直到J=0或P[I] == P[J]，确保找到最长的公共前缀后缀： 2. 匹配时：主串指针回溯，违背 KMP 核心逻辑： 坑点描述： 受暴力匹配思维影响，在S[I] != P[J]时，不自觉地让主串指针I回溯（如I = I - J + 1），导致时间复杂度退化为O(N*M)，失去 KMP 的效率优势。 反例代码（错误） 问题分析： KMP 的核心优化是 “主串不回溯”，所有调整仅针对模式串指针J。主串指针I一旦后移，就不再退回，这是保证O(N+M)复杂度的关键。 避坑方案： 牢记：匹配过程中主串指针I只做自增，绝不回溯。所有匹配失败的调整都通过修改J实现。 3. 边界处理：忽略模式串为空或长度大于主串的情况 坑点描述： 编码时未考虑极端边界场景，如模式串P为空、P.SIZE() > S.SIZE()，导致数组越界或返回错误结果。 反例代码（错误） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第七部分：常见问题与注意事项： 1.PMT 与 NEXT 数组的区别：有些资料中NEXT数组是 PMT 的 “右移 + 1” 版本（如NEXT[0] = -1），本质逻辑一致，只是实现时指针调整方式略有不同，本文采用原始 PMT 定义更易理解。 2.模式串为空的处理：根据题目要求，通常模式串为空时返回 0（匹配开头）或空列表。 3.字符类型适配：KMP 算法适用于所有可比较的字符类型（如大写字母、小写字母、数字），无需修改核心逻辑。 4.PMT 构建的易错点：当P[I] != P[J]时，必须用WHILE循环回溯J（而非IF），确保找到最长的有效前缀后缀。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 尾声： > 特别鸣谢： > > > 排版： @AC是最好的 > > > > 标题：@‮༺དༀ༒∞░∞༒ༀཌ༻ > > > > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻ > > > > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻ 创作不易，给一个赞吧，求求了

可以看样例？？？ 绝对不是F12！

题解

1 * 2 * 3 * 4 * 5的确等于5！啊~~~ ☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢☢

一、上节课作业部分 1. 细胞数量 2. 打开转盘锁 二、课堂案例部分

这个帖子是图论算法的合集，你会看到： · 图的存储 · 图的遍历 · 并查集 · 最小生成树 · 最短路 · 拓扑排序 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图的存储 图的存储分为两种：邻接表和邻接矩阵 邻接矩阵存图： 邻接矩阵存图思想很简单： 对于无权图，如果 iii 和 jjj 有一条边相连，那么 graph[i][j]=1graph[i][j]=1graph[i][j]=1，否则 graph[i][j]=0graph[i][j]=0graph[i][j]=0 对于有权图，如果 iii 和 jjj 有一条权值为 kkk 的边相连，则 graph[i][j]=kgraph[i][j]=kgraph[i][j]=k，否则 graph[i][j]=∞graph[i][j]=\inftygraph[i][j]=∞ C++模板代码： Python模板代码： 空间复杂度：O(V2)O(V^2)O(V2) 练习： A358. 有向无权图1 A355. 有向带权图1 A352. 无向无权图1 邻接表存图： 我们会发现，邻接矩阵存图，对于稀疏图而言，浪费了太多空间在 000 或 ∞\infty∞ 上，这会导致当 nnn 越来越大，但是图是稀疏图的时候，会开不下邻接矩阵。因此，我们可以把邻接矩阵中所有的 000 或者 ∞\infty∞ 去掉，变成邻接表，adj[i]adj[i]adj[i] 变成一个（C++）向量或者（Python）列表动态添加边的信息。 C++模板： Python模板代码： 空间复杂度：O(E)O(E)O(E) 练习： A351. 有向带权图2 A650. 有向无权图2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图的遍历 图的遍历，主要分为深度优先遍历和广度优先遍历，内容和深度优先搜索（Depth−First−SearchDepth-First-SearchDepth−First−Search）与广度优先搜索（Breadth−First−SearchBreadth-First-SearchBreadth−First−Search）几乎一样。 深度优先遍历： 以邻接表为例，深度优先遍历就是不走回头路，一直往下遍历，遍历到没有未访问的结点就返回。 C++模板代码： Python模板代码： 广度优先遍历： 依然以邻接表为例，广搜像水流一样要流经所有结点，虽然搜索时比深搜效率快很多，但是在这里和深搜遍历就效率上来谈没什么大的区别。 C++模板代码： Python模板代码： 时间复杂度：都是 O(V)O(V)O(V) 练习： A4762. 关系网络 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 并查集： 并查集（Union−FindUnion-FindUnion−Find）是一种用于管理‌不相交集合‌的高效数据结构，主要解决元素的‌分组、合并与连通性查询‌问题。主要分成查询（FindFindFind）和合并（UniteUniteUnite）两个操作。可以形象地想象成是认“义父”操作 C++模板代码： Python模板代码： 单次查找函数的时间复杂度：O(log⁡E)O(\log E)O(logE) 总时间复杂度：O(Elog⁡E)O(E\log E)O(ElogE) 练习： A567. 亲戚1 A565. 亲戚2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 生成树： 在连通图 GGG 中，对于 ∀u、v∈G.V\forall u、v\in G.V∀u、v∈G.V，有且仅有一条路，且生成树中不存在回路。 最小生成树： 是所有的生成树中边权值和最小的一棵生成树。常见算法有 KruskalKruskalKruskal（克鲁斯卡尔）和 PrimPrimPrim（普里姆） 求最小生成树的方法： · KRUSKAL 算法： 1、将所有的边按从小到大顺序排序 2、按排序顺序选择联通 u、vu、vu、v 两个结点的边 3、通过并查集判断 u、vu、vu、v 两个结点是否联通，如果不联通则合并两个结点 4、选到 n−1n-1n−1 条边的时候，根据树的定义可以直接返回 C++模板代码： Python模板代码： 时间复杂度：O(Elog⁡E)O(E\log E)O(ElogE) 空间复杂度：O(V+E)O(V+E)O(V+E) · PRIM算法： 1、初始化距离数组为 ∞\infty∞，选择初始结点，将其距离设为 000 2、遍历所有结点中未标记的结点，选择其中距离最小的结点，进行标记 3、从该结点出发，遍历其能够到达的所有结点，更新其距离 4、重复执行操作 222 和 333 直到全部顶点都被标记 C++模板代码： Python模板代码： 时间复杂度：O(V2)O(V^2)O(V2) 空间复杂度：O(V+E)O(V+E)O(V+E) 练习： A555. 最小生成树 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最短路算法： 即求从结点uuu到结点vvv所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点uuu到所有其它结点vvv的算法，而多源最短路算法可以求∀u∈G.V\forall u \in G.V∀u∈G.V作为起点到其它结点vvv的最短路。 单源最短路算法： 常见的有 DijkstraDijkstraDijkstra（迪杰斯特拉）、Bellman−FordBellman-FordBellman−Ford（贝尔曼-福特）和 SPFASPFASPFA 三个算法。 求单源最短路的方法： · DIJKSTRA 1、初始化距离数组为 ∞\infty∞，选择初始结点，将其距离设为 000 2、遍历所有结点中未标记的结点，选择其中距离最小的结点，进行标记 3、从该结点出发，遍历其能够到达的所有结点，更新其距离 4、重复执行操作 222 和 333 直到全部顶点都被标记 C++模板代码： Python模板代码： 时间复杂度：O(V2)O(V^2)O(V2) 空间复杂度：O(V+E)O(V+E)O(V+E) · DIJKSTRA 的优化 根据上面代码，用 O(V2)O(V^2)O(V2) 的时间复杂度取求最短路无疑是有点浪费时间的，时间都花在了找最小值上面。考虑利用 STLSTLSTL 容器的特性来优化 DijkstraDijkstraDijkstra，我们需要一个能够动态找最小值的容器。 因此，我们可以利用优先队列（堆）动态找到最小值来优化 DijkstraDijkstraDijkstra 算法： C++模板代码： Python模板代码： 时间复杂度：O(Vlog⁡V+Elog⁡V)O(V\log V+E\log V)O(VlogV+ElogV) DIJKSTRA 不适用的情况： 根据 DijkstraDijkstraDijkstra 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。 · BELLMAN-FORD： 1、遍历所有的边 2、从边的起点到终点做松弛操作 优化：如果没有进行过松弛操作则退出循环 C++模板代码： Python模板代码： · BELLMAN_FORD 变形——不超过 KKK 条边的最短路 对于某些题目，要求走的边数不超过 kkk 且求最短路，普通的 Bellman−FordBellman-FordBellman−Ford 算法肯定行不通。此时，我们可以使用 dpdpdp 思想，来进行最短路的计算，如下： C++模板代码： Python模板代码： 时间复杂度：O(VE)O(VE)O(VE) 空间复杂度：O(V+E)O(V+E)O(V+E) · SPFA： SPFASPFASPFA（Shortest  Path  Faster  AlgorithmShortest\,\,Path\,\,Faster\,\,AlgorithmShortestPathFasterAlgorithm）是 Bellman−FordBellman-FordBellman−Ford 算法的进阶版本，通过队列来对其进行优化。 C++模板代码： 时间复杂度：O(kV)O(kV)O(kV)（kkk为常数，通常是在 [2,3][2,3][2,3] 之间） 空间复杂度：O(V+E)O(V+E)O(V+E) 队列空间复杂度：0<x≤O(V)0< x\leq O(V)0<x≤O(V) 练习： A569. 单源最短路1 多源最短路算法： 一般用 Floyd−WarshallFloyd-WarshallFloyd−Warshall 算法（也有版本叫它 Floyed−WarshallFloyed-WarshallFloyed−Warshall）。 求多源最短路的方法： · FLOYD-WARSHALL： Floyd−WarshallFloyd-WarshallFloyd−Warshall算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。 C++模板代码： Python模板代码： 时间复杂度：O(V3)O(V^3)O(V3) 空间复杂度：O(V2)O(V^2)O(V2) 拓扑排序 图的拓扑排序定义： 对于有向无环图（简称 DAGDAGDAG）是将 GGG 中所有顶点排成一个线性序列，使得 ∀u,v∈G.V\forall u,v\in G.V∀u,v∈G.V，若边 <u,v<u,v<u,v >>> ∈G.E\in G.E∈G.E，则 uuu 在线性序列中出现在 vvv之前。 1、选择一个入度为0的顶点并输出 2、从网中删除此顶点及所有出边 3、重复操作 111 和 222 直到没有符合要求的点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 备注： 符号解释： GGG：表示一张图 VVV：表示点的数量 EEE：表示边的数量 G.VG.VG.V：指点的集合 G.EG.EG.E：指边的集合

这一次GESP有一道编程题不会做（全部超时），求大神指点。题目大概如下： > 时限1000ms > 空间限制128MB 小A有一个数组，现在进行一些操作，使数组所有元素变0。求做多少次操作。 一次操作的步骤： 1. 在数组里找出最大的值，称作ak。 2. 再在数组里找出最小的值，称作aj。 3. ak-=aj 输入格式： 输出格式： 值域： 0 ≤\leq≤ n、a的所有值 ≤\leq≤ 100 求解答，在线等，很急，谢谢！

需要维护一个长度为 nnn 的序列，使得支持下面操作： * 区间加 * 区间求异或和 mmm 次操作。 强制在线。 同学说他会 O(mlog⁡2n)O(m \log^2 n)O(mlog2n) 的，怎么做！！！ 结局：被同学忽悠了

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第一次来写比赛题解，轻喷 仅为个人观点 题目 知识点 大大和1 数学思维、找规律 午枫的博弈 数学思维、找规律 小午的请求 数学知识 小枫爬山 前缀和、二分查找 午枫的双人挑战 贪心、优先队列 大大和2 窝也不知道（侥幸） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1.大大和1 传送门 问题分析 给定一个数组，需要判断是否存在一个连续子数组，使得该子数组的最大值大于等于该子数组所有元素的和。 仔细观察和认真烧烤 * 对于任意单个元素，最大值等于和，所以总是满足条件。 * 因此，只要数组非空，一定存在这样的子数组。 解题思路 直接对于每个测试用例，输出"YES"。 CODE 时间复杂度 O(n)O(n)O(n) 空间复杂度 O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2. 午枫的博弈 传送门 问题分析 这是一个两人博弈游戏，小午先手，双方轮流隐藏数字（小午隐藏奇数位置的数，小枫隐藏偶数位置的数），最后剩下一个数字时，如果是奇数则小午胜，偶数则小枫胜。 仔细观察和认真烧烤 情况1：N为奇数（奇数个数字） * 小午先手，小枫后手，共进行 (n-1) 轮操作 * 操作轮次：小午、小枫、小午、小枫...（交替进行） * 由于n为奇数，最后剩下的数字位置取决于操作过程 关键点： * 小午只能隐藏奇数位置的数，小枫只能隐藏偶数位置的数 * 如果数组中存在至少一个奇数数字，小午有可能获胜 * 如果数组中全是偶数数字，小午无法获胜（因为剩下的数字必然是偶数） 情况2：N为偶数（偶数个数字） * 小午先手，小枫后手，共进行 (n-1) 轮操作 * 操作轮次：小午、小枫、小午、小枫...（交替进行） 关键点： * 如果数组中存在至少一个偶数数字，小枫有可能获胜 * 如果数组中全是奇数数字，小枫无法获胜（因为剩下的数字必然是奇数） 解题思路 根据n的奇偶性和数组中数字的奇偶性分布来判断： 当N为奇数时： * 如果数组中存在奇数数字 → 小午获胜（输出"Noon"） * 如果数组中全是偶数数字 → 小枫获胜（输出"Maple"） 当N为偶数时： * 如果数组中存在偶数数字 → 小枫获胜（输出"Maple"） * 如果数组中全是奇数数字 → 小午获胜（输出"Noon"） CODE 由于数据较水，本人微错代码A了，给大家带来不便，太对不起了，现已改正 时间复杂度 O(n)O(n)O(n) 空间复杂度 O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3.小午的请求 传送门 问题分析 给定n个正整数，需要从中选出一些数，使得选出的数之和为偶数，并且这个和要尽可能大。 仔细观察和认真烧烤 众所周知，所有数字之和是最大的。那么就计算所有数字的总和 所有数之和：如果所有数的和已经是偶数，那么这就是最大的偶数和 和为奇数的情况：如果所有数的和是奇数，我们需要减去一个最小的奇数来使和变为偶数 为什么是最小的奇数：因为减去最小的奇数可以保证损失最小，从而得到最大的偶数和 解题思路 计算所有数字的总和 如果总和是偶数，直接输出总和 否则减去最小的奇数（根据小学知识，奇数-奇数=偶数） CODE 时间复杂度 O(n)O(n)O(n) 空间复杂度 O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4.小枫爬山 传送门 问题分析 给定n个非递减的台阶高度和m个爬山者的腿长，每个爬山者只能爬过高度差不超过其腿长的台阶。需要计算每个爬山者能到达的最大高度。 仔细观察和认真烧烤 楼梯是单调递增的且爬山者只能跨过高度差 ≤ 腿长的台阶 解题思路 预处理高度差：计算相邻台阶之间的高度差数组d 计算前缀最大值：创建前缀数组pre，其中pre[i]表示前i+1个高度差中的最大值 二分查找：对于每个爬山者，在前缀数组pre中二分查找第一个大于其腿长的位置 * 这个位置表示从哪个台阶开始，高度差超过了爬山者的腿长 * 爬山者最多只能到达这个位置之前的最后一个台阶 CODE 时间复杂度 O(n+mlogn)O(n + m log n)O(n+mlogn) 空间复杂度 O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5.午枫的双人挑战 传送门 问题分析 这是一个双人协作的关卡通关问题，小午负责解密部分，小枫负责战斗部分。游戏有 nnn 个关卡，每个关卡必须按顺序进行（解密 iii 需要先完成解密 i−1i-1i−1 ）。需要计算完成k个关卡的最短时间。 仔细观察和认真烧烤 关卡必须按顺序完成，解密 iii 需要先完成解密 i−1i-1i−1 总时间 = 所有完成的解密时间 + 选择的战斗时间 总而言之，解密必须一关一关解，战斗可以在解完密的关卡中选择 解题思路 前缀和预处理：计算前i个关卡解密部分的总时间pre[i] = a[0] + a[1] + ... + a[i-1] 对于每个查询k： * 首先选择前k个关卡的战斗部分，计算初始总时间：pre[k] + sum(b[0]到b[k-1]) * 使用最大堆（优先队列）维护当前选择的k个最小的战斗时间 * 从第k个关卡开始，尝试用后面关卡的更小战斗时间替换当前选择中较大的战斗时间 * 每次替换后更新总时间，并记录最小值 CODE 时间复杂度 O(n+q×nlogk)O(n + q × n log k)O(n+q×nlogk) 空间复杂度 O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6.大大和2 传送门 问题分析 类似第一题，只不过是给定一个数组，需要判断是否存在所有连续子数组，使得该子数组的最大值大于等于该子数组所有元素的和。 仔细观察和认真烧烤 不会 求救大佬 解题思路 主包本来是想将数组分成两个元素一组和三个元素一组，分别判断，结果WA了八个点。 于是主包转攻暴力，WA了四个。 经过一番打补丁，终于是又A了一个点。 随后主包开始加快读，尝试多骗一点（未果）。 最后主包急眼了，直接调小了循环范围，结果AC了 CODE 时间复杂度 未知未知未知 空间复杂度 O(n)O(n)O(n) 求讲解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是蒟蒻第一次ak挑战赛，求求了@AC君 @NoonMaple顾老师快来看我写的题解

出错了

e...这是陆尧搞得跟我木有关系（小声）

尊敬的同学，您好，很抱歉打扰到了您，如果您有时间，请加入我们"HTTPS://WWW.ACGO.CN/APPLICATION/1940677638216290304"，很期待您的加入，谢谢；如果你不想参加这个团队，那我向您说声对不起，祝您在ACGO的成功路上越走越远，再见！ 记得跟副团加好友（主团不经常上线）

题目描述 This is yet another problem on regular bracket sequences. A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence. For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest. 给一个序列，序列里面会有左括号、问号、右括号。对于一个‘？’而言，可以将其替换为一个‘（’，也可以替换成一个‘）’，但是都有相应的代价。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。 输入格式 THE FIRST LINE CONTAINS A NON-EMPTY PATTERN OF EVEN LENGTH, CONSISTING OF CHARACTERS "(", ")" AND "?". ITS LENGTH DOESN'T EXCEED 5 ⋅ 1 0 4 5⋅10 4 . THEN THERE FOLLOW � M LINES, WHERE � M IS THE NUMBER OF CHARACTERS "?" IN THE PATTERN. EACH LINE CONTAINS TWO INTEGER NUMBERS � � A I AND � � B I ( 1 < � � , � � < 1 0 6 1<=a i ,b i <=10 6 ), where � � a i is the cost of replacing the � i -th character "?" with an opening bracket, and � � b i — with a closing one. 第一行是序列，序列长度不超过 5 × 1 0 4 5×10 4 ，下面 � m（ � m是？的数量）行有每行 2 2 个数据，第一个是 '（'的代价，第2个是 '）' 的代价。 输出格式 Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second. Print -1, if there is no answer. If the answer is not unique, print any of them. 第一行输出最小代价，第二行输出替换后的序列。不行输出 − 1 −1。 输入输出样例 输入#1 (??) 1 2 2 8 输出#1 4 ()() 谁敢做？！

“入门” 好小众的词汇

@一只Merry

null