UCAS算法设计与分析

简单知识点大纲总结。

新增：期末考试题总结。

期末考试题

这考试，复习和不复习的结果是一样的，绝了，说好是作业题的变形，和作业几乎没关系。。保佑及格。。

• 第一题分治卡了快40分钟，LeetCode第四题
• 第二题动态规划，给个数组，算相邻两个数的差，要使得相邻的两个差值异号，并且要求是连续的，如果是0也不算。简单的dp，难得有道正常的题。
• 第三题贪心，codeforce 1426E，剪刀石头布，两个人，固定各自的出手次数为，对应剪刀石头布三个
  • 第一问，求第一个人的最大能赢的次数，只要贪赢就行。
  • 第二问，求第一个人的最少能赢的次数，这个比较难想明白。。。一直从正面想，也卡了好久。
  • 排除输的和平局，反面思路，
  • 正面思路
• 第四问LP，设置停车场位置，固定n栋楼位置为，在每个楼距离范围内设置一个停车场，每个楼都要设置一个，然后要使得最大的任意两个停车场之间的距离最小化。包含去绝对值，还有去max。max不知道怎么去，写了个min max。。。
  • 优化 | 线性规划和整数规划的若干建模技巧
  • 
  • 
• 第五题是树状DP，题目都理解反了，把neighbor理解成了兄弟节点，没想到是节点编号的neighbor。。。也是两小问，第二问好像是贪心。
• 第六题是括号匹配，只有第三小问比较难，但是没啥时间写了。。听说是卡特兰数。

Lec1-Introduction-and-some-representative-problems

1. TSP问题
   1. 没有环，分治
      
      
   2. 改进策略，2-opt，只允许两条边不同
      
      
   3. 聪明的枚举策略，就是先按照每步的顺序，构造多步决策树，然后剪枝
      
      
      
   4. 回溯策略，考虑第一步之后，枚举所有可能的情况，不用先把每一步排好序，上面的智能枚举是枚举每一步走不走，是二叉树，这里不是。这里解的形式是的形式
      
      
      

Lec5-Divide-And-Conquer

1. merge sort
   1. 分治的划分，如果是数组就是看是按照值分还是按照下标分，要选择好的划分点，不能线性规模下降，要指数规模下降
   2. 
   3. 
   4. 
2. 逆序数
   1. 划分成两部分，分别计算逆序数
   2. 
   3. 合并的时候有两种策略
      1. 
      2. 
   4. 
3. 快排
   1. 
   2. 时间复杂度
      
   3. 快排的优化
      1. pivot位置，在足够好
         
      2. 
      3. 
      4. 就地算法
      5. 
      6. 
4. 第k大数
   1. 
   2. 和快排差不多，只要看返回的pivot是哪个位置，如果整好是k，就返回这个位置，否则只要再递归找其中一边的就好了
   3. 优化
   4. 对于pivot位置进行限制，选接近中心点的位置作为pivot，如何获取这个pivot，有三种方法
      1. 
      2. 分组，然后取中点的中点来近似全局的median
      3. 
      4. inplace的方法：BFPRT算法
      5. 随机选择pivot
      6. 
      7. 随机采样的方法选pivot：Lazy Select算法
      8. 
      9. 
5. 乘法和矩阵乘法
6. 找最邻近点对
   1. 划分成两个大小相等的子集
   2. 合并过程是在每个子集找最近点对
      1. 左边的，右边的，还有横跨中间的
      2. 
      3. 如何加快combine？
      4. 条带法去冗余
      5. 
      6. 每个点不需要探索所有的地方
      7. 
      8. 
7. FFT, DFT一系列，不考

Lec6-Dynamic-Programming

1. 导弹分配问题
   1. 
   2. 
2. 矩阵链乘
   1. 
   2. 
   3. DP方法
   4. 
   5. 直接递归DP，指数级别
   6. 
   7. 去冗余，记忆化OPT表，多项式级别
   8. 
   9. 
   10. 自底向上unroll recursion tree
   11. 
   12. 
3. 背包问题
   1. 0-1背包
      1. 
      2. 
      3. 
      4. 
      5. 
      6. 
      7. 空间可以用滚动数组优化到
   2. 完全背包
      1. 
4. 顶点覆盖问题
   1. 
   2. 
   3. 
5. 字符串序列对齐问题
   1. 方法和最长公共子序列差不多，回溯的方法也是，只不过LCS的权重为1
   2. 当前字符i和j，匹配、错配、不匹配且删除i、不匹配且删除j
   3. 
   4. 
   5. 
   6. 
   7. 回溯
   8. 
6. 高级动态规划Advanced DP
   1. 
   2. 缩减空间
      
   3. 后缀对齐
      
   4. 对于只用两列数组的DP问题，回溯方法
      1. 
      2. 
   5. 进一步的优化略过
   6. 
7. banded dp
8. LCS问题
   1. 
   2. 
   3. Sparse DP
   4. 
9. 单源最短路径
   1. 如果是有向无环图，相当于拓扑排序
      1. 
      2. 
   2. 如果有环存在，那上面的就无法处理，要把子问题划分的更小
      1. 
      2. 限制步数，Bellman-Ford算法
      3. 
      4. 
   3. 对于负圈的问题
      1. 
      2. 
      3. 

线性规划LP

1. Diet问题
2. 最大流
3. 最小化费流
4. 多物品流
5. SAT
6. 基因重排序距离问题
7. ILP整数线性规划
8. 单纯形算法，这个比较难
9. 对偶问题

LP和拉格朗日对偶

其他的不管了，不考，直接记一下公式和对偶怎么用拉格朗日推出来

1. 对偶公式
   1. 
   2. 
   3. 
2. 拉格朗日对偶
   1. 
   2. 
   3. 

证明方法

1. 循环不变量
   1. 分为循环不变量和递归不变量
   2. 分治里有用到，可以用来证明包含循环或者递归的算法
   3. 
   4. 
   5. 
   6. 分为三步骤
      1. 初始化
      2. 维持
      3. 终止
2. 数学归纳法
3. 交换论证法
4. 反证法

时间复杂度

对于递归问题

1. 
2. 
3. 
4. 
5. 

Take Home Message

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12.