基础算法练习题汇总

这份题目汇总，是我和几个朋友一起整理所得，放在我的博客只是为了存档纪念曾经一起奋斗的日子，以及分享给有需要的人。感谢老战友。

帖子很长，建议在目录查找需要的主题，然后直接Ctrl+F。

目录

  • 1.基本算法
    • 1.1.递归与分治
      • 1.1.1.基础练习
      • 1.1.2.进阶练习
    • 1.2.模拟
      • 1.2.1.基础练习
      • 1.2.2.进阶练习
    • 1.3.贪心
      • 1.3.1.基础练习
      • 1.3.2.进阶练习
  • 2.解空间搜索
    • 2.1.初出茅庐
      • 2.1.1.深度优先搜索
      • 2.1.2.广度优先搜索
      • 2.1.3.穷竭(暴力)搜索
    • 2.2.出类拔萃
      • 2.2.1.隐式图最短路,简单剪枝
      • 2.2.2.尺取
      • 2.2.3.反转(开关问题,关灯问题)
      • 2.2.4.二分搜索
        • 2.2.4.1.最大化最小值(或最小化最大值)
        • 2.2.4.2.最大化平均值
        • 2.2.4.3.查找第K大的值
        • 2.2.4.4.最小化第K大的值
        • 2.2.4.5.其他
    • 2.3.登峰造极
      • 2.3.1.双端队列
      • 2.3.2.调整搜索顺序和智慧剪枝
      • 2.3.3.智慧搜索2( A IDA)
  • 3.图论
    • 3.1.图论基础
    • 3.2.图论中等
    • 3.3.图论高级
  • 4.动态规划
    • 4.1.动态规划基础
    • 4.2.DP中等
    • 4.3.DP高级

1. 基本算法

1.1. 递归与分治

递归：找出递归子结构性质（原问题的解包含了子问题的解）、用子问题的解来递归定义原问题的解、找出递归终止条件。

分治：问题分解，逐个击破。在处理公共子问题时，可以引入一个表格，对于计算过的解缓存起来，重复利用。

1.1.1. 基础练习

  1. 放苹果：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16690
  2. Science：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=31627
  3. Oil Skimming：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=31171
  4. 棋盘问题：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15202

1.1.2. 进阶练习

  1. Two Famous Companies：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=29898
  2. Crazy Tank：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33707
  3. Palindromin Substring：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33418

1.2. 模拟

根据题目实际意思一步步写代码就好，没算法可言，耐心+基本功

1.2.1. 基础练习

  1. Biorhythms：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16391
  2. Maya Calendar：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11385
  3. 最大连续积：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=38909
  4. 体重：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37583
  5. 最佳裁判：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37617
  6. Running Rabbits：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33714
  7. Counterfeit Dollar：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16424
  8. Numbers that Count：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11260
  9. Packets：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16476
  10. Packing Rectangles：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16996

1.2.2. 进阶练习

  1. 矩阵覆盖：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37614
  2. Sum of divisors：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33549
  3. Joseph：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11573
  4. Calendar Game：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17540
  5. Chemical Reactions：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=31592

1.3. 贪心

顾名思义，贪心就是找到某一策略，每次寻找该策略下的最优，逐步找到最后的最优解。

而贪心的难点在于，你怎么确认是否存在有效的贪心策略！

下面是一些经典的例子

  1. 活动选择问题 Activity selection

  2. 最小生成树 Minimum spanning tree

  3. 部分背包问题 Partial knapsack problem

1.3.1. 基础练习

  1. Scientific Conference：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26713
  2. Exam：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=175278
  3. Electrification Plan：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=47106
  4. Dragon of Loowater：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19048
  5. Two Teams：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14092
  6. Wooden Sticks：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16477
  7. Radar Installation：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10537
  8. Power of Cryptography：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10040
  9. Y2K Accounting Bug：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18025
  10. Gone Fishing：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16478
  11. Pass-Muraille：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11166
  12. Game Prediction：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16382
  13. Box of Bricks：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16479
  14. Integer Intervals：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16482
  15. Huffman’s Greed：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16483

1.3.2. 进阶练习

  1. Minimal Coverage：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13756
  2. Crossing River：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26251

2. 解空间搜索

所谓 解空间 ，顾名思义，就是 所有可能解的集合 或者说 所有候选答案的集合。

解空间搜索 是通用解法之首。如果问题无法用特别明显的算法解决，往往可以考虑搜索。

2.1. 初出茅庐

搜索入门,基础的穷搜,广搜,深搜

2.1.1. 深度优先搜索

  1. Lake Counting：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14167
  2. Red and Black：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26084
  3. Property Distribution：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46522
  4. Ball：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22516
  5. Curling 2.0：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15201
  6. Catch That Cow：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15204

2.1.2. 广度优先搜索

  1. Cheese：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=49879
  2. Meteor Shower：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12685
  3. Seven Puzzle：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=49880

2.1.3. 穷竭(暴力)搜索

  1. Smallest Difference：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17170
  2. Backward Digit Sums：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=39458
  3. Hopscotch：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12306
  4. Osenbei：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=50785

2.2. 出类拔萃

隐式图最短路,简单剪枝,尺取,反转(开关问题,关灯问题),二分搜索

2.2.1. 隐式图最短路,简单剪枝

  1. Shuffle’m Up：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15207
  2. Pots：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15208
  3. Network Saboteur：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15209
  4. Sudoku：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15211
  5. Tudoku：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16441
  6. Channel Allocation：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15212

2.2.2. 尺取

头指针和尾指针不断交替推进 寻找满足条件的最小区间

  1. Jessica’s Reading Problem：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24699
  2. Bound Found：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=39361
  3. Sum of Consecutive Prime Numbers：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18023
  4. Graveyard Design：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=39270

2.2.3. 反转(开关问题,关灯问题)

同一灯开关操作两次会互相抵消,可利用二进制压缩状态

  1. EXTENDED LIGHTS OUT：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17722
  2. Flip Game：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16122
  3. Fliptile：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17522
  4. Game：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22970
  5. The Water Bowls：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17471

2.2.4. 二分搜索

利用有序数列的特性,每次检查解空间的中点是否满足条件,无论是否满足 最优解只会落在大于中点或小于中点的解空间内,

从而每次可以把解空间缩小一半,最终在O(logN)次的比较之内求得最优解

2.2.4.1. 最大化最小值(或最小化最大值)
  1. Aggressive cows：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21309
  2. River Hopscotch：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16277
  3. Monthly Expense：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14546
  4. Drying：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16416
  5. Cow Acrobats：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11013
2.2.4.2. 最大化平均值
  1. Dropping tests：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17097
  2. K Best：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=39448
2.2.4.3. 查找第K大的值
  1. Median：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24230
  2. Matrix：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24239
2.2.4.4. 最小化第K大的值
  1. Moo University - Financial Aid：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11455
  2. Telephone Lines：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12427
2.2.4.5. 其他
  1. Garland：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17196
  2. Showstopper：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15091

2.3. 登峰造极

双端队列搜索,智能搜索(剪枝 A* IDA*)

2.3.1. 双端队列

双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。是一种具有队列和栈的性质的数据结构。

  1. Sliding Window：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16694
  2. The Fewest Coins：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20465
  3. Batch Scheduling：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10364
  4. FIMO sequence：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22461

2.3.2. 调整搜索顺序和智慧剪枝

调整搜索顺序,对比盲目搜索,需要对所有分支做一定的评估,选择最大可能性的解空间优先进行搜索

以数独为例,优先填只有1个可能性的空格,如果没有,优先填可能性少的空格

智慧剪枝,设计特殊的评估函数 或 利用已经得到部分解 限制搜索深度和广度

例如 要求最小深度,目前得到满足条件的深度是5,当搜索深度到了6即可立即终止,搜索其他分支

  1. Sudoku：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10883
  2. Sudoku：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10698
  3. Sticks：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14913
  4. Gap：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27367
  5. Power Calculus：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11302
  6. Square Destroyer：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17543

2.3.3. 智慧搜索2( A IDA)

剪枝虽然可以一定程度优化,让我们较快接近最优解,但没有找到较好解前,依然需要探索很多不必要的解空间

深度优先搜索通过估算下界,提前剪枝优化的算法叫IDA*

广度优先搜索利用估算下界优化,就是A*

  1. N皇后问题：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33634
  2. Solution to the n Queens Puzzle：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23664
  3. Eight：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16377
  4. The Morning after Halloween：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18735
  5. Square Carpets：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36736
  6. 15-Puzzle Problem：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21237

3. 图论

3.1. 图论基础

最短路径、最小生成树、强连通分量、拓扑排序入门题

  1. Christmas Tree：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10444
  2. Unique MST：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17124
  3. Slim Span：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15723
  4. School Network：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17001
  5. Labeling Balls：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19855

3.2. 图论中等

有一定难度的图论题，最大流、网路流、NP问题入门题

  1. Bottom of Graph：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11217
  2. Going Home：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11578
  3. Popular Cows：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16578
  4. Network：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11132
  5. Taxi Cab Scheme：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11751
  6. Instantaneous Transference：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14370
  7. Drainage Ditches：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10499
  8. King’s Quest：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17071
  9. Optimal Milking：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10503
  10. Sightseeing：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15297
  11. Sightseeing Cows：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17742
  12. Graph Coloring：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17391
  13. Secret Milking Machine：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10504

3.3. 图论高级

综合性较强难度较大的题目

  1. Cow Relays：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17690
  2. Picnic Planning：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11062
  3. Friendship：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12876
  4. Cable TV Network：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11083
  5. March of the Penguins：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10507
  6. Dual Core CPU：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16358
  7. Kaka’s Matrix Travels：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17098
  8. Distance Queries：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11131
  9. PIGS：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10509
  10. Knights：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12602
  11. Priest John’s Busiest Day：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18641
  12. Firing：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17404

4. 动态规划

4.1. 动态规划基础

DAG最短路问题、01背包、最长递增子序列、多源最短路、树形DP

  1. Strategic game：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18778
  2. Stockbroker Grapevine：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14577
  3. AGTC：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17326
  4. Charm Bracelet：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17547
  5. Longest Ordered Subsequence：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15302
  6. Kind Spirits：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22065
  7. Metro：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14094

4.2. DP中等

有一定难度的动态规划问题，最长递增子序列、排列组合问题、完全背包、矩阵连乘、状态压缩DP、区间DP

  1. Folding：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11442
  2. False Mirrors：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17671
  3. Multiplication Puzzle：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21493
  4. Piggy-Bank：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17110
  5. Flags：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21494
  6. Bridging signals：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17328

4.3. DP高级

综合性较强难度较大的动态规划题目

  1. Sightseeing Trip：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14074
  2. Two Rounds：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14101
  3. K-based Numbers：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16555