题目链接 实现字通配符 题目描述 在 Linux Shell 中，通配符 * 代表任意长度（可为 0）的字符串。给定一条模式串 （仅包含可见字符及通配符 *）和一条目标串 ，请输出  中所有与  匹配的子串的起始位置（从 0 开始计）及长度。 若不存在匹配，输出 -1 0。多组匹配按“起始位置升序，长度升序”排序输出。 解题思路 本题解法严格遵循您提供的代码，其核心思路是**遍历所有可能的起始点，并对每个起始点进行一次无记忆化的深度优先搜索（DFS）**来查找所有匹配。 1. 整体框架  主函数通过一个 for 循环，遍历目标串  的每一个位置 （从  到 ），将每个  都作为一个潜在匹配的起...

题目链接 kotori和素因子 题目描述 kotori 拿到  个互不相同的正整数 。她要从每个  中选出一个素因子 ，要求所有选出的素因子两两不同，即  ()。 若无法满足要求输出 ；否则输出所有选出的素因子之和  的最小可能值。 解题思路 本题要求为  个不同的数分别选择一个唯一的素因子，并使得这些素因子的总和最小。 由于数据规模  非常小（），这提示我们可以使用搜索算法来解决。一个经典的方法是深度优先搜索（DFS）配合回溯。 具体思路如下：   预处理：对输入的每个数 ，分解质因数，得到它所有不重复的素因子列表。因为 ，我们可以用试除法高效地完成这一步。   深度优先搜索：我们定义一个递...

题目链接 取数游戏 题目描述 给定一个  的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻的8个格子中的一个，即认为这两个数字相邻），求取出数字和的最大值。 解题思路 这是一个在网格中选取不相邻元素以获取最大和的经典问题。由于矩阵的维度非常小（），这提示我们可以使用状态压缩动态规划（Bitmask DP）来解决。 1. 核心思想与状态定义 我们逐行处理矩阵，计算每一行在不同选取方案下的最大和。 我们定义一个二维DP数组：。   ：代表当前处理到第  行（从0开始）。   ：一个整数，它的二进制表示法代表了第  行的选取状态。如果...

题目链接 数组分组 题目描述 对于给定的  个整数，需要将其分为  和  两个数组，并满足以下条件：   所有 5 的倍数元素均在  数组中。   所有 3 的倍数（且非 5 的倍数）元素均在  数组中。   其他元素可以任意分配到  或  中。   求解是否存在一种分配方案，使得  数组中各个元素之和等于  数组中各个元素之和。 解题思路 这个问题的核心在于如何分配那些既不是 3 的倍数也不是 5 的倍数的“自由元素”，以使得两个数组的和相等。 问题转化 我们可以将所有输入数字分为三类：   G5: 5 的倍数。这些数必须放入数组 。我们计算它们的和 。   G3: 3 的倍数（但非 5 的...

题目链接 模意义下最大子序列和 题目描述 给定一个含有  () 个正整数的数组  以及一个正整数模数  ()。你可以任选若干下标递增的元素构成一个子序列（允许选择空序列）。设所选元素之和为 ，求  的最大可能值。 解题思路 这是一个求解所有子序列和模  的最大值问题。 1. 算法选择 本题的关键在于数据范围：数组长度  非常小（），而模数  和数组元素  可能非常大。   的动态规划解法：由于  可以达到 ，时间和空间复杂度都无法接受。  的搜索解法：由于 ，，这是一个非常小的计算量。因此，我们可以通过枚举所有可能的子序列来解决问题。  深度优先搜索（DFS）是实现子序列枚举的经典方法。 2....

题目链接 全排列 题目描述 给定一个整数 ，请按字典序输出数字  的所有排列。 解题思路 这是一个生成全排列的经典问题，可以使用深度优先搜索（DFS）结合回溯法来解决。 1. 核心思想 我们的目标是构建一个长度为  的排列。我们可以把它想象成有  个空位，我们需要从数字  中不重复地选择数字填入这些空位。  第1个位置：可以填入  中的任意一个。 第2个位置：可以填入剩下  个未使用的数字中的任意一个。 ... 第n个位置：只能填入最后一个剩下的数字。  这个逐层决策的过程天然形成了递归结构，非常适合用DFS来解决。 2. 回溯算法流程   定义递归函数： 创建一个递归函数，例如 dfs(cu...

题目链接 数水坑 题目描述 由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个  的矩形网格，每个格子要么是水 (W)，要么是干地 (.)。 若两个水格子在八连通（上下左右及四条对角线）意义下互达，则它们属于同一个水坑。 给出田地示意图，计算水坑数量。 解题思路 这是一个在二维网格中统计连通块数量的经典问题。核心思想是遍历整个网格，每当我们发现一个属于水坑但尚未被访问过的水格子时，就找到了一个新的水坑。然后，我们从这个格子出发，通过搜索（如深度优先搜索DFS或广度优先搜索BFS）找到并标记所有与它相连的水格子，以确保同一个水坑不会被重复计数。 1. 算法流程   初始化：  创建一个 vis...

题目链接 迷宫寻路 题目描述 给定一个  的矩形迷宫，每个格子要么是空地（用符号 . 表示），要么是墙（用符号 # 表示）。旺仔哥哥只能从一个空地移动到其上下左右四个相邻的空地。 已知起点为左上角 ，终点为右下角 。请判断他是否能够从起点到达终点。 解题思路 这是一个典型的图搜索问题，目标是判断图（迷宫）中两个节点（起点和终点）是否连通。我们可以将迷宫的每个空地格子看作图中的一个节点，相邻的空地格子之间存在一条边。 解决此类问题的常用算法是广度优先搜索 (BFS) 或深度优先搜索 (DFS)。这里我们采用广度优先搜索 (BFS)，因为它在寻找路径问题中非常直观且能保证找到最短路径（尽管本题不要...

题目链接 长椅安置 题目描述 公园内有  条东西向小径与  条南北向小径，彼此相交形成  个交叉点。现有  张长椅需要放置，要求：  每张长椅放在某个交叉点； 同一条小径上 至多 放置一张长椅。  请计算满足条件的放置方案数量。输入  满足 。 解题思路 这个问题是在一个  的网格中放置  张长椅，并要求任意两张长椅都不能在同一行或同一列。这是一个经典的组合计数问题。 我们可以分两步来构造一个合法的放置方案： 第一步：选择放置长椅的行和列 要放置  张长椅，它们必须占据  个不同的行和  个不同的列。  选择 5 个不同的行：从  个可用的行中，选择  个来放置长椅。这是一个组合问题，方案数为...

题目链接 中位数之和 题目描述 给定一个长度为  的二进制数组 （每个元素为  或 ）。记  为奇数。对于数组  的所有长度恰为  的子序列，求它们中位数之和，并对  取模。 名词解释：  子序列：如果数组  可以从  中删除几个（可能是零）元素得到，那么  就是  的子序列。 中位数：长度为奇数  的数组的中位数是排序后的第  个元素。  解题思路 这是一个组合计数问题。直接枚举所有长度为  的子序列是不可行的，因为其数量可能非常巨大。我们需要找到一种更高效的数学方法。 1. 问题转化 由于数组是二进制的（只包含  和 ），任何子序列排序后都会形成一段连续的  和一段连续的 （其中一段可能为...

题目链接 人员分组问题 题目描述 某公司计划从  份应聘简历中选出  到  人组成一个创新小组。请求出所有可能的小组组合数量，结果对  取模。 解题思路 本题是一个基础的组合计数问题。我们需要计算从  个人中选出  人、 人、 人的方案数之和。 问题分解 小组的人数可以是 、 或  人，这三种情况是互斥的。因此，总的组合数量是这三种情况的组合数之和：  其中  表示从  个不同元素中选出  个元素的组合数，模数 。 组合数计算 由于输入  的范围可以达到 ，预计算所有阶乘的方案会占用过大的空间且没有必要。注意到我们需要计算的  值非常小（最大为7），我们可以采用一种更直接的计算方法。 组合数的...

题目链接 【模板】组合数 题目描述 给定两个整数  与  ()，请你计算组合数  的值，并对模数  取模。 解题思路 本题是求解组合数模一个质数的模板题。 1. 组合数公式 组合数的基本公式为：  在进行模运算时，除法不能直接计算，需要转化为乘以除数的模逆元。 公式变为：  其中  是一个质数。 2. 模逆元 因为模数  是一个质数，我们可以使用费马小定理来计算一个数  的模逆元 。 费马小定理指出：如果  是一个质数，且  不是  的倍数，则有 。 由此可得：，所以 。 计算  可以通过快速幂算法高效完成。 3. 预处理 题目包含多组测试用例，且  的最大值达到了 。如果每次查询都重新计算阶...

题目链接 矩形计数 题目描述 给定一个  的网格，每个单元格被染成白色（0）或黑色（1）。求满足以下条件的非空单元格集合  的数量：  集合中所有单元格颜色相同。 集合中任意两单元格处在同一行或同一列。  结果对  取模。 解题思路 本题的核心在于理解“任意两单元格处在同一行或同一列”这一约束。 核心条件分析 这个条件意味着一个有效的集合  中的所有单元格，必须全部位于同一行，或者全部位于同一列。任何跨越多行和多列的单元格组合（例如 L 形或  的矩形）都会存在一对不满足条件的单元格。 因此，问题转化为统计两类集合的总数：  所有单元格都在同一行且颜色相同的非空集合。 所有单元格都在同一列且颜...

题目链接 礼物清单 题目描述 旺仔哥哥收到  种不同的礼物（同种礼物彼此完全相同，数量无限）。他准备将礼物放入  个贴有不同名字的盒子中寄给朋友。 打包需满足：  同一盒子内同一种礼物不能出现两次。 每一种礼物至少放入一个盒子（可以放入多个盒子）。  求满足要求的打包方案数量，对  取模。 解题思路 这是一个组合计数问题。由于  种礼物之间的打包决策是相互独立的，我们可以先分析一种礼物有多少种合法的打包方案，然后利用乘法原理推广到所有  种礼物。 1. 单一礼物的打包方案 考虑其中任意一种礼物。我们有  个不同的盒子。  对于盒子1，我们可以选择“放”或“不放”这种礼物，有  种选择。 对于盒...