Skip to content

Latest commit

 

History

History
62 lines (60 loc) · 3.17 KB

README.md

File metadata and controls

62 lines (60 loc) · 3.17 KB
Raw

UCAS算法设计作业

卜东波老师的算法课程作业，包括简答题和上机实验题。

简答题包括自然语言描述、伪代码以及时间复杂度分析。 上机题用C++实现，部分采用了c++11标准，代码通过OJ测试。

目前学业较忙，暂且只更新上机题:D
课程OJ链接:http://theory.ict.ac.cn/grad_oj

Update

  • 2018.1.21 网络流OJ题已更新。
  • 2018.1.13 更新Take-Home Message内容，网络流OJ题待更新～（一周考三科，尼玛要死了
  • 2018.12.21 更新贪心OJ，更新LP算法OJ。LP算法OJ第二题未AC，且不是用单纯形解决，仅供参考。
  • before 2018.12.21 更新分治递归、动态规划OJ题，全部AC。（懒得去写什么时候上传的了=_=

Take-Home Message

  1. 先观察问题的结构、解的形式，再设计算法;
  2. 能分解成子问题，是非常有效的信息;
  3. 优化问题时，下界很重要;
  4. 给一个问题，从最简单的case入手;
  5. 观察INPUT的关键结构，看能否分解、能否combine;
  6. 观察OUTPUT，不要坚持追求optimal，适当放松标准追求sub-optimal;
  7. 采样！采样！采样！;
  8. 手动执行最基本的算法，发现冗余；
  9. merge时，考虑引入结构；
  10. 离散化;
  11. 省内存：分问题的另一种思路;
  12. 省时间：Banded DP;
  13. 还是optimal和sub-optimal;
  14. (老师忘了要说啥了;
  15. 子问题的描述方式:
    a.背包-子集：指数多-{1,2,3,...}前i个：多项式;
    b.最短路径-子图：指数多-引入新变量表示解：k步;
  16. 递归中有at most如何表示？加一个递归项;
  17. DP需要空间太多→用神经网络表示函数;
  18. 每一个Greedy的背后都有一个more cumbersome DP;
  19. weight加强后，有可能不用枚举;
  20. 先做一个笨方法，再发现冗余;
  21. loose the structure but don't loost it too much;
  22. 分析时：一个操作慢，但随后操作快，均摊;
  23. 求和：每一项转乘phi的差，相约;
  24. 要允许剪枝，但不要剪太多→不要偏离完美的树太远;
  25. 抽象，就能推广;
  26. 写LP时，先写自然语言，再转成不等式约束;
  27. 不要只用不等式约束，再加上目标函数约束;
  28. Lagrange乘子就是对偶变量;
  29. 千方百计构造一个对手出来
  30. 构造对手:
    a.y 直接构造 x;
    b.找一个隐含变量B，同时构造x和y;
  31. 目标: original
    Releaxed! releaxed
  32. 还是optimal和Sub-Optimal;
  33. Scaling;
  34. 分析一个event的发生次数：找一个量\Phi，考察连续两次event中间发生了什么;
  35. 既然已经花了很多时间，索性把opt的所有油水全榨干。

Code Tips

  1. 当问题规模比较大时，采用cin接收输入会比较耗时。
    解决方法：a. 换成 scanf ; b. 用 std::ios::sync_with_stdio(false) 提升cin效率;
  2. 学会选择合适的数据结构，如优先队列、双端队列等
  3. 线性规划可用GLPK、matlab等工具解决；原问题不好解决找其对偶
  4. 程序写的6不如板子找的好（胡说八道