国科大.算法设计与分析.2022期末考试真题回忆版
目录
- 分而治之
- 贪心
- 动态规划
- 线性规划：搬家问题
- 网络流
- Bonus 1
- Bonus 2
分而治之
找众数
贪心
找数组中的子数组，和为target，问最多能找到多少个？
动态规划
字符串A和字符串B，每次可以删除一个字符，问最少的删除次数，能够使得这两个字符串相等。
线性规划：搬家问题
卡车每次容量为Q，共m个箱子和n个物品都要搬走，每个箱子和每个物品都有容量，物品要放到箱子里，一个箱子可以放多件物品。
最小化卡车搬运趟数。
网络流
比所有的作业题都简单
Bonus 1
N个学生，每人一个成绩。range为同一组内最大成绩减最小成绩。
- 将N个学生分为k组，最小化最大的range。
- 每个组的range不能超过d，人数不能少于l，问是否存在这样的方式？
Bonus 2
字符、字符串、文章L。文章是无限的。已经有一个判别器A，可以在线性时间内判断某一字符串是否属于文章。
- 定义操作，L={s1s2s3…}，其中si属于L。
- 设计一个判别器B，可以利用A，在多项式时间内判断s是否属于L*。