1115总结
T1
简单题写蠢做法。
我用了 \(set\)
来维护同一行同一列的信息然后还要查询什么的，实际上 vector
就可以了，记录一下该点的行下标和列下标。
T2
简单题写挂。
首先转对照局面。
想到可以先二分个左时间出来，然后仿超级钢琴。
实际上可以二分个左时间和右时间暴力排序，码量更小了。
写挂是排序的各种问题。
排序，尤其是对编号排序，一定要搞清楚排的到底是什么的序。
T3
做不来的趣味题。
考场上想到可以 \(O(n^3)\) 的动态规划，方法是设 \(dp[i][j][k]\) 表示考虑到 \(i\)，漏了 \(j\) 个 \(B\)，当前有 \(k\) 个 \(A\)，转移可以做到 \(O(1)\)。
左看右看都觉得有一维是多余的，但是就是去不掉。
考虑最终答案的分界线，然后动态规划，就可以去掉一维，但是动态规划变成反向了。
容易发现转移的重复性很高，相当于是一个行向量乘上若干矩阵再乘一个列向量，可以反过来写。
考场上没想到反过来写，是因为反过来之后动态规划就没有明晰的组合意义了，所以陷入了正向的窠臼，不容易思考。
参考某道题(T2)。