题目链接 前缀最大周期长度之和 题目描述 给定一个长度为  的字符串 。对于  的每一个前缀 （其中  从 到 ），都需要计算其“最大周期长度”。最终，输出所有这些长度的总和。 解题思路 本题的核心是正确理解“最大周期”的定义，并利用 KMP 算法中的前缀函数（ 数组）进行高效计算。 关键洞察：周期与 Border 根据题意，“若  是  的真前缀，且  也是  的前缀，则称  为  的周期”。 这一系列的定义可以转化为一个经典的字符串性质： 一个长度为  的字符串  有一个长度为  的周期 （），当且仅当  有一个长度为  的 border（一个既是真前缀又是真后缀的子串）。 题目要求的是“...

题目链接 子串匹配 题目描述 给定一个文本串  和一个模式串 。任务是：  按升序输出  在  中的所有出现位置（1-indexed）。 输出模式串  的前缀函数（题目中称为 border 数组）。  解题思路 本题是 Knuth-Morris-Pratt (KMP) 字符串匹配算法的模板题。KMP 算法的核心思想是利用模式串自身的性质，在发生不匹配时，尽可能地向右“滑动”模式串，从而避免文本串指针的回溯，达到线性时间复杂度。整个算法分为两步。 1. 预处理模式串：计算前缀函数（Border 数组） 首先，我们需要为模式串  计算一个前缀函数，通常记为  数组。对于模式串  的每个前缀 ， 的...

题目链接 【模板】前缀函数（kmp） 题目描述 对于一个长度为  的字符串 ，其前缀函数  被定义为一个长度为  的数组。其中  的值是字符串  的前缀  的最长真前缀（proper prefix）同时也是其真后缀（proper suffix）的长度。 任务是对于给定的字符串 ，计算其完整的前缀函数  数组。 解题思路 这是计算 KMP 算法中 next 数组（或称前缀函数/失配函数）的模板题。该算法使用动态规划的思想，可以在线性时间内完成。 我们用  表示前缀串  的最长相等真前缀和真后缀的长度。我们的目标是依次计算出 。   基础情况: 对于 ，由于  只有一个字符，没有真前缀或真后缀，所...

题目链接 护花使者 题目描述 有  头奶牛，每头奶牛  有两个属性：运送回牛棚并返回花园所需的往返时间 ，以及在等待期间每分钟毁坏花朵的数量 。每次只能运送一头奶牛。目标是规划一个运送顺序，使得所有奶牛毁坏的花朵总数最少。 解题思路 这是一个经典的排序贪心问题。我们的目标是最小化一个与顺序相关的成本总和。 首先，我们来建立成本函数。假设我们确定了一个运送顺序 。  第一头奶牛  的等待时间为 。 第二头奶牛  的等待时间为 。 第三头奶牛  的等待时间为 。 ... 第  头奶牛  的等待时间为 。  因此，第  头奶牛  毁坏的花朵数量为 。 所有奶牛毁坏的花朵总数  为：  邻项交换法证明...

PEEK125 皇后游戏 题目链接 PEEK125 皇后游戏 题目描述 皇后有  位大臣，每位大臣左右手分别写着正整数 。大臣们需要排成一队。 第  位大臣获得的奖金  由他前面大臣的奖金 、他前面大臣（包括自己）左手数字之和  以及他自己右手数字  决定。 递推公式为： ，其中 。 目标是找到一个大臣的排列顺序，使得所有大臣中获得奖金的最大值  尽可能小。 解题思路 这是一个典型的排序贪心问题，目标是最小化最大奖金。问题的核心是找到一个最优的排序准则。 这个奖金的递推公式与一个经典的调度问题模型——双机流水调度（Johnson's Algorithm）——完全一致。 我们可以将问题类比为在两...

题目链接 货物堆放 题目描述 有  种不同的商品，每种商品有重量 、初始体积  和压缩系数  三个参数。当一个商品上方（不含自身）的总重量为  时，其体积会变为 。要求找到一种堆放顺序，使得所有商品最终的实际体积之和最小。 解题思路 这是一个可以通过贪心策略解决的排序问题。我们的目标是最小化所有商品实际体积的总和。 设商品的堆放顺序从下到上为 。 第  个商品  上方的总重量为 。 该商品的实际体积为 。 总的实际体积为 。 由于  是一个定值，不受排序影响，因此要最小化 ，我们必须最大化 。 邻项交换法证明 我们可以使用邻项交换法来推导贪心排序的准则。 假设在某个最优序列中，存在两个相邻的物...

PEEK123 [P1080] 国王游戏(简化版) 题目链接 PEEK123 [P1080] 国王游戏(简化版) 题目描述 国王和  位大臣玩游戏。国王的左右手分别写有整数 ，第  位大臣左右手分别写有 。 所有大臣排成一队，国王站在最前面。对于排在第  个位置的大臣，他能获得的金币数是 。也就是说，金币数等于国王和他前面所有大臣的左手数字的乘积，再除以他自己右手上的数字。 国王希望通过调整大臣的站位顺序，使得获得金币数最多的大臣得到的金币数尽可能小。请求出这个最小的最大金币数。 解题思路 这是一个典型的最小化最大值问题，通常可以通过贪心算法找到最优解。问题的关键是确定大臣们的最佳排序策略。 ...

题目链接 奥赛组队 题目描述 共有  名学生，每人有编程能力  和体育能力 。需要组建一支  人的编程队伍和一支  人的体育队伍，每人最多参加一队。目标是最大化两队的能力总和（编程队看 ，体育队看 ），并输出方案。 解题思路 这是一个复杂的组队优化问题，之前简单的贪心思路存在缺陷。一个正确且精妙的解法是采用“基准选择 + 迭代贪心优化”的策略。 算法思想：   建立基准选择： 我们首先做一个最直接的贪心假设：编程队伍由编程能力最强的  名学生组成。我们以此为起点，计算一个初始的总分，并将这  名学生的状态标记为“编程队”。   准备迭代优化： 接下来，我们需要为体育队挑选  名队员。我们进行 ...

题目链接 种树 题目描述 在 N 个坑中选择最多 K 个进行种树，要求任意两个种树的坑不能相邻。每个坑 i 对应一个收益 p_i（可能为负）。目标是最大化总收益。 解题思路 这是一个经典的贪心选择问题，但简单的贪心（如每次选收益最高的坑）会因为选择的局部最优性影响后续选择而失效。我们需要一种能够“反悔”的贪心策略。 核心贪心策略：带悔贪心 我们进行 K 轮选择，每一轮都选择当前能带来的最大收益增量。   初始选择：最开始，最大收益增量就是所有坑中收益最高的那一个。假设我们选择了坑 i，获得了 p_i 的收益。   选择后的影响：一旦选择了坑 i，根据规则，其相邻的坑 i-1 和 i+1 就不能...

题目链接 https://www.nowcoder.com/practice/61ad3cbe0e7d4db9b64fc2b7b503dfd8 题目描述 给定未来  天的股票价格。每天最多操作一次（买入1股、卖出1股或不操作）。初始时无股票，最终也必须清空股票。求最大收益。 解题思路 这是一个经典的可以通过“后悔贪心”思想解决的问题。核心在于，当我们决定在某天卖出时，我们应该匹配历史上哪一天的买入价格？显然是最低的那个。但这个决策可能不是全局最优的，因为未来可能有更高的卖出价。 “后悔贪心”算法通过优先队列（小顶堆）巧妙地解决了这个问题。 算法思想：  我们按天数顺序遍历每日股价。 我们维护一...

题目链接 任务安排 题目描述 有 N 个任务，每个任务都需要一个单位时间来完成。第 i 个任务有截止时间 d_i 和收益 p_i。只有在截止时间前（含）完成任务，才能获得相应收益。在任何时刻只能进行一项任务。求能够获得的最大总收益。 解题思路 这是一个经典的调度问题，可以使用贪心算法来高效解决。由于任务的截止时间 d_i 范围很大（高达 ），直接使用与时间点相关的数组会导致内存超限，因此我们需要一种不依赖于截止时间大小的算法。 核心贪心策略 一个直观的想法是，截止时间早的任务更“紧急”，我们应该优先考虑它们。   按截止时间排序：我们将所有任务按照截止时间 d 从小到大排序。这使得我们总是先处...

题目链接 PEEK116 旺仔哥哥组战团 题目描述 共有  名士兵，每名士兵有战力  和人数上限要求 。若要将士兵  编入战团，则战团总人数不能超过 。需要组建一个战团，满足所有被选中士兵的人数上限要求，并使得总战力最大。 解题思路 这是一个贪心问题，可以通过排序和优先队列（小顶堆）来解决。 问题的核心约束是，一个战团的规模取决于团内人数上限要求最严格（即  最小）的士兵。这启发我们应从要求最宽松的士兵开始考虑。 具体解题步骤如下：   排序：将所有士兵按照人数上限  从大到小进行排序。如果  相同，可以按战力  从大到小排序（此为次要排序，不影响最终结果的正确性）。这种排序策略保证了我们在遍...

题目链接 PEEK115 [JSOI2007]建筑抢修 题目描述 共有  座建筑受损。维修第  座建筑需要  秒，且必须在  秒内完成（含第  秒）。维修工同一时刻只能维修一座建筑，请求出最多能成功维修的建筑数量。 解题思路 这是一个典型的贪心问题，可以使用优先队列（大顶堆）来解决。 核心思想是：总是优先处理截止日期早的建筑，并随时准备用耗时短的新任务替换已选的耗时长的任务，以节省时间。 具体步骤如下：  排序：将所有建筑按照其截止日期  从小到大进行排序。这确保我们总是先考虑最紧急的维修任务。 遍历与决策：我们按排序后的顺序遍历每个建筑，并维护一个当前已花费的总时间 currentTime ...

题目链接 迷宫可达任务 题目描述 给定一个由  间房间和  条单向通道组成的迷宫。你需要判断这个迷宫是否为“完美迷宫”。 一个完美迷宫的定义是：对于迷宫中任意两间不同的房间  和 ，必须满足以下两个条件之一：   是从  可达的（即存在一条从  到  的路径）。  是从  可达的（即存在一条从  到  的路径）。  简单来说，任意两点之间都必须至少存在一个单向的路径。 解题思路 这是一个图论问题。我们可以将房间和通道模型化为一个有向图。题目中的“完美迷宫”定义了一个特殊的图属性，我们需要判断给定的图是否满足这个属性。 1. 强连通分量 (SCC) 与缩点 这个问题的核心在于分析图的全局连通性。...