【刷题】保研机试题型分类

更新，如果你是OI大佬，ACM大佬，那这份题型分类对你来说可能太简单了，仅供参考。在我看来，这个分类似乎更适合像我一样的算法题0基础的同学从0开始学习的难度。

---

这里是我在1月到7月刷的一些有分类的题型的总结。博主的保研之路已经圆满结束，成功拿到了本校的offer。虽然因为疫情原因，博主参加的夏令营基本都取消了机考，但面试的时候还是受益于做过的这些题，因此分享出来，大家也可以参考一下。其中笔记.pdf是这些题我写的一些题解和易错点，不过太过随意，大家最好在网上搜题解。刷题笔记.pdf里还有一些题目。经典算法笔记.pdf记录了一些经典的算法，其代码在模板代码里可以找到。STL笔记.pdf记录了一些STL的常用数据结构。

枚举法

• 假硬币：http://noi.openjudge.cn/ch0201/15/
• 五户共井问题：http://noi.openjudge.cn/ch0201/7623/
• 画家问题：http://noi.openjudge.cn/ch0201/1815/
• 因子问题：http://noi.openjudge.cn/ch0201/2723/
• 我家的门牌号：http://noi.openjudge.cn/ch0201/7649/

递归和递推

• PKU2506Tiling（递推）：http://noi.openjudge.cn/ch0202/9273/
• 放苹果（递推）：http://noi.openjudge.cn/ch0202/666/
• 二叉树问题：http://t.cn/Ai0Ke6I0
• 2的幂次方表示（上交复试题）：http://noi.openjudge.cn/ch0202/8758/

分治

• 求排列的逆序数（O(nlogn)）：http://noi.openjudge.cn/ch0204/7622/
• 2011：http://noi.openjudge.cn/ch0204/2991/
• 找第k大的数（快排思想）

搜索

广度优先BFS

• Catch That Cow：http://acm.hdu.edu.cn/showproblem.php?pid=2717
• Find The Multiple：http://poj.org/problem?id=1426
• 玛雅人的密码（清华复试）：http://t.cn/Ai0lUhJj

深度优先DFS

• 神奇的口袋（北大复试，这题dp也能做，其实就是subset sum）：http://t.cn/Ai0u0GUz
• 碎纸机：http://noi.openjudge.cn/ch0205/1805/

不告诉你广搜还是深搜ww

• 鸣人和佐助（带限制的最短路）：http://noi.openjudge.cn/ch0205/6044/
• 无线网络：http://118.190.20.162/view.page?gpid=T7
• 算24：http://noi.openjudge.cn/ch0205/1789/
• 寻找Nemo：http://noi.openjudge.cn/ch0205/1998/
• 取石子游戏（感觉这题不太像搜索，其实就是博弈论的一种）：http://noi.openjudge.cn/ch0205/6266/

字符串

• Oulipo（KMP板子题，KMP一定要掌握）：http://acm.hdu.edu.cn/showproblem.php?pid=1686

线性数据结构

• Powerful Calculator（栈）：https://www.nowcoder.com/practice/6bc1dd2ee0ce4257821531719b8d1c83
• Blah数集（队列）：http://noi.openjudge.cn/ch0304/2729/

数学问题

进制转换

略，但是要会任意m进制转n进制的方法

质数相关

• 整除问题（上交复试）：https://www.nowcoder.com/practice/8e29045de1c84d349b43fdb123ab586a

快速幂、高精度

略，快速幂模板要记一下，高精度最好也记一下以防万一。

非线性数据结构

• 特殊的前序建树：http://t.cn/AiKuUtlX
• 已知前中遍历序列建树：http://t.cn/AiKgDfLU
• 哈弗曼树权重计算：http://t.cn/AiCuGMki

贪心

• To fill or not to fill：https://www.nowcoder.com/practice/f7eba38f7cd24c45982831e0f38518f9
• 最短前缀：http://noi.openjudge.cn/ch0406/1799
• 电池的寿命：http://noi.openjudge.cn/ch0406/2469/
• Magic of David Copperfield：http://noi.openjudge.cn/ch0406/712/
• 拼点游戏（难）：http://noi.openjudge.cn/ch0406/2986/
• 特殊密码锁（感觉不太像贪心？）：http://noi.openjudge.cn/ch0406/8469/
• Cell Phone Network（连通图最小支配集板子题）：http://noi.openjudge.cn/ch0406/2384/
• Ride to Office：http://noi.openjudge.cn/ch0406/2404/

图算法

• 宗教信仰（连通分支计算）：http://noi.openjudge.cn/ch0403/1526/
• 丛林中的路（并查集）：http://noi.openjudge.cn/ch0403/253/
• Gopher II（二部图匹配）：http://noi.openjudge.cn/ch0403/1538/
• ROADS（带限制的最短路）：http://noi.openjudge.cn/ch0403/726/
• Is It A Tree（有向树的判定）：http://noi.openjudge.cn/ch0308/310/
• Professor John（Floyd算法传递闭包）：http://noi.openjudge.cn/ch0308/3529/
• 最短路径问题（二重最短路）：http://t.cn/AilPbME2
• Legal or Not（拓扑排序）：http://acm.hdu.edu.cn/showproblem.php?pid=3342
• Instruction Arrangement（关键路径，即AOE问题）:http://acm.hdu.edu.cn/showproblem.php?pid=4109
• 畅通工程：http://t.cn/AiOvBHj9
• 找出直系亲属：http://t.cn/AiOzQMBH
• 最短路径（上交复试）：https://www.nowcoder.com/practice/a29d0b5eb46b4b90bfa22aa98cf5ff17
• 确定比赛名次：http://acm.hdu.edu.cn/showproblem.php?pid=1285

动态规划

最大连续子段和、最大公共子序列（LCS）、最大递增子序列（LIS）和背包问题等一定要先烂熟于胸（背包问题可以看《背包九讲》）。特别是各种背包问题，保研机试考的dp大部分都是背包问题的变种。

• 合唱队形：http://t.cn/AiYNyHPe
• 最小邮票数：http://t.cn/AiYlwchD
• 买书：http://noi.openjudge.cn/ch0206/6049/
• 宠物小精灵之收服：http://noi.openjudge.cn/ch0206/4978/
• 鸣人的影分身：http://noi.openjudge.cn/ch0206/8467/
• 切割回文：http://noi.openjudge.cn/ch0206/8471/
• 奶牛散步：http://noi.openjudge.cn/ch0206/9271/
• 鸡蛋的硬度：http://noi.openjudge.cn/ch0206/7627/
• 摘花生：http://noi.openjudge.cn/ch0206/2728/
• 方格取数（多线程dp）：http://noi.openjudge.cn/ch0206/8786/
• 酒鬼：http://noi.openjudge.cn/ch0206/9268/
• 计算字符串距离（edit distance裸题）：http://noi.openjudge.cn/ch0206/2988/
• 海贼王之伟大航路（状压dp，感觉机试应该不会考这种）：http://noi.openjudge.cn/ch0405/4979/
• 完美覆盖：http://noi.openjudge.cn/ch0405/1665/
• 雷涛的小猫：http://noi.openjudge.cn/ch0405/2454/
• 偶数个数字3：http://noi.openjudge.cn/ch0206/9272/