9-21 今天上午做了三题： Run 最小生成树+倍增，可能是倍增写错了，爆零，需要继续调试。后来发现倍增确实写错了，但是没有再次调试这道题。 Nim 涉及到博弈论，不会做。正解是奇数行的亦或值是否为1 Toy 应该是树形dp，我写了暴力。正解是选或不选这个点，如果不选这个点，子节点就必须有选的 下午： Sequence 正解是O(n)算法，我只想到了O(n^2)的模拟算法，需要进一步研究。 Word 涉及到高深的技术和kmp字符串匹配，没有想到怎么做 Car 一开始模仿八皇后写了搜索算法，时间复杂度略高，后来改成了状压dp，因为有一个状态被遗漏了，WA，后来该上了，应该能AC。 9-22 今天到noi.ac上打比赛，只拿到了60分暴力分。 第一题，count 组合数学题，for I = 1..n+1 do ans[i] = C(n+1, i) – C(L+R, I – 1)。调试的时候，由于组合数复杂度太高而T，后来由于模后数相减没有调整为正数，卡了好久。还要背过逆元递推式，并进行阶乘的预处理，O(n) 第二题，delete，首先是DP，60分，研究DP的转移状态，得到二维偏序问题，sort后做LIS即可，O(nlogn) 第三题，涉及到树剖，没有研究。
另外研究了昨天的LCA问题，洛谷上LCA如果用倍增法，不用读入优化会T，而ST表求RMQ则不会T，昨天T1需要求额外的信息，就不能用ST表来做了
9-23 今天考了几道题，isbn、connect和drive Isbn水过了。 Connect 爆了0，后来研究发现，是printf输出符号打错了，lf达成了ld。修改后只有45分，调整模拟退火算法的参数后75.查看题解，发现正解是枚举+最大生成树。 照题解修改程序后发现是95分，后来查出，是循环内使用es数组数据，而sort改变了es数组的顺序，进而有一组数据没有通过。谨以记之。 第三题是图上dp，实际上也可以不建图，常数略大而已。写的时候有一点小问题，gdb调了半天，发现时复制样例输入的时候复制错了，程序本身没有问题。 9-24 今天上午做了: Toy: dp+斜率优化。考试的时候看错了题意，写了贪心，没有得分。下午和晚上学习了斜率优化，打算配合相关的题目练习一下。 Fence：据说是要用单调队列计算对答案的贡献。没有研究。 Sequence: 据说要用单调队列优化，或者是某种奇怪的贪心。 Apple dp+优化（离散化+排序）
9-25 上午做了dp优化系列2，以为是有两道题以为是贪心，结果是错误的。 第一题garden非常诡异，当时搜索没有写出来，就放弃了。题意是，只能是长条和矩形，这样才能保证距离是曼哈顿距离 第二题写了搜索，可能剪枝剪得太厉害了，只过了样例。正解是m=2时的答案最大，按照l, r排序后，用单调栈维护状态、更新答案。 第三道题是某种贪心、也使用单调栈维护。 第四题是某种dp，和编辑距离有关，我写了搜索，搜到了小部分的分。后来在推dp方程，没有推出来。 另外提交答案的时候，输出搞错了，要注意一下。 晚上研究了树链剖分，被某种有坑的文章坑了好久。
9-26 今天没有考试，研究了一些零散的dp题，在洛谷上做了一些，感觉不是很熟练，需要进一步练习
9-27 今天考试内容是图论，二分图匹配。 城堡守卫，当时写了搜索，A1W1T8，应该是搜索剪枝厉害了，正解是每行设置一个编号，遇到墙则断开，然后每列这么处理，同时又可以站立的格子，则把当前格子所属的行列编号连边，进行二分图匹配或网络流。 序列变换，距离公式是还上距离，当时写了搜索。正解是裸的二分图匹配，从大到小开始匹配，匹配时从小到大，如果不能完全匹配则No Answer，完全匹配则输出匹配内容。 机器调度，考场上写了spfa+map的最短路问题，同时将问题简化，认为调度时只能依次处理，骗到了70分。正解是modA和modB连边，直接二分图匹配。 导弹，第一题是求同时满足三维的最长上升子序列，直接连边求最长路即可，spfa会被卡一个点，记忆化dfs可以过，第二题是求小路径覆盖问题，根据公式 最小路径覆盖=点数-最大匹配，套用匈牙利算法解决。预处理需要o(n^2)，由于没有时间限制，所以每次必须遍历所有的点。似乎可以排序后遍历一部分，常数会小很多，但没必要。