2018-10-29~2018-10-30
T1 逃离
原题考的数据范围比较小，标程给了\(O(nm \log (n+m))\)的做法。实际上可以做到严格\(O(nm)\)，另外还有\(O(n^2m^2)\)（暴力预处理）、\(O(nm\log nm)\)（Dijkstra）、\(O(nm\alpha (nm))\)(并查集维护连通性)的做法。
预处理的思路是多源bfs，是本题得分的关键。然后可以枚举答案，可以通过原题。发现答案有单调性，于是可以二分，也可以上优先队列，就有了那两个带有log的做法。实际上严格\(O(n^2m^2)\)的做法是通过Dijkstra的做法优化而来的，具体实现是用多个桶，维护多个解，然后按照limit减小的方向更新，权值为历史路径和当前点的最近距离取min，可以证明不会出现比limit更大的权值。每个节点都会遍历一次，所以是严格\(O(n^2m^2)\)的。
另外有一种常熟较小的Dijkstra的做法，即将到路径上最近值的最大值作为第一关键字，距离终点的距离作为第二关键字，用的是A*的思想，不过没有实现。
这道题的标程有问题，被我hack掉了，原因是读入时没有和下表对齐。
T2 求最大01子矩阵，行可以交换。
做法有很多，比如枚举每一行的排列，随机化+卡时等，这些期望是20分的。 更好的做法有：预处理出right数组，排序后用单调栈找最大矩形，或者二分长度，找最大出现次数，这些分别是\(O(mn\log n)\)、\(O(mn\log m)\)的，能过70分的点。 标程是在预处理出right数组，排序后用单调栈找最大矩形的基础上，用计数排序，压缩掉了log的复杂度，是严格\(O(mn)\)的
这道题的问题是，为了保险，写部分分的解时，5000*5000的数组开了7个，导致MLE。
T3 两个限制的最小生成树
题意：每条边有两个权值x,y，给定a,b，求将所有点联通时的最小化的代价。代价为\[max{x}\times a + max{y}\times b\] 一种做法是暴力枚举所有加边方式，复杂度\(O(m!)\)。 60分做法是枚举x，找最小的y，利用并查集维护连通性，复杂度为\(O(m^2)\) 标程是\(O(mn)\)的做法，每次加边时，在环上将最坏的边去掉，link-cut-tree或者暴力都可以，标程应该是暴力。
这道题的m开小了，导致RE一片
T4 permutation
这是一道水题，用桶计数，每次分配桶内元素的个数+1作为第x个排列，最后桶内元素需要非严格递减，才是由排列构成的，否则就不是。 这道题看错了题意，以为排列只能向后弄，只拿了10分样例分。
T5 zuma
部分分有搜索+剪枝，正解的dp很难想，也有情况无法处理，只拿了20分。 ## T6 正解是并查集或树套树，大概是。//TODO