[总结]2023-7-13A组模拟赛
P1 心路历程
发现今天的题目描述很直接，比昨天的好懂。
然后发现T2似乎是数据结构，好像找到了归宿，心里踏实了一点。之后就发现自己不会的计数题但是有两道：T1和T3。T4还以为是板子题，然后发现读不懂。
于是就开始干T2（终于不是从T1开始做了！！！），一开始以为要用高级算法或者数据结构：树套树、CDQ等等。然后发现对于一个二维区间判断是否有树可以直接用过二维前缀和。而且答案是可以二分的，不过要用 \(O(nm)\) 的时间判断。这样的时间复杂度是 \(O(T\log(\min(n,m)nm))\) 的。
发现数据的 \(T\) 很大，这样可能会TLE0pts。着手考虑优化。不过我实在是太蒟蒻了，这个想法怎么样都优化不了一点。
后面想到可以把矩阵中的每一个点都作为左上角，进行扩展正方形，这样是 \(O(n^2\log n)\) 的预处理，处理询问是 \(O(Tnm)\) 的，太不优美了。之后就停了很久。
大概9:30的时候觉得不能再这样什么也不打了，于是乎画了画图。发现可以剪枝。最开始我考虑的是一个正方形太大而边界容不下的情况：
之后就推出了对答案贡献的公式：
\[\min(x_2-i,y_2-j,f(i,j)) \]其中 \(f(i,j)\) 代表以 \((i,j)\) 为左上角的最大边长。
经过一段时间的思考，我发现可以答案可以减少枚举量，类似于下图：
图中的阴影部分可以不用枚举，因为无论如何他们的贡献都不可能大于原答案了。
于是就很开心，因为好像能拿很多分。之后边打边注意卡常，全部开register，只写了main()一个函数（怕调用常数太大）。
打完、调完，已经10:40。再看T1，很容易想到设状态 \(f(i,j)\) 表示以 \(i\) 为根、\(i\) 的权值填 \(j\) 的方案数，写出了如下转移方程：
\[f(i,j)=(\sum_{i=k+1} ^m \prod_{v\in \text{son}_i} \sum_{l=1}^{i-k} f(v,l))+(\sum_{i=1} ^{m-k} \prod_{v\in \text{son}_i}\sum _{l=i+k}^m f(v,j)) \]然后因为式子实在太抽象了，而且觉得退错了什么。于是又思考了一遍，发现可以用前缀和。以为式子推错了，还以为转移需要把所有东西乘一遍，要再打一个dfs，于是弃疗。
后面的时间也过得很抽象，只有一个小时，要打三道题，都不知道怎么分配，T2打太久了。后面好像是想了一下T3，连暴力都懒得打，之后检查了一下T2，发现一个致命错误，赶紧改过来（我一个比赛就打一道题，还打错，那就不用玩了！！！），再交一发。
后面什么也没干。
P2 赛后总结
用IOI看了一下，T260分，好像很低。
后面和fy讨论，T2似乎可以用整体二分，但不过ljr好像有更好的方法。
中午睡过头了，下午回机房，发现rnk还能20。我只打了一道题的暴力啊？？？
和ljr讨论了一下，正解还是用二分，不过可以用二维ST表做到 \(O(1)\) check，很神奇。
其他题都没怎么看，全在搞T2。顺便把二维ST表在不看题解的前提下自己推了出来。
然后就是讲题，T1是结论优化DP，T2我讲了自己的暴力，T3是点分治，T4是奇怪的图论，几乎都没听懂。
整个下午全在干T2，和绿老师一起呆到了6:20，其实我早就调完了，然后在等的过程中交了一下，等了很久还在running，于是放弃了，去看绿老师搞T4，后面刷新了一下，发现AC100，2982ms，一发入魂。
这次比赛还是有很多地方要改进的。比如说又把很多时间押到一道题上面。而且这次比赛的心态波动很大，几乎就是想出来一个办法，然后又否定自己，落差感极大，最后心态爆炸，其余三道题的暴力都不想写了。但事实上，没有想象的那么糟糕，如果今天多打几份暴力，可能就会进rnk10，因为比赛题目确实很难。
所以在以后的比赛里面，要做到心态及时调整，要时刻保持冷静。
P3 题目总结
T2
感觉非常难以评价的一道题。
首先我们可以延续赛时我的想法，设 \(f(i,j)\) 表示以 \((i,j)\) 为右下角的最大边长。之后我们考虑二分答案，二分完答案之后，就可以查询 \((x_1+mid-1,y1+mid-1)\to (x_2,y_2)\) 这个矩形的 \(f(i,j)\) 最大值。如果大于等于 \(mid\) 显然可行；否则，则不可行。再思考一下，发现这个查询是询问二维区间最大值，由于是静态的，而且空间、时间限制很紧，可以用二维ST表。
之后来说一下为什么只用查询 \((x_1+mid-1,y1+mid-1)\to (x_2,y_2)\) 这个矩形的 \(f(i,j)\) 最大值。首先回到之前那个公式：
\[\min(i-x_1,j-y_1,f(i,j)) \]画图可知，画阴影部分的一定要小于等于 \(mid\) ，因为边界问题已经限制它的大小。
之后就做完了，要注意一下细节，反正我打错了挺多的，这里说几个：
- 二维ST表要先有一维ST表的预处理，就是算出来每行每列的那些值。
- 要注意二维ST表转移时那些 \(+1/-1\) 的问题。
- 注意二分，我一开始打的是：如果\(mid\) 合法，还把 \(l=mid-1\)，相当于减小答案。