题目链接 混乱的奶牛 题目描述 有  头奶牛，每头奶牛都有一个唯一的整数编号。如果一个排列中，任意相邻两头奶牛的编号之差的绝对值都严格大于 ，则称这个排列为“混乱队伍”。 给定  头奶牛的编号和整数 ，计算有多少种不同的排列是混乱队伍。 解题思路 这是一个带有特定约束条件的排列计数问题。鉴于奶牛的数量  非常小（），这强烈地暗示了一个指数级复杂度的算法。解决这类问题的经典方法是状态压缩动态规划 (DP on Subsets)。 我们可以将这个问题建模为：在一个图中寻找哈密尔顿路径的数量。图的每个顶点代表一头奶牛，如果两头奶牛  和  的编号之差 abs(c[i] - c[j]) > k，...

题目链接 PEEK145 最强碰撞 题目描述 火星科研团队发现了  颗性质各异的原子，编号依次为 。他们可以任取其中两颗原子进行碰撞，碰撞后，其中一颗原子会消失并从系统中移除，同时产生一定的能量。这个过程会一直持续，直到只剩下一颗原子为止。 研究人员已经提前测得了任意两颗原子  和  发生碰撞，如果原子  消失，能够产生的能量为 。为了获得尽可能多的总能量，他们可以自由决定碰撞的顺序，以及每次碰撞中哪颗原子消失。你需要帮助研究人员设计碰撞顺序，使得所有  次碰撞产生的能量之和最大。 解题思路 这是一个寻找最优决策序列以获取最大收益的问题。观察到原子数量  的范围非常小（通常 ），这是使用状态压...

题目链接 简单环 题目描述 给定一张  个顶点和  条边的无向图。一个简单环（Simple Cycle）是指顶点序列  () 满足：  边  均在图中存在（下标对  取模）。 顶点  均不重复出现。  现给定正整数 ，请统计图中长度大于 2（即长度 ）的简单环数量，并按环长度对  取模后的余数分类，统计出各个长度类的简单环总数对  取模的结果。 解题思路 这是一个在图中寻找并计数特定长度简单环的问题。由于顶点数  非常小（），这强烈暗示了需要使用一个指数级复杂度的算法，状态压缩动态规划 (DP on Subsets) 是解决此类问题的经典方法。 为了避免对同一个环重复计数（例如，从不同节点开始...

PEEK143 郊区春游 题目链接 PEEK143 郊区春游 题目描述 给定一个由  个郊区和  条无向道路组成的城市地图，每条道路有通行费用。现在需要从中挑选  个指定的郊区进行游玩。游玩顺序可以任意排列，但必须访问完所有  个郊区。总费用等于游玩过程中，按顺序访问的相邻两个郊区之间的最短路径长度之和。请求出最小可能的总费用。 解题思路 本题的实质是寻找一个访问  个指定节点的最优顺序，使得总路径成本最低。这是一个经典的旅行商问题 (Traveling Salesperson Problem, TSP) 的变体。由于  的值很小（通常 ），我们可以使用状态压缩动态规划 (State Comp...

题目链接 萌芽 题目描述 管理一棵字符串树（本质为一棵前缀树/Trie）。树中每条自根到叶的路径对应一条已存储的字符串。 现在需要连续提交  个字符串 。对于当前提交的字符串 ：  若树中不存在以  为前缀的任何字符串，则将  插入到字符串树中。 否则，输出树中以  为前缀的字符串数量（不插入）。  请你依次处理所有询问并输出对应结果。 解题思路 这道题目的核心是处理字符串前缀的查询和插入操作，这是 Trie (前缀树) 数据结构的典型应用场景。 Trie 是一种树形结构，它的每个节点代表一个字符串前缀。从根节点到任意一个节点的路径，构成了一个字符串。每个节点通常包含一个指向子节点的指针数组（...

PEEK142 炮兵阵地 题目链接 PEEK142 炮兵阵地 题目描述 在一个 N x M 的网格地图上，'P' 代表平原（可部署），'H' 代表山地（不可部署）。部署一个炮兵后，它会攻击同一行左右各 2 格，以及同一列上下各 2 格。要求任意两个炮兵不能互相攻击，求最多能部署多少个炮兵。 解题思路 本题是又一个经典的棋盘类动态规划问题，解法仍然是状态压缩DP。与“互不侵犯的国王”问题相比，本题的核心区别在于炮兵的攻击范围更远，一个炮兵会影响到其上下两行，这使得 DP 的状态定义和转移变得更加复杂。 核心思想： 由于第 i 行的决策会受到第 i-1 行和第 i-2 行的影响，因此我们的 DP ...

PEEK141 [SCOI2005]互不侵犯的国王 题目链接 PEEK141 [SCOI2005]互不侵犯的国王 题目描述 给定一个 N x N 的棋盘，要在上面放置 K 个国王，使得任意两个国王互相不攻击。国王的攻击范围是其周围的 8 个格子。请求出所有合法的摆放方案总数。 解题思路 这是一道经典的棋盘放置类组合计数问题，由于 N 的范围较小，非常适合使用状态压缩动态规划 (State Compression DP) 来解决。 核心思想： 我们按行（从上到下）在棋盘上放置国王。当我们决定第 i 行的布局时，只需要考虑它是否与第 i-1 行的布局冲突即可，因为国王的攻击范围只会延伸到相邻的行。...

PEEK139 固定长度的回文子串计数 题目链接 PEEK139 固定长度的回文子串计数 题目描述 给定一个由小写字母组成的字符串 S，长度为 N，以及一个正整数 L。请计算 S 中有多少个长度为 L 的子串是回文串。 解题思路 本题要求我们统计一个给定字符串 S 中，所有长度为 L 的回文子串的数量。 一个朴素的解法是遍历所有长度为 L 的子串。字符串 S 中共有 N - L + 1 个这样的子串。对于每个子串，我们再花费  的时间来检查它是否为回文串。这种方法的总时间复杂度为 ，在 N 很大的情况下，效率较低，可能会超时。 为了优化回文判断的效率，我们可以采用字符串哈希。其核心思想是：一个...

题目链接 神秘串 题目描述 给定一个仅由小写英文字母组成的字符串 ，长度为 。设元音字母集合为 {a, e, i, o, u}，其余字母视为辅音。 定义元音回文串如下：设子串 ，长度 。 若对所有 ，满足：若  或  为元音，则必须有 。 则称  为元音回文串。 注意：  对于一对对称位置 ，若两侧均为辅音，则无需相等。 若其中至少一侧为元音，则必须相等。  现在请你在  的所有子串中找出最长的元音回文串，并输出其长度。 解题思路 这是一个广义回文串问题。标准的回文串要求对称位置的字符必须完全相等。而本题的“元音回文串”则定义了一个特殊的匹配规则：对于一对对称字符 ，它们匹配的条件是 c1 =...

题目链接 神秘串 题目描述 给定一个仅由小写英文字母组成的字符串 ，长度为 。设元音字母集合为 {a, e, i, o, u}，其余字母视为辅音。 定义元音回文串如下：设子串 ，长度 。 若对所有 ，满足：若  或  为元音，则必须有 。 则称  为元音回文串。 注意：  对于一对对称位置 ，若两侧均为辅音，则无需相等。 若其中至少一侧为元音，则必须相等。  现在请你在  的所有子串中找出最长的元音回文串，并输出其长度。 解题思路 这是一个广义回文串问题。标准的回文串要求对称位置的字符必须完全相等。而本题的“元音回文串”则定义了一个特殊的匹配规则：对于一对对称字符 ，它们匹配的条件是 c1 =...

题目链接 不是烤串故事 题目描述 给定两个长度为  的字符串  和 。对于每一个 ，我们通过翻转  的前  个字符得到一个新的字符串 。任务是找到所有  中，使得  和  的最长公共前缀 (LCP) 最长的那个，并输出这个最长的 LCP 长度以及达到该长度的最小的 。 解题思路 这是一个可以通过字符串哈希 (String Hashing) 和二分查找 (Binary Search) 高效解决的问题。 对于每个翻转长度 （从  到 ），我们都会生成一个新的字符串 ，并需要计算它与字符串  的最长公共前缀 (LCP)。   的构成是： 的前  个字符翻转后的结果，拼接上  剩下的  个字符。 即 ...

题目链接 【模板】马拉车算法 题目描述 给定一个长度为  的字符串 ，请求出其最长回文子串的长度。 解题思路 本题是求解最长回文子串的模板题，最高效的算法是 Manacher's Algorithm（马拉车算法），它可以在  的线性时间内解决该问题。 1. 预处理字符串 传统求解回文串问题时，需要分别处理长度为奇数和偶数的回文串，比较繁琐。Manacher 算法通过一个巧妙的预处理，将两种情况统一起来。 我们在原字符串的每个字符之间以及字符串的两端插入一个特殊的分隔符（如 #）。  例如: aba -> #a#b#a# 例如: abba -> #a#b#b#a#  这样处理后，原字...

PEEK134 【模板】Trie 字典树 题目链接 PEEK134 【模板】Trie 字典树 题目描述 给定  个模式串和  次查询。对于每次查询，给定一个文本串 ，你需要统计有多少个模式串是以  作为前缀的。 解题思路 这是一个经典的使用 Trie 树（字典树或前缀树） 解决的问题。Trie 树是一种专门用于高效存储和检索字符串集合的数据结构，特别擅长处理前缀相关的查询。 Trie 树的结构和性质：  它是一个多叉树，树的根节点不代表任何字符。 从根节点到任意一个节点的路径构成一个字符串（通常是某个插入单词的前缀）。 每个节点包含一个指向子节点的指针数组（或哈希表）。数组的大小是字符集的大小...

题目链接 【模板】失配树 题目描述 给定一个字符串  和  组询问。每组询问给出两个整数  和 ，要求计算  的第  个前缀  和第  个前缀  的最长公共 border 的长度。 解题思路 本题是 KMP 算法与树上最近公共祖先（LCA）算法的结合。 1. 从 Border 到失配树 一个字符串  的 border 是指既是  的真前缀又是其真后缀的子串。KMP 算法的前缀函数  计算的正是前缀  的最长 border 的长度。 一个重要的性质是：一个前缀  的所有 border 的长度，可以通过  函数的“失配链”得到。即 （这里假设  数组是 1-indexed）。 这个链式关系启发我们...