Go算法巅峰能力认证
算法启蒙题库 算法进阶题库 算法巅峰题库
❀ 算 法 启 蒙 题 库（共12题）❀ 返回最前
第一章：算法思维基础
试题1、双重循环与九九乘法表
【题目描述】
使用双重循环结构，生成一个标准的九九乘法表。通过这个练习，读者将理解循环嵌套的执行顺序，并掌握如何用代码实现规律的二维表格输出。
【输出结果】
九九乘法表：
1×1= 1
1×2= 2 2×2= 4
1×3= 3 2×3= 6 3×3= 9
1×4= 4 2×4= 8 3×4=12 4×4=16
1×5= 5 2×5=10 3×5=15 4×5=20 5×5=25
1×6= 6 2×6=12 3×6=18 4×6=24 5×6=30 6×6=36
1×7= 7 2×7=14 3×7=21 4×7=28 5×7=35 6×7=42 7×7=49
1×8= 8 2×8=16 3×8=24 4×8=32 5×8=40 6×8=48 7×8=56 8×8=64
1×9= 9 2×9=18 3×9=27 4×9=36 5×9=45 6×9=54 7×9=63 8×9=72 9×9=81
试题2、多重循环与三位水仙花数
【题目描述】
三位水仙花数是一个既有趣又能很好锻炼多重循环思维的经典题目。它指的是一个三位数，其每位数字的3次幂之和恰好等于它本身。比如，经典的例子是153，因为 1³ + 5³ + 3³ = 1 + 125 + 27 = 153。
【输出结果】
三位水仙花数有：
153
370
371
407
试题3、递归算法与爬楼梯
【题目描述】
假设有10级台阶，一次可以爬1级或2级。从地面（第0级）到第10级，有多少种不同的走法？关键在于：到达第10级台阶的前一步，要么站在第9级（爬1级），要么站在第8级（爬2级）。所以，到达第10级的方法数，就是到达第9级和到达第8级的方法数之和。这形成了一个递推关系：f(n) = f(n-1) + f(n-2)。
【输出结果】
爬 10 级台阶，一共有 89 种方法。
试题4、递归算法与斐波那契数列
【题目描述】
斐波那契数列是一个非常有趣的数列，从0和1开始，后面的每一项都是前两项之和。用数学公式表示就是：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （当 n ≥ 2）
数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34…
求斐波那契数列第10项。
【输出结果】
斐波那契数列第10项是: 55
试题5、分治算法与寻找最大值
【题目描述】
给定一个整数列表，请使用分治算法找出其中的最大值。
# 测试示例
numbers = [3, 7, 2, 9, 5, 1, 8, 4]
【输出结果】
列表 [3, 7, 2, 9, 5, 1, 8, 4] 中的最大值为: 9
试题6、分治算法与巧克力分块
【题目描述】
计算将一条由N个小方格组成的长条形巧克力全部掰成1×1小块所需的最少掰断次数。每次操作只能沿直线掰开一块巧克力。使用分治算法设计递归函数，通过将问题分解为子问题来求解。
# 测试不同大小的巧克力
test_sizes = [1, 2, 3, 4, 5, 10]
【输出结果】
巧克力大小(n) | 最少掰断次数：
1 | 0
2 | 1
3 | 2
4 | 3
5 | 4
10 | 9
试题7、贪心算法与零钱兑换
【题目描述】
买零食的零钱兑换：小明想用最少的硬币数来买价值8元的零食。假设现在有面额为1元、2元和5元的硬币，如何用最少的硬币凑出8元？
# 测试数据
amount = 8
coins = [1, 2, 5]
【输出结果】
用最少的硬币凑出8元的方法是：[5, 2, 1]
最少需要3个硬币
试题8、贪心算法与课堂时间安排
【题目描述】
学校每天有多个活动（如语文、数学、英语等课程或社团活动）需要使用同一个教室，每个活动有固定的开始时间和结束时间。由于教室资源有限，需要合理安排活动，使得在一天内能在该教室举行的活动数量最多，且活动时间不冲突。
# 测试数据：活动名, 开始时间, 结束时间
# 使用24小时制时间表示，如900表示9:00
activities = [
(“语文”, 800, 900),
(“数学”, 830, 1000),
(“英语”, 900, 1000),
(“物理”, 1000, 1100),
(“化学”, 1030, 1130),
(“生物”, 1100, 1200)
]
【输出结果】
今日活动安排：
活动名称 开始时间 结束时间
语文 800 900
英语 900 1000
物理 1000 1100
生物 1100 1200
最多可安排 4 个活动
试题9、滑动窗口与最甜3颗糖
【题目描述】
连续3颗糖甜度总和最高：小明有一排糖果，每颗糖都有一个甜度值。现在要找出连续3颗糖甜度总和最高的组合。
例如：糖果甜度：[5, 2, 8, 3, 1]，连续3颗糖的甜度总和：
5+2+8=15
2+8+3=13
8+3+1=12
最高总和是15，对应第1-3颗糖（5, 2, 8）
【输出结果】
最甜的3颗糖是第1-3颗，甜度总和是15，它们是[5, 2, 8]
试题10、滑动窗口与高峰时间段
【题目描述】
公交车高峰时段统计：假设要统计公交车在任意连续5分钟内乘客人数最多的时段，以调整发车间隔。给定一个时间序列，每个数字代表每分钟上车的乘客数。找出连续5分钟内乘客总数的最大值。
# 测试数据：10分钟内每分钟上车的乘客数
passengers = [3, 7, 2, 5, 8, 4, 6, 9, 1, 5]
【输出结果】
连续5分钟内的最大乘客总数为: 32
试题11、算法复杂度-素数判断
【题目描述】
设计一个程序，判断输入的数字是否为素数，并统计1到N之间所有素数的个数。通过逐步优化算法，体会如何通过减少循环次数和提前终止来提升程序效率。（素数定义：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。）
test_numbers = [2, 3, 10, 97, 1009, 10000] # 单独测试的数字
【输出结果】
正确性验证：
数字 2: 基础法=True, 平方根法=True, 6k法=True
数字 3: 基础法=True, 平方根法=True, 6k法=True
数字 10: 基础法=False, 平方根法=False, 6k法=False
数字 97: 基础法=True, 平方根法=True, 6k法=True
数字 1009: 基础法=True, 平方根法=True, 6k法=True
数字 10000: 基础法=False, 平方根法=False, 6k法=False
时间复杂度分析：基础暴力法 O(n)，平方根优化法 O(√n)，6k±1优化法 O(√n/3)
试题12、算法复杂度-百钱买百鸡
【题目描述】
百钱买百鸡问题最早记载于中国南北朝时期的数学著作《张丘建算经》。原题为：“今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？”
用现代数学语言描述，即设公鸡、母鸡、小鸡的数量分别为 x, y, z，可得到如下方程组：
- x+y+z=100（总数约束）
- 5x+3y+3z=100（总钱约束）
- x,y,z均为非负整数，且 z必须是 3 的倍数。
【输出结果】
暴力枚举结果： [(0, 25, 75), (4, 18, 78), (8, 11, 81), (12, 4, 84)]
约束与消元优化结果： [(0, 25, 75), (4, 18, 78), (8, 11, 81), (12, 4, 84)]
数学解析结果： [(0, 25, 75), (4, 18, 78), (8, 11, 81), (12, 4, 84)]
❀ 算 法 进 阶 题 库（共28题）❀ 返回最前
第二章：数据结构
试题13、链表与约瑟夫问题-猴子选大王
【题目描述】
n只猴子围成一圈，按1~n编号。从第1只开始报数，报到m的猴子出圈，再从下一只重新报数。最后剩下的猴子就是大王。
# 测试：7只猴子，数到3出圈,求解剩下的猴王是第几只？
【输出结果】
有7只猴子，数到3出圈
最后大王的编号是: 4
试题14、栈-括号匹配问题
【题目描述】
假设一个表达式由英文字母（小写）、运算符（+、-、*、/）和左右小括号构成，以”@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配则输出”YES”，否则输出”NO”。表达式长度小于255，左圆括号少于20个。
样例输入1：
2*(x+y)/(1-x)@
样例输出1：
YES
样例输入2：
((a+b)*c@
样例输出2：
NO
【输出结果】
括号匹配测试结果：
测试1: 2(x+y)/(1-x) → YES
测试2: ((a+b)c → NO
测试3: (a+b)(c-d) → YES
测试4: a+b)c → NO
测试5: ((a+b) → NO
试题15、队列-基本操作
【题目描述】
初始时队列中有10个元素，从队首到队尾依次为：2, 3, 1, 5, 4, 6, 7, 3, 2, 8。要求每次从队首取出两个元素，若两数奇偶性相同，则将它们的和加入队列；否则，将它们的乘积加入队列。最终队列中会只剩下一个元素，求这个元素的数值。
【输出结果】
初始队列: [2, 3, 1, 5, 4, 6, 7, 3, 2, 8]
第1步: 取出(2, 3), 2 × 3 = 6, 新队列: [1, 5, 4, 6, 7, 3, 2, 8, 6]
第2步: 取出(1, 5), 1 + 5 = 6, 新队列: [4, 6, 7, 3, 2, 8, 6, 6]
第3步: 取出(4, 6), 4 + 6 = 10, 新队列: [7, 3, 2, 8, 6, 6, 10]
第4步: 取出(7, 3), 7 + 3 = 10, 新队列: [2, 8, 6, 6, 10, 10]
第5步: 取出(2, 8), 2 + 8 = 10, 新队列: [6, 6, 10, 10, 10]
第6步: 取出(6, 6), 6 + 6 = 12, 新队列: [10, 10, 10, 12]
第7步: 取出(10, 10), 10 + 10 = 20, 新队列: [10, 12, 20]
第8步: 取出(10, 12), 10 + 12 = 22, 新队列: [20, 22]
第9步: 取出(20, 22), 20 + 22 = 42, 新队列: [42]
最终剩余元素为: 42
试题16、字典-不重复数字
【题目描述】
给定n个数，要求把其中重复的去掉，只保留第一次出现的数。
输入格式：
- 本题有多组数据。
- 第一行一个整数T，表示数据组数。
- 对于每组数据：
- 第一行一个整数n。
- 第二行n个数，表示给定的数。
输出格式：
- 对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。
数据范围：
- 对于30%的数据，n ≤ 100，给出的数 ∈ [0, 100]
- 对于60%的数据，n ≤ 10⁴，给出的数 ∈ [0, 10⁴]
- 对于100%的数据，1 ≤ T ≤ 50，1 ≤ n ≤ 5 × 10⁴，给出的数在32位有符号整数范围内
输入格式：
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6
【输出结果】
测试用例（字典版本）：
1 2 18 3 19 6 5 4
1 2 3 4 5 6
试题17、集合-不重复数字
【题目描述】
给定n个数，要求把其中重复的去掉，只保留第一次出现的数。
输入格式：
- 本题有多组数据。
- 第一行一个整数T，表示数据组数。
- 对于每组数据：
- 第一行一个整数n。
- 第二行n个数，表示给定的数。
输出格式：
- 对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。
数据范围：
- 对于30%的数据，n ≤ 100，给出的数 ∈ [0, 100]
- 对于60%的数据，n ≤ 10⁴，给出的数 ∈ [0, 10⁴]
- 对于100%的数据，1 ≤ T ≤ 50，1 ≤ n ≤ 5 × 10⁴，给出的数在32位有符号整数范围内
输入格式：
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6
【输出结果】
测试用例（集合版本）：
1 2 18 3 19 6 5 4
1 2 3 4 5 6
试题18、字典与集合-扑克牌
【题目描述】
完整的一副牌有52张，每一张牌由点数和花色构成，它们互不相同。其中点数为2,3,4,5,6,7,8,9,T,J,Q,K,A，花色为C,D,H,S。
现在手头有一些牌，请问需要再添加至少多少张牌，可以构造出一副完整的牌。
输入格式：
- 第一行包含一个整数n，表示手中已有的牌数
- 接下来n行，每行包含一个字符串，表示一张牌，格式为”点数花色”，如”2C”表示梅花2
输出格式：
- 输出一个整数，表示需要添加的最少牌数
数据范围：
- 1 ≤ n ≤ 52
- 保证输入的牌都是合法的，且可能重复
输入：
5
2C
3D
4H
5S
2C
输出：
48
【最终输出结果】
测试用例1（集合方法）：
48
测试用例2（列表+集合方法）：
48
测试用例3（字典计数方法）：
48
不重复的牌数：4
有1张重复的牌
边界测试：已经有52张不同的牌
测试只有1张牌的情况：
51
试题19、二叉树-遍历
【题目描述】
给定一棵二叉树的中序遍历序列和后序遍历序列，请你输出其层序遍历序列。
输入格式：
第一行包含一个整数N（1≤N≤30），表示树中节点的个数。
第二行包含N个整数，表示二叉树的中序遍历序列。
第三行包含N个整数，表示二叉树的后序遍历序列。
节点编号为1到N的整数，且每个编号在序列中只出现一次。
输出格式：
输出一行，包含N个整数，表示二叉树的层序遍历序列。
输入：
7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
【输出结果】
1 2 3 4 5 6 7
试题20、二叉树-叶子节点计算
题目背景：这是二叉树基础题目的常见形式，考察对树结构的理解和基本递归应用。
【题目描述】
给定一棵二叉树的层序遍历序列（用-1表示空节点），请你计算这棵二叉树的叶子节点个数。
输入格式：
第一行包含一个整数N（1≤N≤1000），表示序列中元素个数（包含空节点标记）。
第二行包含N个整数，表示二叉树的层序遍历序列，其中-1表示空节点。
树根是序列的第一个非-1元素。
输出格式：
输出一个整数，表示叶子节点的个数。
输入：
15
1 2 3 4 5 -1 7 -1 -1 8 -1 -1 -1 -1 9
（这棵树的结构：节点1有两个孩子2和3，节点2有孩子4和5，节点3有右孩子7，节点5有左孩子8，节点7有右孩子9）
【输出结果】
3
（叶子节点是：4, 8, 9）
第三章：查找与排序
试题21、线性查找-查找数组中的最值
【题目描述】
给定一个包含n个整数的数组，请找出数组中的最大值和最小值。
输入格式：
第一行包含一个整数n（1≤n≤1000），表示数组元素的个数。
第二行包含n个整数，每个整数之间用空格分隔。
输出格式：
输出两个整数，分别表示数组中的最大值和最小值，用空格分隔。
输入：
6
5 2 9 1 5 6
【输出结果】
9 1
试题22、线性查找-珠心算测验
【题目描述】
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？
输入格式：
共两行，第一行包含一个整数n（3≤n≤100），表示测试题中给出的正整数个数。
第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数（大小不超过10,000）。
输出格式：
一个整数，表示测验题答案。
输入：
4
1 2 3 4
【输出结果】
2
样例说明：
由1+2=3，1+3=4，故满足测试要求的答案为2。注意，加数和被加数必须是集合中的两个不同的数。
试题23、二分查找-解密
【题目描述】
给定一个正整数k，有k次询问，每次给定三个正整数ni, ei, di，求两个正整数pi, qi，使得：
- ni = pi × qi
- ei × di = (pi – 1)(qi – 1) + 1
如果无解，输出”NO”。为使输出统一，保证pi ≤ qi。
输入格式：
- 第一行：一个正整数k，表示询问次数
- 接下来k行：每行三个正整数ni, di, ei
输入：
10
770 77 56
33 1 2
11545 1 4996
83 3 227
858 3 257
723 37 13
572 26 11
867 17 1
7829 3 263
528 4 109
【输出结果】
NO
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
试题24、二分查找-和为给定数
【题目描述】
给出若干个整数，询问其中是否有一对数的和等于给定的数。
输入格式：
- 第一行是整数n（0 < n ≤ 100,000），表示有n个整数。
- 第二行是n个整数。整数的范围是在0到10^8之间。
- 第三行是一个整数m（0 ≤ m ≤ 2^30），表示需要得到的和。
输出格式：
若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行”No”。
输入：
6
2 5 1 3 7 8
6
【输出结果】
1 5
试题25、选择排序-基础应用
【题目描述】
实现选择排序算法对多组测试数据进行升序排序。
输入格式：
- 第一行是一个正整数 T，表示测试数据组数
- 对于每组测试数据：
- 第一行有一个正整数 n (1 ≤ n ≤ 100)
- 接下来有 n 个空格分隔的非负整数 ai (0 ≤ ai < 50)
输出格式：
针对每一组测试案例，在单独一行上打印出经过升序处理后的数字列表，相邻两个数之间用单个空格分隔。
输入：
2
4
98 36 74 12
5
3 7 9 1 5
【输出结果】
12 36 74 98
1 3 5 7 9
试题26、选择排序-奖学金名单
【题目描述】
某小学为学习成绩优秀的前5名学生发奖学金。每个学生有3门课成绩：语文、数学、英语。排序规则如下：
- 按总分从高到低排序
- 如果总分相同，按语文成绩从高到低排序
- 如果总分和语文成绩都相同，学号小的同学排在前面
输入格式：
- 第1行：正整数n，表示学生人数
- 第2到n+1行：每行3个用空格隔开的数字，表示学号为j-1的学生的语文、数学、英语成绩
输出格式：
共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。
输入：
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
【输出结果】
6 265
4 264
3 258
2 244
1 237
试题27、冒泡排序-最少比较次数
【题目描述】
冒泡排序算法的伪代码如下：
输入：数组L，n ≥ k
输出：按非递减顺序排序的L
算法 BubbleSort:
- FLAG ← n //标记被交换的最后元素位置
- while FLAG > 1 do
- k ← FLAG – 1
- FLAG ← 1
- for j = 1 to k do
- if L(j) > L(j+1) then do
- L(j) ↔ L(j+1)
- FLAG ← j
对n个数用以上冒泡排序算法进行排序，最少需要比较多少次？
输出结果
最少需要比较 n-1 次
输入：
# 测试：数组本身已经有序的情况
test_arr = [1, 2, 3, 4, 5]
# 对比测试：完全逆序的情况
reverse_arr = [5, 4, 3, 2, 1]
【输出结果】
原始数组: [1, 2, 3, 4, 5]
排序后数组: [1, 2, 3, 4, 5]
比较次数: 4
数组长度n: 5
最少比较次数理论值: n-1 = 4
完全逆序数组比较次数: 10
理论最大比较次数: n(n-1)/2 = 10
试题28、冒泡排序-逆序对关系
【题目描述】
使用冒泡排序对序列进行升序排列，每执行一次交换操作将会减少1个逆序对，因此序列：5, 4, 3, 2, 1需要执行多少次交换操作，才能完成冒泡排序？
输出结果:
需要执行 10 次交换操作
输入：
# 测试序列：5, 4, 3, 2, 1
test_sequence = [5, 4, 3, 2, 1]
# 扩展：其他序列测试
test_cases = [
[1, 2, 3, 4, 5], # 已有序，逆序对为0
[3, 1, 4, 1, 5], # 部分有序
[5, 1, 4, 2, 3], # 随机序列
]
【输出结果】
序列: [5, 4, 3, 2, 1]
逆序对数量（理论交换次数）: 10
排序后序列: [1, 2, 3, 4, 5]
实际交换次数: 10
验证：交换次数10 = 逆序对数量10？ True
其他序列测试：
序列[1, 2, 3, 4, 5]: 逆序对=0, 交换次数=0, 是否相等？True
序列[3, 1, 4, 1, 5]: 逆序对=3, 交换次数=3, 是否相等？True
序列[5, 1, 4, 2, 3]: 逆序对=6, 交换次数=6, 是否相等？True
试题29、插入排序-基本实现
【题目描述】
插入排序基础实现题
题目描述：实现插入排序算法对给定数组进行升序排序。插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从前向后扫描，找到相应位置并插入。
输入格式：
- 第一行：整数N（2 ≤ N ≤ 100），表示待排序元素个数
- 第二行：N个整数，表示待排序的元素
输出格式：
- 一行，按升序排列的序列
输入：
# 测试用例1
arr1 = [34, 8, 64, 51, 32, 21]
# 测试用例2：已部分有序的数组
arr2 = [1, 3, 5, 2, 4, 6]
# 测试二分查找优化的插入排序
arr3 = [34, 8, 64, 51, 32, 21]
# 插入排序逐步演示
arr = [5, 2, 4, 6, 1, 3]
【输出结果】
=== 基础插入排序测试 ===
原始数组: [34, 8, 64, 51, 32, 21]
第1轮排序后: [8, 34, 64, 51, 32, 21]
第2轮排序后: [8, 34, 64, 51, 32, 21]
第3轮排序后: [8, 34, 51, 64, 32, 21]
第4轮排序后: [8, 32, 34, 51, 64, 21]
第5轮排序后: [8, 21, 32, 34, 51, 64]
最终排序结果: [8, 21, 32, 34, 51, 64]
部分有序数组: [1, 3, 5, 2, 4, 6]
第1轮排序后: [1, 3, 5, 2, 4, 6]
第2轮排序后: [1, 3, 5, 2, 4, 6]
第3轮排序后: [1, 2, 3, 5, 4, 6]
第4轮排序后: [1, 2, 3, 4, 5, 6]
第5轮排序后: [1, 2, 3, 4, 5, 6]
最终排序结果: [1, 2, 3, 4, 5, 6]
=== 二分查找优化版插入排序 ===
原始数组: [34, 8, 64, 51, 32, 21]
第1轮（二分优化）: [8, 34, 64, 51, 32, 21]
第2轮（二分优化）: [8, 34, 64, 51, 32, 21]
第3轮（二分优化）: [8, 34, 51, 64, 32, 21]
第4轮（二分优化）: [8, 32, 34, 51, 64, 21]
第5轮（二分优化）: [8, 21, 32, 34, 51, 64]
最终排序结果: [8, 21, 32, 34, 51, 64]
=== 插入排序逐步演示 ===
初始数组: [5, 2, 4, 6, 1, 3]
插入2后: 2, 5, 4, 6, 1, 3
插入4后: 2, 4, 5, 6, 1, 3
…后续步骤类似
试题30、插入排序-四数排序
【题目描述】
阅读以下程序，分析其功能并回答问题。程序首先对三个整数a1、a2、a3进行排序，然后读入第四个整数x，将x插入到已排序的三个数中的合适位置，使得四个数保持升序排列。
程序伪代码：
输入a1, a2, a3
// 对a1, a2, a3进行排序（使用冒泡排序思想）
if a1 > a2: swap(a1, a2)
if a2 > a3: swap(a2, a3)
if a1 > a2: swap(a1, a2)
输入x
// 将x插入到合适位置
if x < a1:
输出 x, a1, a2, a3
else if x < a2:
输出 a1, x, a2, a3
else if x < a3:
输出 a1, a2, x, a3
else:
输出 a1, a2, a3, x
输入：
# 测试用例1
a1, a2, a3, x = 91, 2, 20, 77
# 测试用例2
a1, a2, a3, x = 5, 4, 3, 2
# 测试数组
arr1 = [34, 8, 64, 51, 32, 21]
# 测试已部分有序的数组
arr2 = [1, 3, 5, 2, 4, 6]
【输出结果】
=== NOIP插入排序测试 ===
排序后的三个数: 2, 20, 91
输入: a1=91, a2=2, a3=20, x=77
输出: [2, 20, 77, 91]
预期: [2, 20, 77, 91]
测试通过: True
排序后的三个数: 3, 4, 5
输入: a1=5, a2=4, a3=3, x=2
输出: [2, 3, 4, 5]
预期: [2, 3, 4, 5]
测试通过: True
=== 通用插入排序测试 ===
原始数组: [34, 8, 64, 51, 32, 21]
第1轮插入后: [8, 34, 64, 51, 32, 21]
第2轮插入后: [8, 34, 64, 51, 32, 21]
第3轮插入后: [8, 34, 51, 64, 32, 21]
第4轮插入后: [8, 32, 34, 51, 64, 21]
第5轮插入后: [8, 21, 32, 34, 51, 64]
最终排序结果: [8, 21, 32, 34, 51, 64]
部分有序数组: [1, 3, 5, 2, 4, 6]
第1轮插入后: [1, 3, 5, 2, 4, 6]
第2轮插入后: [1, 3, 5, 2, 4, 6]
第3轮插入后: [1, 2, 3, 5, 4, 6]
第4轮插入后: [1, 2, 3, 4, 5, 6]
第5轮插入后: [1, 2, 3, 4, 5, 6]
最终排序结果: [1, 2, 3, 4, 5, 6]
试题31、快速排序-时间复杂度
【题目描述】
假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程中总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为？
A. 快速排序对于此类输入的表现最好，因为数组已经排序
B. 快速排序对于此类输入的时间复杂度是 O(nlogn)
C. 快速排序对于此类输入的时间复杂度是 O(n²)
D. 快速排序无法对此类数组进行排序，因为数组已经排序
正确答案：C
输入验证：
# 已排序数组
sorted_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
【输出结果】
原始数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
排序后数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
递归调用分析:
当数组已排序且选择第一个元素为基准时：
每次划分只能将数组分为1个元素和n-1个元素两部分
递归深度达到n层，时间复杂度为O(n²)
试题32、快速排序-明明随机数
【题目描述】
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成”去重”与”排序”的工作。
输入格式：
- 第1行为1个正整数，表示所生成的随机数的个数：N
- 第2行有N个用空格隔开的正整数，为所产生的随机数
输出格式：
- 第1行为1个正整数M，表示不相同的随机数的个数
- 第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数
输入：
10
20 40 32 67 40 20 89 300 400 15
【输出结果】
8
15 20 32 40 67 89 300 400
试题33、归并排序-基本实现
【题目描述】
归并排序实现：给定一个长度为n的整数数列，请你使用归并排序对这个数列按照从小到大进行排序，并将排好序的数列按顺序输出。
输入格式：
- 第一行包含整数n
- 第二行包含n个整数（所有整数均在1~10^9范围内）
输出格式：
输出共一行，包含n个整数，表示排好序的数列
数据范围：
1 ≤ n ≤ 100000
输入：
5
3 1 2 4 5
【输出结果】
1 2 3 4 5
试题34、归并排序-瑞士轮
【题目描述】
问题描述：2×N名编号为1~2N的选手共进行R轮比赛。每轮比赛前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分总和。总分相同的，约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第2K-1名和第2K名、……、第2N-1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分。
现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号。
输入格式：
第一行是三个正整数N、R、Q，每两个数之间用一个空格隔开
第二行有2N个非负整数s₁, s₂, …, s₂N，每两个数之间用一个空格隔开，其中s_i表示编号为i的选手的初始分数
第三行有2N个正整数w₁, w₂, …, w₂N，每两个数之间用一个空格隔开，其中w_i表示编号为i的选手的实力值
输出格式：
一个整数，即R轮比赛结束后，排名第Q的选手的编号
数据范围：
1 ≤ N ≤ 100,000，1 ≤ R ≤ 50，1 ≤ Q ≤ 2N
0 ≤ s_i ≤ 10^8，1 ≤ w_i ≤ 10^8
输入：
2 4 2
7 6 6 7
10 5 20 15
【输出结果】
1
试题35、堆排序-小根堆应用
【题目描述】
输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式：
- 第一行包含整数n和m
- 第二行包含n个整数，表示整数数列
输出格式：
- 共一行，包含m个整数，表示整数数列中前m小的数
数据范围：1≤m≤n≤10⁵，1≤数列中元素≤10⁹
输入：
5 3
4 5 1 3 2
【输出结果】
1 2 3
试题36、堆排序-合并果子问题
【题目描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
输入格式：
- 第一行：整数n(1≤n≤10000)，表示果子的种类数
- 第二行：n个整数，用空格分隔，第i个整数ai(1≤ai≤20000)是第i种果子的数目
输出格式：
- 一个整数，表示最小的体力耗费值
输入：
3
1 2 9
【输出结果】
15
试题37、计数排序-双关键字场景
【题目描述】
计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。例如有三对整数(3,4)、(2,4)、(3,3)，那么排序之后应该是(2,4)、(3,3)、(3,4)。输入第一行为n，接下来n行，第i行有两个数a[i]和b[i]，分别表示第i对整数的第一关键字和第二关键字。从小到大排序后输出。
数据范围：1 < n < 10⁷，1 < a[i], b[i] < 10⁴
提示：应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第二关键字排序的结果，数组res[]存储双关键字排序的结果。
输入：
3
3 4
2 4
3 3
【输出结果】
2 4
3 3
3 4
试题38、计数排序-明明随机数
【题目描述】
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数(N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成”去重”与”排序”的工作。
输入格式：
- 第1行为1个正整数，表示所生成的随机数的个数：N
- 第2行有N个用空格隔开的正整数，为所产生的随机数
输出格式：
- 第1行为1个正整数M，表示不相同的随机数的个数
- 第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数
输入：
10
20 40 32 67 40 20 89 300 400 15
【输出结果】
8
15 20 32 40 67 89 300 400
试题39、希尔排序-过程演示
【题目描述】
希尔排序是一种改进的插入排序算法。给定一个整数序列和增量序列，请实现希尔排序算法，并输出每趟排序后的结果。
输入格式：
- 第一行：整数n(1≤n≤1000)，表示序列长度
- 第二行：n个整数，表示待排序序列
- 第三行：整数m，表示增量序列长度
- 第四行：m个整数，表示增量序列（保证最后一个增量为1）
输出格式：
输出m行，每行表示对应增量排序后的序列
输入：
10
49 38 65 97 76 13 27 49 55 4
3
5 3 1
【输出结果】
13 27 49 55 4 49 38 65 97 76
13 4 49 38 27 49 55 65 97 76
4 13 27 38 49 49 55 65 76 97
试题40、希尔排序-增量分析
【题目描述】
对序列{98, 36, -9, 0, 47, 23, 1, 8, 10, 7}采用希尔排序，请编写程序验证增量为4的一趟排序结果，并输出排序过程。
输入格式：无输入，使用固定测试数据
输出格式：
- 第一行输出原始序列
- 第二行输出增量为4的分组情况
- 第三行输出每组排序结果
- 第四行输出最终一趟排序结果
【输出结果】
原始序列: [98, 36, -9, 0, 47, 23, 1, 8, 10, 7]
增量gap=4的分组:
第1组(索引0,4,8): [98, 47, 10] -> 排序后: [10, 47, 98]
第2组(索引1,5,9): [36, 23, 7] -> 排序后: [7, 23, 36]
第3组(索引2,6): [-9, 1] -> 排序后: [-9, 1]
第4组(索引3,7): [0, 8] -> 排序后: [0, 8]
增量为4的一趟排序结果: [10, 7, -9, 0, 47, 23, 1, 8, 98, 36]
❀ 算 法 巅 峰 题 库（共60题）❀ 返回最前
第四章：搜索与图论
41、深度优先搜索DFS-迷宫最短路径问题
【题目描述】
给定一个N×M的迷宫，用数字表示地图：
- 0 表示通路，可以通过
- 1 表示障碍物，不可通过
从起点(sx, sy)到终点(ex, ey)，只能向上、下、左、右四个方向移动。请找出从起点到终点的最短路径长度，并输出一条最短路径。如果无法到达，输出-1。
输入格式：
- 第一行：两个整数N和M（1≤N,M≤100）
- 接下来N行：每行M个整数（0或1）
- 最后一行：四个整数sx, sy, ex, ey（1-based坐标）
输出格式：
- 第一行：最短路径长度
- 第二行开始：输出路径坐标，格式为”(x,y) (x,y) …”
输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 1
0 0 0 0 0
1 1 5 5
【输出结果】
8
(1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (5,4) (5,5)
42、广度优先搜索BFS-迷宫最短路径问题
【题目描述】
给定一个N×M的迷宫，用数字表示地图：
- 0 表示通路，可以通过
- 1 表示障碍物，不可通过
从起点(sx, sy)到终点(ex, ey)，只能向上、下、左、右四个方向移动。请计算从起点到终点的最短路径长度（步数）。
输入格式：
- 第一行：两个整数N和M（1≤N,M≤100）
- 接下来N行：每行M个整数（0或1）
- 最后一行：四个整数sx, sy, ex, ey（1-based坐标）
输出格式：
- 一个整数，表示最短路径长度。如果无法到达，输出-1
输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 1
0 0 0 0 0
1 1 5 5
【输出结果】
8
43、图的遍历DFS-石油探测
【题目描述】
地质勘探公司正在探测地下油田。他们使用一个网格来表示探测区域，网格中的每个单元格要么是’@’（表示有油），要么是’*’（表示无油）。如果两个’@’单元格在水平、垂直或对角方向上相邻（8个方向），则认为它们属于同一个油田。你的任务是计算网格中有多少个不同的油田。
输入格式：
- 输入包含多个测试用例
- 每个测试用例的第一行包含两个整数m和n（1 ≤ m, n ≤ 100），表示网格的行数和列数
- 接下来m行，每行n个字符，表示网格
- 输入以”0 0″结束
输出格式：
- 对于每个测试用例，输出油田的数量
输入：
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
0 0
【输出结果】
0
1
2
44、图的遍历BFS-公路旅行
【题目描述】
某地区有n个城市（编号1~n），m条双向公路，每条公路连接两个城市，长度为1。给定起点s和终点t，求从s到t的最短路径长度，若无法到达输出-1。
输入格式：
- 第一行两个整数n,m，表示点数和边数
- 接下来m行，每行两个整数u,v，表示一条双向公路
- 最后一行两个整数s,t，表示起点和终点
数据范围：
- 1≤n≤1000，1≤m≤10000
输入：
5 5
1 2
1 3
2 4
3 4
4 5
1 5
【输出结果】
3
45、进阶搜索回溯算法-N皇后问题
【题目描述】
在一个如下的6×6的跳棋棋盘上放置6个皇后，要求每行、每列有且只有一个皇后，每条对角线（包括两条主对角线的所有平行线）上至多有一个皇后。请编写程序找出所有棋子放置的解，并按字典顺序排列输出前3个解，最后一行输出解的总个数。
输入格式：一个整数n（6）
输出格式：
前3个解（每行表示一个解，数字表示第i行皇后所在的列），最后一行是解的总数
【输出结果】
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
（注：对于6皇后问题，实际有4个解，这里展示前3个）
46、进阶搜索回溯算法-数独求解
【题目描述】
编写一个程序来解决数独问题。数独是一个9×9的网格，被分成9个3×3的子网格。网格的某些单元格中已经填入了数字（1-9），其他单元格为空。目标是用数字1-9填充所有空单元格，使得：
- 每行包含数字1-9且不重复
- 每列包含数字1-9且不重复
- 每个3×3子网格包含数字1-9且不重复
输入格式：
输入包含9行，每行9个字符。字符可以是数字1-9或点号’.’（表示空单元格）。
输出格式：
输出解出的数独棋盘，格式与输入相同。如果有多解，输出任意一个解即可。
【输出结果】
解出的数独：
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
47、搜索优化迭代加深搜索IDDFS-埃及分数问题
【题目描述】
在古埃及，人们使用单位分数的和（形如1/a的分数，a是自然数）表示一切有理数。如：2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为加数中有相同的。对于一个分数a/b，表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好；其次，加数个数相同的，最小的分数越大越好。
例如：19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18
最好的是最后一种，因为1/18比1/180、1/45、1/30、1/180都大。
给出a,b(0<a<b<1000)，编程计算最好的表达方式。
输入：
19 45
【输出结果】
5 6 18
解释：19/45 = 1/5 + 1/6 + 1/18
48、最短路径Dijkstra算法-最短距离
【题目描述】
如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是多少？
（图结构：A-B(3), A-G(4), A-F(6), B-C(1), B-D(7), C-E(8), C-F(1), C-G(2), D-E(4), D-F(2), F-E(6), G-D(4)）
【输出结果】
从A到E的最短距离为：11
49、最短路径Bellman-Ford算法-有边数限制的最短路
【题目描述】
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出”impossible”。
注意：图中可能存在负权回路。
输入格式：
- 第一行包含三个整数n, m, k
- 接下来m行，每行包含三个整数x, y, z，表示存在一条从点x到点y的有向边，边长为z
输出格式：
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。如果不存在满足条件的路径，则输出”impossible”。
测试示例1（正常情况）：
输入：n=3, m=3, k=1, edges=[(1, 2, 1), (2, 3, 1), (1, 3, 3)]
输出：3
测试示例2（存在负权边）：
输入：n=3, m=3, k=2, edges=[(1, 2, 1), (2, 3, -2), (1, 3, 4)]
输出：-1
测试示例3（不可达）：
输入：n=3, m=2, k=1, edges=[(1, 2, 1), (2, 1, 1)]
输出：impossible
50、最短路径SPFA算法-判断负环
【题目描述】
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。
输入格式：
- 第一行包含整数n和m
- 接下来m行每行包含三个整数x, y, z，表示存在一条从点x到点y的有向边，边长为z
输出格式：
如果图中存在负权回路，则输出”Yes”，否则输出”No”。
【输出结果】
SPFA负环检测测试
========================================
测试1：存在负环
图1: [(1, 2, -1), (2, 3, 4), (3, 1, -4)]
是否存在负环: Yes
测试2：不存在负环
图2: [(1, 2, 1), (2, 3, 2), (1, 3, 4)]
是否存在负环: No
测试3：复杂负环
图3: [(1, 2, 1), (2, 3, -3), (3, 4, 2), (4, 2, -1), (2, 1, -2)]
是否存在负环: Yes
测试4：自环负权
图4: [(1, 1, -5), (1, 2, 3), (2, 1, 2)]
是否存在负环: Yes
51、最小生成树Kruskal算法-无向图应用
【题目描述】
给出一个无向图，求出最小生成树。如果该图不连通，则输出”orz”。
输入格式：
- 第一行包含两个整数n,m，表示该图共有n个结点和m条无向边
- 接下来m行每行包含三个整数u,v,w，表示有一条长度为w的无向边连接结点u,v
输出格式：
- 如果该图连通，则输出一个整数表示最小生成树的各边的长度之和
- 如果该图不连通则输出”orz”
输入：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
【输出结果】
7
52、最小生成树Prim算法-最小费用
【题目描述】
给你一个points数组，表示平面上的点，其中points[i] = [xi, yi]。连接点[xi, yi]和点[xj, yj]的费用为它们之间的曼哈顿距离：|xi – xj| + |yi – yj|。请你返回将所有点连接的最小总费用。只有任意两点之间有且仅有一条路径时，才认为所有点都已连接。
输入格式：
- points：二维整数数组，表示点的坐标
输出格式：
- 整数，表示最小总费用
【输出结果】
输入: [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
堆优化Prim结果: 20, 期望: 20, 正确
朴素Prim结果: 20, 期望: 20, 正确
--------------------------------------------------
输入: [[3, 12], [-2, 5], [-4, 1]]
堆优化Prim结果: 18, 期望: 18, 正确
朴素Prim结果: 18, 期望: 18, 正确
--------------------------------------------------
输入: [[0, 0], [1, 1], [1, 0], [-1, 1]]
堆优化Prim结果: 4, 期望: 4, 正确
朴素Prim结果: 4, 期望: 4, 正确
--------------------------------------------------
53、拓扑排序Kahn算法-课程表
【题目描述】
现在你总共有numCourses门课需要选，记为0到numCourses-1。给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]，表示在选修课程ai前必须先选修bi。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。
输入格式：
- numCourses：课程数量
- prerequisites：先修关系列表，每个元素为[ai, bi]表示ai依赖于bi
输出格式：
- 可行的学习顺序列表，如果无法完成返回空列表
【输出结果】
测试用例 1:
课程数: 2
先修关系: [[1, 0]]
✓ 测试通过，拓扑排序结果: [0, 1]
测试用例 2:
课程数: 4
先修关系: [[1, 0], [2, 0], [3, 1], [3, 2]]
✓ 测试通过，拓扑排序结果: [0, 1, 2, 3]
测试用例 3:
课程数: 1
先修关系: []
✓ 测试通过，拓扑排序结果: [0]
测试用例 4:
课程数: 3
先修关系: [[1, 0], [1, 2], [0, 1]]
✓ 测试通过，正确检测到环
测试用例 5:
课程数: 5
先修关系: [[1, 0], [2, 1], [3, 2], [4, 3], [0, 4]]
✓ 测试通过，正确检测到环
==================================================
=== 课程表 - 拓扑排序示例 ===
示例输入:
课程数量: 4
先修关系: [[1,0],[2,0],[3,1],[3,2]]
拓扑排序结果:
[0, 1, 2, 3]
学习顺序解释:
第1学期: 学习课程0
第2学期: 学习课程1
第3学期: 学习课程2
第4学期: 学习课程3
54、强连通分量Kosaraju算法-信息传递
【题目描述】
有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中第i个同学的信息传递对象是Ti同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉自己的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入格式：
第一行包含一个正整数n，表示人数
第二行包含n个正整数T1,T2,…,Tn，其中第i个整数Ti表示第i个同学的信息传递对象是Ti同学，Ti保证是1到n之间的整数，且Ti≠i
输出格式：
一个整数，表示游戏可以进行多少轮
输入：
5
2 4 2 3 1
【输出结果】
3
55、强连通分量Tarjan算法-信息传递
【题目描述】
有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中第i个同学的信息传递对象是Ti同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉自己的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入格式：
第一行包含一个正整数n，表示人数
第二行包含n个正整数T1,T2,…,Tn，其中第i个整数Ti表示第i个同学的信息传递对象是Ti同学，Ti保证是1到n之间的整数，且Ti≠i
输出格式：
一个整数，表示游戏可以进行多少轮
输入：
5
2 4 2 3 1
【输出结果】
3
第五章：动态规划与贪心算法
56、经典线性DP模型-爬楼梯问题
【题目描述】
假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入格式：一个正整数 n (1 ≤ n ≤ 45)，表示楼梯的阶数。
输出格式：一个整数，表示爬到楼顶的不同方法数。
输入：
10
【输出结果】
89
57、经典线性DP-最长上升子序列（LIS）
【题目描述】
一个数的序列bi，当b₁ < b₂ < … < bₛ的时候，我们称这个序列是上升的。对于给定的一个序列(a₁, a₂, …, aₙ)，我们可以得到一些上升的子序列(aᵢ₁, aᵢ₂, …, aᵢₖ)，这里1 ≤ i₁ < i₂ < … < iₖ ≤ N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入格式：
- 第一行：序列的长度N (1 ≤ N ≤ 1000)
- 第二行：N个整数，取值范围在0到10000
输出格式：最长上升子序列的长度
输入：
7
1 7 3 5 9 4 8
【输出结果】
4
58、0/1背包问题-开心的金明
【题目描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：”你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
输入格式：
- 第1行：两个正整数N和m（N<30000，m<25）
- 第2行到第m+1行：每行有2个非负整数v和p（v≤10000，1≤p≤5）
输出格式：一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值
输入：
1000 5
800 2
400 5
300 5
400 3
200 2
【输出结果】
3900
59、完全背包问题-疯狂的采药
【题目描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：”孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
与0/1背包的区别：每种草药可以无限次采摘（完全背包），而0/1背包中每种草药只能采一次。
输入格式：
- 第一行有2个整数T(1≤T≤100000)和M(1≤M≤10000)，用一个空格隔开
- T代表总共能够用来采药的时间，M代表山洞里的草药的数目
- 接下来的M行每行包括两个在1到10000之间的整数，分别表示采摘某株草药的时间和这株草药的价值
输出格式：在规定的时间内可以采到的草药的最大总价值
输入：
70 3
71 100
69 1
1 2
【输出结果】
140
60、多重背包问题-砝码称重
【题目描述】
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重≤1000），可以表示成多少种重量？
输入格式：
输入方式：a₁ a₂ a₃ a₄ a₅ a₆（表示1g砝码有a₁个，2g砝码有a₂个，…，20g砝码有a₆个）
输出格式：
输出方式：Total=N（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
输入：
1 1 0 0 0 0
【输出结果】
Total=3
61、区间DP-括号匹配问题
【题目描述】
给定一个只包含 ‘(‘, ‘)’, ‘[‘, ‘]’ 四种字符的字符串，求该字符串中满足完全匹配的括号的最大数量。括号匹配规则如下：
- ()是一对匹配的括号
- []是一对匹配的括号
- 如果A和B都是匹配的括号序列，那么AB也是匹配的括号序列
- 如果A是匹配的括号序列，那么(A)和[A]也是匹配的括号序列
输入格式：
多组测试数据，每组数据一行字符串（长度不超过100）。输入以字符串”end”结束。
输出格式：
对于每组测试数据，输出最大匹配括号数。
输入：
((()))
()()()
([]])
)[)(
end
【输出结果】
字符串: ((())), 最大匹配数: 6
字符串: ()()(), 最大匹配数: 6
字符串: ([]]), 最大匹配数: 4
字符串: )[)(, 最大匹配数: 0
62、树形DP-树的最小点覆盖问题
【题目描述】
鲍勃喜欢玩战略游戏，但他有时候找不到够快的解决方案。现在他必须保卫一座中世纪城市，城市的道路形成一棵树。他必须把最小数量的士兵放在节点上，这样才可以观察到所有道路。请帮鲍勃找到放置的最小士兵数。
输入格式：
输入多个测试用例。对每个测试用例：
- 第一行包含节点数 n (0 < n ≤ 1500)
- 接下来的 n 行，每行的描述为”节点编号:(道路数) 节点编号1 节点编号2 …”或”节点编号:(0)”
- 节点编号为0~n-1，每个节点连接的道路数不超过10条，每条道路在输入数据中都只出现一次
输出格式：
对于每个测试用例，都单行输出放置的最小士兵数。
输入：
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
【输出结果】
1
2
63、状态压缩DP-旅行商问题TSP-最短Hamilton路径
【题目描述】
给定一张n个点的带权无向图，点从0~n-1标号，求从起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。
输入格式：
- 第一行包含整数n
- 接下来n行每行n个整数，其中第i行第j个整数表示点i到点j的距离（记为a[i][j]）
输出格式：
- 输出一个整数，表示最短Hamilton路径的长度
数据范围：
- 1 ≤ n ≤ 20
- 0 ≤ a[i][j] ≤ 10^7
输入：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
【输出结果】
18
64、数位DP-数字统计
【题目描述】
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。
比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入格式：
- 输入共1行，为两个正整数L和R，之间用一个空格隔开
输出格式：
- 输出共1行，表示数字2出现的次数
数据范围：
- 1 ≤ L ≤ R ≤ 10^6
输入1：2 22
输出1：6
输入2：2 100
输出2：20
65、DP剪枝与优化-启发式剪枝
【题目描述】
将整数n分成k份，且每份不能为空，任意两种划分方案不能相同（不考虑顺序）。例如：n=7,k=3，下面三种分法被认为是相同的：1,1,5; 1,5,1; 5,1,1。问有多少种不同的分法。
输入格式：n,k (6 < n ≤ 200, 2 ≤ k ≤ 6)
输出格式：一个整数，即不同的分法
【输出结果】
数的划分问题测试
输入：n=7, k=3
DP解法结果：4
DFS+剪枝解法结果：4
66、经典贪心-活动安排问题
【题目描述】
活动安排问题：有n个活动，每个活动有开始时间s和结束时间e。这些活动都需要使用同一个资源（如会议室），同一时间只能有一个活动使用该资源。要求选择尽可能多的互不冲突的活动，即活动之间时间不重叠（一个活动的开始时间必须大于等于前一个活动的结束时间）。
输入格式：
- 第一行：整数n（活动数量）
- 接下来n行：每行两个整数s和e，表示活动的开始时间和结束时间
输出格式：
- 一个整数，表示最多可以安排的活动数量
输入：
9
1 4
3 5
0 6
5 6
3 8
5 9
6 10
2 4
3 6
【输出结果】
最多可以安排 3 个活动
67、经典贪心-区间覆盖问题
【题目描述】
区间完全覆盖问题：给定一个目标区间[s, t]和n个小区间，每个小区间有左端点a和右端点b。要求选择最少数量的区间，使得这些区间的并集完全覆盖目标区间[s, t]。如果无法完全覆盖，则输出-1。
输入格式：
- 第一行：两个整数s和t，表示目标区间的左右端点
- 第二行：整数n，表示小区间的数量
- 接下来n行：每行两个整数a和b，表示一个小区间的左右端点
输出格式：
- 一个整数，表示最少需要的区间数量；如果无法覆盖，输出-1
输入：
1 10
5
1 3
2 5
4 7
6 9
8 10
【输出结果】
5
测试用例1：
test1 = interval_cover(1, 10, [(1, 4), (3, 6), (5, 8), (7, 10)])
结果1：
测试1: 目标区间[1,10]，最少需要 4 个区间
测试用例2：
test2 = interval_cover(1, 10, [(2, 3), (4, 5), (6, 7), (8, 9)])
结果2：
测试2: 目标区间[1,10]，结果: -1 (无法覆盖)
测试用例3：
test3 = interval_cover(0, 5, [(0, 2), (1, 3), (2, 4), (3, 5)])
结果3：
测试3: 目标区间[0,5]，最少需要 3 个区间
68、经典贪心-部分背包问题
【题目描述】
阿里巴巴有一个承重量为T的背包，藏宝洞里有N堆金币，第i堆金币的总重量为mᵢ，总价值为vᵢ。所有金币都可以随意分割，分割后单位价格不变。问最多能拿走多少价值的金币？结果保留两位小数。
输入格式：
- 第一行：N T（N≤100，T≤1000）
- 接下来N行：每行两个整数mᵢ vᵢ（1≤mᵢ,vᵢ≤100）
输入：
4 50
10 60
20 100
30 120
15 45
【输出结果】
最大价值: 240.00
计算过程：
- 计算单位价值：60/10=6.0，100/20=5.0，120/30=4.0，45/15=3.0
- 按单位价值降序排序：堆1(6.0)→堆2(5.0)→堆3(4.0)→堆4(3.0)
- 贪心选择：
- 装堆1：重量10，价值60，剩余容量40
- 装堆2：重量20，价值100，剩余容量20
- 装堆3：只能装20重量，价值=4.0×20=80
- 总价值：60+100+80=240.00
测试用例1：3,10,[(5, 10), (3, 6), (2, 4)]
结果1：测试1（全部能装下）: 20.00
测试用例2：3,25,[(30, 60), (20, 100), (10, 30)]
结果2：测试2（部分装入）: 115.00
69、进阶贪心-任务调度-Johnson算法
【题目描述】
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。某个产品i在A、B两车间加工的时间分别为Aᵢ、Bᵢ。怎样安排这n个产品的加工顺序，才能使总的加工时间最短？这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
输入格式：
- 第一行：n，表示产品的数量
- 第二行：n个整数，表示每个产品在A车间加工的时间
- 第三行：n个整数，表示每个产品在B车间加工的时间
输入：
5
3 5 8 7 10
6 2 1 4 9
【输出结果】
=== 加工生产调度问题（Johnson算法） ===
产品数量: 5
A车间加工时间: [3, 5, 8, 7, 10]
B车间加工时间: [6, 2, 1, 4, 9]
最优加工顺序: [1, 5, 4, 2, 3]
最短总加工时间: 34
=== Johnson算法详细步骤 ===
步骤1：计算每个产品的min(A时间, B时间)
产品1: min(3, 6) = 3
产品2: min(5, 2) = 2
产品3: min(8, 1) = 1
产品4: min(7, 4) = 4
产品5: min(10, 9) = 9
步骤2：按min_time升序排序
排序结果: ['产品3(min=1)', '产品2(min=2)', '产品1(min=3)', '产品4(min=4)', '产品5(min=9)']
步骤3：构建调度顺序
- 如果min_time来自A时间，放在前部
- 如果min_time来自B时间，放在后部
步骤4：计算加工时间线
产品1: A结束=3, B开始=3, B结束=9
产品5: A结束=13, B开始=13, B结束=22
产品4: A结束=20, B开始=22, B结束=26
产品2: A结束=25, B开始=26, B结束=28
产品3: A结束=33, B开始=33, B结束=34
70、进阶贪心-带权区间调度
【题目描述】
小明收到了n个任务的邀请，每个任务i有一个开始时间sᵢ、结束时间fᵢ和完成该任务能获得的价值vᵢ。由于小明时间有限，他不能同时参加两个时间重叠的任务。请帮助小明选择一组互不重叠的任务，使得这些任务的总价值最大。
输入格式：
- 第一行：n，表示任务数量（1 ≤ n ≤ 10⁵）
- 接下来n行：每行三个整数sᵢ fᵢ vᵢ，表示任务的开始时间、结束时间和价值
输入：
4
1 2 50
3 5 20
6 19 100
2 100 200
【输出结果】
250
解释：最优选择是任务1(1-2,价值50)和任务4(2-100,价值200)，总价值250。注意任务1和任务4在时间点2处结束和开始，不算重叠。
# 测试用例1：所有任务都不冲突
test1_tasks = [(1, 3, 10), (4, 6, 20), (7, 9, 30)]
# 测试用例2：所有任务都冲突
test2_tasks = [(1, 5, 10), (2, 6, 20), (3, 7, 30)]
# 测试用例3：混合情况
test3_tasks = [(1, 4, 5), (3, 5, 1), (0, 6, 8), (4, 7, 3), (3, 8, 6), (5, 9, 4), (6, 10, 2), (8, 11, 4)]
更多测试用例输出：
=== 带权区间调度问题 ===
任务数量: 4
任务列表（开始时间, 结束时间, 价值）:
任务1: 1-2, 价值50
任务2: 3-5, 价值20
任务3: 6-19, 价值100
任务4: 2-100, 价值200
按结束时间排序后的任务:
任务1: 1-2, 价值50
任务2: 3-5, 价值20
任务3: 6-19, 价值100
任务4: 2-100, 价值200
=== 构建p数组（最后一个不冲突的任务） ===
任务1: 没有不冲突的前置任务
任务2: 最后一个不冲突的任务是任务1
任务3: 最后一个不冲突的任务是任务2
任务4: 最后一个不冲突的任务是任务1
=== 动态规划计算过程 ===
dp[1] = 50 (选择任务1)
dp[2] = 70 (选择任务2)
dp[3] = 170 (选择任务3)
dp[4] = 250 (选择任务4)
最大总价值: 250
选择的任务编号（按结束时间排序后）: [1, 4]
选择的任务编号（原始顺序）: [1, 4]
验证总价值: 250
=== 更多测试用例 ===
测试1（全不冲突）: 60
测试2（全冲突）: 30
测试3（混合）: 12
第六章：数学与数论
71、基础数论-最大公约数GCD与最小公倍数LCM
【题目描述】
最大公约数和最小公倍数问题
输入两个正整数x0, y0（2 ≤ x0, y0 ≤ 10^5），找出所有满足以下条件的正整数对(a, b)：
- gcd(a, b) = x0
- lcm(a, b) = y0
求满足条件的(a, b)对数。注意：(a, b)和(b, a)视为同一对。
输入：
3 60
【输出结果】
4
解释：满足条件的数对有：(3,60), (12,15), (15,12), (60,3)
72、基础数论-质因数分解
【题目描述】
已知正整数n是两个不同的质数的乘积，试求出两者中较大的那个质数。
输入格式：一个正整数n（1 ≤ n ≤ 2×10^9）
输出格式：一个正整数p，即较大的那个质数
输入：
21
【输出结果】
7
解释：21 = 3 × 7，较大的质数是7
73、基础组合数学-双胞胎相邻排列
【题目描述】
五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有多少种不同排列方法？
【输出结果】
五个小朋友中双胞胎必须相邻的排列方法有：48种
计算过程：
1. 将双胞胎捆绑后，共有4个元素
2. 捆绑后元素排列数：24
3. 双胞胎内部排列数：2
4. 总排列数：24 × 2 = 48
解释：
使用捆绑法计算：
- 将双胞胎视为一个整体，与其他3个小朋友共4个元素进行排列：4! = 24种
- 双胞胎内部可以交换位置：2! = 2种
- 总排列数：24 × 2 = 48种
74、基础组合数学-班级小组组合问题
【题目描述】
一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？
【输出结果】
班级小组组合问题
班级有10个男生和12个女生，选3人小组，至少包含1个女生
直接法计算结果：1420种
间接法计算结果：1420种
✓ 两种方法结果一致：1420种
计算过程详解：
1. 选1女2男：C(12,1) × C(10,2) = 12 × 45 = 540
2. 选2女1男：C(12,2) × C(10,1) = 66 × 10 = 660
3. 选3女：C(12,3) = 220
总计：540 + 660 + 220 = 1420
解释：
总共有22名学生（10男12女），选3人小组。
方法1（直接法）：
- 选1女2男：C(12,1) × C(10,2) = 12 × 45 = 540
- 选2女1男：C(12,2) × C(10,1) = 66 × 10 = 660
- 选3女：C(12,3) = 220
总计：540 + 660 + 220 = 1420种
方法2（间接法）：
总组合数：C(22,3) = 1540
不含女生的组合（全男生）：C(10,3) = 120
至少1女生：1540 – 120 = 1420种
75、数值计算-高精度计算-阶乘之和
【题目描述】
用高精度计算出 S = 1! + 2! + 3! + ⋯ + n! (n ≤ 50)。
其中”!”表示阶乘，定义为 n! = n × (n-1) × (n-2) × ⋯ × 1。例如，5! = 5 × 4 × 3 × 2 × 1 = 120。
输入格式：一个正整数 n。
输出格式：一个正整数 S，表示计算结果。
【输出结果】
阶乘之和测试：
----------------------------------------
n= 1: 期望=1 实际=1 ✓
n= 3: 期望=9 实际=9 ✓
n= 5: 期望=153 实际=153 ✓
n=10: 期望=4037913 实际=4037913 ✓
n=20: 期望=2561327494111820313 实际=2561327494111820313 ✓
计算n=50的阶乘之和（前20位）：
总位数：65
前20位：31035053229546199656...
后20位：...94566672920420940313
==================================================
阶乘之和计算器
==================================================
请输入n（1-50，输入0退出）: 5
S = 1! + 2! + ... + 5! = 153
请输入n（1-50，输入0退出）: 0
程序结束！
76、数论进阶-欧拉函数-互质个数
【题目描述】
给定一个正整数 n，求 1 到 n 中与 n 互质的数的个数。即求欧拉函数 φ(n) 的值。
两个数互质是指这两个数的最大公约数为 1。
输入格式：一个整数 n (1 ≤ n ≤ 10^6)。
输出格式：一个整数，表示 φ(n) 的值。
【输出结果】
==================================================
欧拉函数计算器
==================================================
选择模式：
1. 计算单个数的欧拉函数
2. 计算范围内所有数的欧拉函数
3. 退出
请输入选择 (1-3): 1
请输入正整数 n: 10
φ(10) = 4
与 10 互质的数：
1, 3, 7, 9
共 4 个
选择模式：
1. 计算单个数的欧拉函数
2. 计算范围内所有数的欧拉函数
3. 退出
请输入选择 (1-3): 2
请输入范围上限 n (1-1000): 16
1 到 16 的欧拉函数值：
----------------------------------------
φ(1) = 1 φ(2) = 1 φ(3) = 2 φ(4) = 2 φ(5) = 4
φ(6) = 2 φ(7) = 6 φ(8) = 4 φ(9) = 6φ(10) = 4
φ(11) = 10 φ(12) = 4 φ(13) = 12φ(14) = 6 φ(15) = 8
φ(16) = 8
统计：
最大值：φ(13) = 12
平均值：5.00
选择模式：
1. 计算单个数的欧拉函数
2. 计算范围内所有数的欧拉函数
3. 退出
请输入选择 (1-3): 3
感谢使用，再见！
解释：与 6 互质且不超过 6 的正整数有 1 和 5，共 2 个。
解释：与 12 互质且不超过 12 的正整数有 1, 5, 7, 11，共 4 个。
77、数论进阶-同余方程-模线性方程求解
【题目描述】
求关于 x的同余方程 ax≡1(mod b)的最小正整数解。数据保证一定有解。
输入格式：一行，包含两个正整数 a,b，用一个空格隔开。
输出格式：一个正整数 x0，即最小正整数解。
数据范围：2≤a,b≤2,000,000,000
输入：
3 10
【输出结果】
7
因为 3×7=21，21 mod 10=1，满足方程。
78、数论进阶-扩展中国剩余定理-生理周期
【题目描述】
人有体力、情感、智力三个生理周期，周期长度分别为23、28、33天。给定某个日期（从给定起始日算起的天数）和三个周期在当前日期所处的位置（分别距离下一个峰值的天数 p, e, i），求下一次三个峰值同一天出现的时间（距离给定起始日的天数）。
输入格式：多组数据，每组一行四个整数：p, e, i, d（0 ≤ p, e, i ≤ 365, d ≤ 36500）。p=e=i=d=-1 时结束。
输出格式：输出下一次三峰值同天出现的时间（距离起始日的天数），格式为：”Case {序号}: the next triple peak occurs in {天数} days.”
输入：
0 0 0 0
0 0 0 100
5 20 34 325
-1 -1 -1 -1
【输出结果】
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 1027 days.
79、组合数学进阶-容斥原理-互质数计数
【题目描述】
10000以内，与10000互质的正整数有多少个？
题目解析：
与10000互质意味着不能被10000的质因子整除。首先分解质因数：10000 = 2⁴ × 5⁴ = 2×2×2×2×5×5×5×5。因此，10000的质因子只有2和5。
问题转化为：在1~10000中，有多少个正整数不能被2整除且不能被5整除。
【输出结果】
1~10000中与10000互质的正整数个数: 4000
计算过程验证:
10000以内能被2整除的数: 5000个
10000以内能被5整除的数: 2000个
10000以内能被10整除的数: 1000个
能被2或5整除的数: 6000个
与10000互质的数: 4000个
80、组合数学进阶-鸽巢原理-纸牌花色问题
【题目描述】
一副纸牌除掉大小王有52张牌，四种花色（红桃、黑桃、梅花、方块），每种花色13张。假设从这52张牌中随机抽取13张纸牌，则至少有多少张牌的花色一致？
【输出结果】
鸽巢原理理论结果：至少4张牌花色一致
模拟10000次抽牌，观察到的最小最大同花色数：4
模拟结果中最大同花色数的分布：
最大同花色4张：出现3540次
最大同花色5张：出现4436次
最大同花色6张：出现1633次
最大同花色7张：出现344次
最大同花色8张：出现43次
最大同花色9张：出现4次
说明：模拟10000次抽牌，每次详细结果不一定相同，有一定的概率。
81、高等数学-矩形法-数值积分
【题目描述】
给定二次函数 f(x)=x²+bx+c，其中 b,c为整数。用矩形法估算函数在区间 [l,r]上的积分：
方法：选取区间内所有偶数坐标点 x,x+2,x+4,⋯，计算每个点的函数值并求和，再乘以坐标点间距2。
计算公式：s=2×[f(x)+f(x+2)+f(x+4)+⋯]，其中 x是大于等于 l的最小偶数。
输入格式：
- 一行四个整数 b,c,l,r
输出格式：
- 一个整数 s，表示积分估算结果
数据范围：0≤l<l+2≤r≤1000，−20≤b,c≤20
输入1：
1 2 0 5
输出1：
64
输入2：
-20 -20 1 1000
输出2：
324294000
解释：
- 第一个测试：f(x)=x²+x+2，在[0,5]区间上偶数点求和再乘2
- 第二个测试：大区间计算，验证算法效率
82、高等数学-概率期望计算-赠券收集问题
题目背景：
概率期望是竞赛中高等数学的重要考点，常涉及动态规划或公式推导。本问题简化自”赠券收集问题”。
【题目描述】
有一个 k面的公平骰子，每面朝上的概率均为 1/k。每次掷骰子并记录结果，直到所有 k个面都至少出现一次为止。求掷骰子次数的数学期望 E(k)。
输入格式：一个整数 k(1≤k≤10^6)。
输出格式：输出理论期望值 E(k)，与模拟实验的平均值进行对比。理论值保留6位小数，模拟值保留4位小数。
输出结果
输入为 3时，理论期望 E(3)=3×(1+1/2+1/3)=5.5。模拟实验（基于大数定律）接近该值。
输入：
3
【输出结果】
理论期望: 5.500000
模拟期望 (50000次实验): 5.5028
说明：模拟期望每次生成的值不完全相同，但都在理论期望附近。
83、概率论-醉汉上飞机问题
【题目描述】
有n个人排队上飞机，我是第n个人。第一个人是醉汉，醉汉不坐自己的位置，占据他人位置的概率相等。对于剩下的人，如果他的座位没有被占，他会坐到自己的座位；否则，他会等概率地坐到空的位置。问：我的位置（位置n）被占据的概率是多少？
输出结果
醉汉上飞机问题概率分析
==================================================
n 解析概率 模拟概率
----------------------------------------
2 0.500000 1.000000
3 0.500000 0.748640
5 0.500000 0.626860
10 0.500000 0.556100
20 0.500000 0.523760
50 0.500000 0.513360
100 0.500000 0.505360
关键观察：
1. 当n=2时，概率为0.5（只有两个座位，醉汉要么坐你的座位，要么不坐）
2. 当n>2时，概率稳定在0.5
3. 这是一个反直觉的结果：无论飞机有多少座位，你的座位被占的概率总是1/2
解释：当n=100时，概率 ≈ 0.5
84、博弈论-异或运算-Nim游戏
【题目描述】
有n堆石子，每堆有aᵢ个石子。两人轮流操作，每次可以从任意一堆中取走任意数量的石子（可以取完，但不能不取），最后无法进行操作的人判负。双方都采取最优策略，问先手是否必胜。
【输出结果】
测试用例1：石子堆 = [3, 4, 5]
异或和 = 2 = 2
结果：先手必胜
必胜操作：从第1堆取2个石子
操作后石子堆：[1, 4, 5]
操作后异或和：0
==================================================
测试用例2：石子堆 = [2, 2]
异或和 = 0 = 0
结果：先手必败
无论先手怎么取，后手都能通过对称操作获胜
==================================================
交互式Nim游戏演示
==================================================
游戏开始！共有3堆石子：
第1堆：7个石子
第2堆：1个石子
第3堆：6个石子
所有石子数的异或和 = 0
先手处于必败态！
分析：无论先手怎么取，后手都能通过对称操作保持异或和为0
85、博弈论-模运算-巴什博奕变种
【题目描述】
有一堆n个石子，两人轮流取石子，每次可以取1~m个石子（至少取1个，最多取m个），最后取光石子的人获胜。双方都采取最优策略，问先手是否必胜。
【输出结果】
测试用例：n=10, m=3
计算：n % (m+1) = 10 % 4 = 2
结果：先手必胜
必胜策略：第一次取2个石子
策略演示：
先手取2个石子，剩余8个
后手取2个石子，剩余6个
先手取1个石子，剩余5个
后手取1个石子，剩余4个
先手取1个石子，剩余3个
后手取1个石子，剩余2个
先手取2个石子，剩余0个
后手获胜！
测试用例：n=8, m=3
计算：n % (m+1) = 8 % 4 = 0
结果：先手必败
分析：无论先手取多少，后手都能通过取(m+1-先手取的数)个石子来保持剩余石子数为(m+1)的倍数
测试用例：n=15, m=4
计算：n % (m+1) = 15 % 5 = 0
结果：先手必败
分析：无论先手取多少，后手都能通过取(m+1-先手取的数)个石子来保持剩余石子数为(m+1)的倍数
测试用例：n=12, m=4
计算：n % (m+1) = 12 % 5 = 2
结果：先手必胜
必胜策略：第一次取2个石子
策略演示：
先手取2个石子，剩余10个
后手取2个石子，剩余8个
先手取1个石子，剩余7个
后手取1个石子，剩余6个
先手取1个石子，剩余5个
后手取1个石子，剩余4个
先手取1个石子，剩余3个
后手取1个石子，剩余2个
先手取2个石子，剩余0个
后手获胜！
==================================================
巴什博奕变种：每次只能取2的幂次个石子
==================================================
石子数n | 先手胜负 | 分析
----------------------------------------
1 | 必胜 (n不是3的倍数) | SG值=1
2 | 必胜 (n不是3的倍数) | SG值=2
3 | 必败 (n是3的倍数) | SG值=0
4 | 必胜 (n不是3的倍数) | SG值=1
5 | 必胜 (n不是3的倍数) | SG值=2
6 | 必败 (n是3的倍数) | SG值=0
7 | 必胜 (n不是3的倍数) | SG值=1
8 | 必胜 (n不是3的倍数) | SG值=2
9 | 必败 (n是3的倍数) | SG值=0
10 | 必胜 (n不是3的倍数) | SG值=1
11 | 必胜 (n不是3的倍数) | SG值=2
12 | 必败 (n是3的倍数) | SG值=0
13 | 必胜 (n不是3的倍数) | SG值=1
14 | 必胜 (n不是3的倍数) | SG值=2
15 | 必败 (n是3的倍数) | SG值=0
==================================================
通用SG函数实现（Sprague-Grundy定理）
==================================================
标准巴什博奕（m=3）的SG值：
n=1: SG值=1, 先手必胜
n=2: SG值=2, 先手必胜
n=3: SG值=3, 先手必胜
n=4: SG值=0, 先手必败
n=5: SG值=1, 先手必胜
n=6: SG值=2, 先手必胜
n=7: SG值=3, 先手必胜
n=8: SG值=0, 先手必败
n=9: SG值=1, 先手必胜
n=10: SG值=2, 先手必胜
第七章：工程实践
86、工程化搜索-路径规划搜索-骑士巡游问题
【题目描述】
在n×n的国际象棋棋盘上，骑士从任意位置出发，要求访问每个格子恰好一次，找到一条完整的巡游路径。骑士的移动遵循”日”字形规则（横2竖1或横1竖2）。
输入格式：第一行整数n表示棋盘大小，第二行两个整数x,y表示起始位置。
输出格式：如果存在巡游路径，输出n×n的矩阵，表示每个格子的访问顺序；否则输出”无解”。
输入：
请输入棋盘大小n: [8]
请输入起始位置(x y): [0 0]
【输出结果】
找到骑士巡游路径：
1 16 31 40 3 18 21 56
30 39 2 17 42 55 4 19
15 32 41 46 53 20 57 22
38 29 48 43 58 45 54 5
33 14 37 52 47 60 23 62
28 49 34 59 44 63 6 9
13 36 51 26 11 8 61 24
50 27 12 35 64 25 10 7
87、工程化搜索-状态压缩技巧-炮兵阵地
【题目描述】
在一个N×M的网格地图上，有平原(‘P’)和山地(‘H’)。炮兵的攻击范围是上下左右各2格。现在要在平原上布置炮兵，使得任意两个炮兵不在对方的攻击范围内。求最多能布置多少个炮兵。
输入格式：
- 第一行：两个整数N, M（N ≤ 100, M ≤ 10）
- 接下来N行：每行M个字符，’P’表示平原，’H’表示山地
输出格式：一个整数，表示最多能布置的炮兵数量
输入：
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
【输出结果】
6
88、工程化搜索-综合图论应用-地图探险
【题目描述】
有一片丛林，其环境可以用一个 n 行 m 列的字符表来表示。第 i 行第 j 列的位置记作 (i,j)。如果这个位置的字符为 ‘.’，代表这个位置是一片空地，可以通过；如果字符为 ‘x’，代表这个位置上有障碍，不可通过。
机器人的状态由位置和朝向两部分组成。位置由坐标 (x,y) 刻画，朝向用一个 0∼3 的整数 d 表示，其中 d=0 代表向东，d=1 代表向南，d=2 代表向西，d=3 代表向北。
初始时，机器人的位置为 (x₀,y₀)，朝向为 d₀。保证初始时机器人所在的位置为空地。接下来机器人将要进行 k 次操作。
每一步操作规则如下：
- 假设机器人当前处在的位置为 (x,y)，朝向为 d。则它的方向上的下一步的位置 (x’,y’) 定义如下：
- 若 d=0，则令 (x’,y’)=(x,y+1)
- 若 d=1，则令 (x’,y’)=(x+1,y)
- 若 d=2，则令 (x’,y’)=(x,y-1)
- 若 d=3，则令 (x’,y’)=(x-1,y)
- 机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断 (x’,y’) 是否满足 1≤x’≤n，1≤y’≤m，且 (x’,y’) 位置上是空地 ‘.’。
- 如果条件成立，则机器人会向前走一步。它新的位置变为 (x’,y’)，且朝向不变。
- 如果条件不成立，则它会执行”向右转”操作。也就是说，令 d’=(d+1) mod 4，且它所处的位置保持不变，但朝向由 d 变为 d’。
需要计算在机器人执行完 k 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。
输入：
2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....
【输出结果】
3
13
89、工程化搜索-综合图论应用-加工零件
【题目描述】
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 n 位工人，工人们从 1∼n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 x 号工人想生产一个被加工到第 L(L>1) 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L−1 阶段的零件（但 x 号工人自己无需生产第 L−1 阶段的零件）。
如果 x 号工人想生产一个被加工到第 1 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要为 x 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 q 张工单，第 i 张工单表示编号为 a_i 的工人想生产一个第 L_i 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。
输入格式：
第一行三个正整数 n,m,q，分别表示工人的数目、传送带的数目和工单的数目。
接下来 m 行，每行两个正整数 u 和 v，表示编号为 u 和 v 的工人之间存在一条零件传输带。保证 u≠v。
接下来 q 行，每行两个正整数 a 和 L，表示一张工单。
输出格式：
输出 q 行。每行一个字符串 Yes或 No，表示对于这张工单，轩轩是否需要提供原材料。
数据范围：
1≤n,m,q≤10^5，1≤L≤10^9
输入：
3 2 2
1 2
2 3
1 1
3 2
【输出结果】
No
Yes
90、工程化动态规划-公交换乘队列优化
【题目描述】
小轩轩最近乘坐地铁和公交出行时，发现乘坐地铁可以领取优惠券，用于抵扣后续公交车的费用。现在给出小轩轩的出行记录，请你计算他的总花费。
出行记录规则：
- 出行记录按时间顺序给出，每条记录包含三个整数：type（0表示地铁，1表示公交）、price（票价）、time（时间戳）。
- 乘坐地铁时，必须支付票价，同时获得一张与票价等值的优惠券，有效期为45分钟（即从获得时刻起45分钟内可用）。
- 乘坐公交车时，如果存在有效的优惠券，可以选择使用一张面值不低于票价的优惠券抵扣本次费用；否则需要支付票价。
- 优惠券使用规则：优先使用最先获得的优惠券，且每张优惠券只能使用一次。
输入格式：
第一行一个整数 n，表示出行记录数量。
接下来 n 行，每行三个整数 type, price, time，表示一条出行记录。
输出格式：
一个整数，表示小轩轩的总花费。
数据范围：
1 ≤ n ≤ 10^5，1 ≤ price ≤ 1000，0 ≤ time ≤ 10^9
输入：
6
0 10 3
1 5 46
0 20 50
1 10 95
1 5 96
0 5 110
【输出结果】
40
91、工程化动态规划-飞扬的小鸟
【题目描述】
游戏界面是一个长为n，高为m的二维平面，其中有k个管道（忽略管道的宽度）。小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标位置i时，可以上升的高度为up[i]，下降的高度为down[i]。
小鸟高度等于0或者等于m时，无法再继续上升或下降。现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
输入格式：第一行有3个整数n，m，k，分别表示游戏界面的长度，高度和水管的数量。接下来的n行，每行2个整数up[i]和down[i]。接下来的k行，每行3个整数P，L，H，表示每根水管的横坐标、下边沿高度、上边沿高度。
输出格式：第一行，如果可以完成游戏，输出1，否则输出0。第二行，如果可以完成游戏，输出最少点击屏幕数，否则输出最多可以通过的管道数量。
输入：
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
【输出结果】
1
6
92、工程化系统设计-资源分配-廊桥分配
【题目描述】
L市新建了一座机场，一共有n个廊桥。机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
廊桥的使用遵循”先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将n个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
输入格式：
- 第一行包含三个正整数n, m₁, m₂，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量
- 接下来m₁行，每行两个正整数a₁ᵢ, b₁ᵢ，表示一架国内航班飞机的抵达、离开时刻
- 接下来m₂行，每行两个正整数a₂ᵢ, b₂ᵢ，表示一架国际航班飞机的抵达、离开时刻
输出格式：一个正整数，表示能够停靠廊桥的飞机数量的最大值。
输入：
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
【输出结果】
7
说明：对于样例输入，最优分配是国内区2个廊桥，国际区1个廊桥，总共可以停靠7架飞机。
93、工程化系统设计-资源分配-机器分配问题
【题目描述】
总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。
输入格式：
- 第一行包含两个整数M和N，分别表示设备台数和分公司数
- 接下来是一个N×M的矩阵，其中第i行第j列的数表示第i个公司分配j台机器的盈利
输出格式：
- 第一行输出最大盈利值
- 接下来N行，每行输出一个整数，表示对应分公司分配的机器数
输入：
3 3
30 40 50
20 30 50
20 25 30
【输出结果】
70
1
1
1
说明：对于样例输入，最优分配方案是：第一个公司分配1台机器（盈利30），第二个公司分配1台机器（盈利20），第三个公司分配1台机器（盈利20），总盈利为70。
94、工程化缓存设计-机器翻译-FIFO缓存
题目背景：
小晨的电脑上安装了一个机器翻译软件，翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。
【题目描述】
对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入格式：
- 第一行：两个正整数M,N，代表内存容量和文章的长度
- 第二行：N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词
输出格式：一个整数，为软件需要查词典的次数
输入：
3 7
1 2 1 5 4 4 1
【输出结果】
5
95、工程化缓存设计- LRU-哈希与双向链表
【题目描述】
请你设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构。
实现LRUCache类：
- LRUCache(int capacity)：以正整数作为容量capacity初始化LRU缓存
- int get(int key)：如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
- void put(int key, int value)：如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字
函数get和put必须以O(1)的平均时间复杂度运行。
输入示例：
lRUCache = LRUCache(2)
lRUCache.put(1, 1) # 缓存是 {1=1}
lRUCache.put(2, 2) # 缓存是 {1=1, 2=2}
lRUCache.get(1) # 返回 1
lRUCache.put(3, 3) # 该操作会使得关键字2作废，缓存是 {1=1, 3=3}
lRUCache.get(2) # 返回 -1 (未找到)
lRUCache.put(4, 4) # 该操作会使得关键字1作废，缓存是 {4=4, 3=3}
lRUCache.get(1) # 返回 -1 (未找到)
lRUCache.get(3) # 返回 3
lRUCache.get(4) # 返回 4
输出示例：
1
-1
-1
3
4
96、工程化贪心算法-哈夫曼树贪心-合并果子
【题目描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入格式：
- 第一行：一个整数n(1≤n≤10000)，表示果子的种类数
- 第二行：包含n个整数，用空格分隔，第i个整数ai(1≤ai≤20000)是第i种果子的数目
输出格式：一个整数，也就是最小的体力耗费值
输入：
3
1 2 9
【输出结果】
15
97、工程化贪心算法-双指针贪心-纪念品分组
【题目描述】
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式：
- 第一行：一个整数w，为每组纪念品价格之和的上限
- 第二行：一个整数n，表示购来的纪念品的总件数
- 第3~n+2行：每行包含一个正整数Pi表示所对应纪念品的价格
输出格式：一个整数，即最少的分组数目
输入：
100
9
90
20
20
30
50
60
70
80
90
【输出结果】
6
98、工程化应用-时间滑动窗口-海港
【题目描述】
小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti（单位：秒），船上的乘客数量ki，以及每名乘客的国籍xi,1,xi,2,…,xi,ki。
小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时（24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲，你需要计算n条信息。对于输出的第i条信息，你需要统计满足 ti – 86400 < tp ≤ ti 的船只p，在所有的x(p,j)中，总共有多少个不同的数。
输入格式：
- 第一行输入一个正整数n，表示小K统计了n艘船的信息
- 接下来n行，每行描述一艘船的信息：前两个整数ti和ki分别表示这艘船到达海港的时间和船上的乘客数量，接下来ki个整数x(i,j)表示船上乘客的国籍
- 保证输入的ti是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第ti秒到达海港
- 保证1≤n≤10^5，Σki≤3×10^5，1≤x(i,j)≤10^5
输出格式：输出n行，第i行输出一个整数表示第i艘船到达后的统计信息
输入1：
3
1 4 4 1 2 2
2 2 2 3
10 1 3
输出1：
3
4
4
输入2：
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
输出2：
3
3
3
4
99、工程化应用-动态规划解决方案-纪念品问题
【题目描述】
小伟知道未来T天N种纪念品每天的价格。每天可以进行无限次交易：以当日价格购买纪念品，或卖出持有的纪念品换回金币。每天卖出换回的金币可以立即用于购买，当日购买的纪念品也可以当日卖出。第T天必须卖出所有纪念品。小伟现在有M枚金币，求超能力消失后最多能拥有的金币数量。
输入格式：第一行三个正整数T、N、M，接下来T行每行N个正整数表示价格。
输出格式：一个正整数表示最多能拥有的金币数量。
输入1：
6 1 100
50
20
25
20
25
50
输出1：
305
输入2：
3 3 100
10 20 15
15 17 13
15 25 16
输出2：
217
100、工程化应用-组合数学解决方案-清仓甩卖问题
【题目描述】
小X的糖果店有n颗糖果，第i颗糖果原价为a_i元。小X计划将每颗糖果清仓价格定为1元或2元。顾客有m元钱，会按以下策略购买：优先选择现价低的糖果，现价相同时优先选择原价高的糖果。求有多少种定价方案不会导致”超卖”（即顾客按策略购买后不会后悔）。
输入格式：第一行两个整数n、m，第二行n个整数表示原价。
输出格式：一个整数表示合法定价方案数，对998244353取模。
输入：
3 5
5 3 2
【输出结果】
8
解释：8种合法定价方案