算法

Hailin

回文字符串

蓝桥杯2024省赛-回文字符串 给定一个只包含小写字母的字符串 S，可以在字符串的开头加入任意数目的指定字符 l、q、b。问是否能通过这种方式将 S 转化为一个回文字符串。 第一行一个整数 T，表示数据组数。 接下来 T 行，每行一个字符串 S。 输出 T 行，每行 Yes 或 No。 输入： 输出： 只能在开头添加字符，新增字符必须与原串末尾的一段相对应。先统计开头连续的 l/q/b 个数 prefix，以及末尾连续的指定字符个数 suffix。全串都是指定字符时直接返回 Yes；否则 suffix 小于 prefix 时无解。 末尾保留 prefix 个字符，与原串开头配对；仅剥离末尾多出的 suffix-prefix 个字符，再判断留下的前缀是否回文。因为第一个和最后一个非指定字符的位置必须对称，需要剥离的数量是确定的。若剩余前缀为回文，在开头补上已剥离部分的逆序即可。 不能直接剥离整个末尾指定字符段：例如 lal 本来就是回文，应保留最后的 l。 不能在匹配完两端后继续跳过中间的不匹配字符，那相当于在原串内部插入字符。例如 alba 应输出 No。 时间复杂度：O(|S|)，每组数据只需一次遍历 空间复杂度：O(1) gmgqlq：末尾指定字符段是 qlq，剩余 gmg 为回文；在开头补 qlq，得到 qlqgmgqlq ✅ pdlbll：剥离末尾 lbll 后，剩余 pd 不是回文，返回 False ❌ aaa：本身是回文 ✅

算法

Hailin

农夫过河问题

一位农夫需要将猫、鸡、米从河的左岸运到右岸。 农夫有一条小船，但船每次只能载农夫本人加上一样东西。 🐱🐔 猫和鸡不能单独待在一起（猫会吃鸡） 🐔🌾 鸡和米不能单独待在一起（鸡会吃米） 🐱🌾 猫和米可以单独待在一起（没有危险） 找到一种安全的搬运顺序，使农夫、猫、鸡、米全部安全到达右岸。 最少需要几步才能完成？ 本题状态空间共 2^4 = 16 种，可利用 BFS 算法求解，也可借助离散数学中的图论方法建模。若使用图论，需将所有状态视为节点，枚举全部路径并剔除非法状态，再求从起点到终点的最短路径。 为什么选择 BFS 而非其他算法？ BFS 按层扩展，第一次到达目标状态时所经过的步数必然最少，因此能保证得到最优解。这正是它在最短路径问题中被广泛使用的原因。 具体实现时，每一步枚举农夫的四种选择（单独过河、带猫、带鸡、带米），对每种选择执行状态转移： 代码逻辑如下： carry = None：农夫单独过河，物品位置不变 carry = 0/1/2：农夫尝试携带猫/鸡/米 若物品与农夫不在同岸 → 跳过 若物品与农夫在同岸 → 将物品位置取反（0→1 或 1→0），完成状态转移 每次得到新状态后，检查其合法性并加入队列，直到到达目标状态为止。

算法

Hailin

埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种简单且古老的算法，用于找出一定范围内所有的素数。其核心思想是从最小的素数开始，逐步标记其倍数为合数，最终未被标记的数即为素数。 创建一个布尔数组 is_prime[0..n]，初始全部设为 True。 将 0 和 1 标记为 False，因为它们不是素数。 从 i = 2 开始，若 i 是素数，则将其所有倍数（从 i*i 开始）标记为 False。 优化：只需遍历到 sqrt(n)，因为大于 sqrt(n) 的倍数会被更小的素数覆盖。 最后，收集所有仍为 True 的索引，即为素数。 时间复杂度：O(n log log n)，非常接近线性。 空间复杂度：O(n)，用于存储布尔数组。

算法

Hailin

排队接水

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Ti，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。 一个人的等待时间不包括他的接水时间。 如果两个人接水的时间相同，编号更小的人应当排在前面。 第一行为一个整数 n。 第二行 n 个整数，第 i 个整数 Ti 表示第 i 个人的接水时间 Ti。 输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

算法

Hailin

洛谷-全排列问题

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 一个整数 n。 由 1 ~ n 组成的所有不重复的数字序列，每行一个序列。 每个数字保留 5 个场宽。 数据范围 1 ≤ n ≤ 9 当前复杂度：O(n!)