看了看今天的题，T1 给我整自闭了然后就打算光看看题不做了）

然后发现除了 T4 都是洛谷主题库的题，难度 黑-黄-蓝-红

什么组题鬼才

然后发现 T2 不会做，我现在的实力已经是不会做黄题了是吧）

（在模拟赛结束前就写题解是吧apj

2022NOIP A层联测22

T4 非常困难的压轴题

钓鱼题。

T3 送给好友的礼物

好像是个经典树形背包，设 \(f_{u,i}\) 为 \(u\) 子树内 \(A\) 走 \(i\) 步时 \(B\) 至少要走多少步，直接做就行了。

我一开始想的其实是 \(f_{u,i,j}\) 为 \(u\) 子树内 \(A\) 走 \(i\) 步 \(B\) 走 \(j\) 步能不能行，复杂度貌似是 \(O(n^3)\) 的，不知道能不能过。

T2 等差数列

呃呃 不会做黄题了

枚举公差 \(k\)，这一步复杂度是 \(O({w \over n})\) 的，然后再枚举每一位，计算出当这一位不需要更改时第一个数应当时多少（\(a_1=a_i-k\times (i - 1)\)），用一个桶维护哪个 \(a_1\) 次数最多就行了，复杂度就是 \(O(w)\) 的。

T1 极源流体

T1 出黑题我没想到。

首先发现肯定只会向下和向右流，因为如果向上流形状其实是和向下流一模一样的。

然后考虑两个黑点什么时候会联通，设一共向下流 \(a\) 次，向右流 \(b\) 次，那么假如两个黑点 \((x_1,y_1),(x_2,y_2),x_1<x_2,y_1<y_2\) 联通，说明 \(x_1+a<x_2,y_1+b<y_2\)，也就是 \(a\le x_2-x_1-1,b\le y_2-y_1-1\)。

那么我们可以看作是一个图，每两个点之间的边的权值为一个二元组 \((a,b)=(x_2-x_1-1,y_2-y_1-1)\)，我们要求的就是这个图的一个最小生成树，这里最小定义为 \(\max a + \max b\) 最小。

设一共有这样的边 \(M\) 条，考虑按照 \(a\) 从小到大往里加，维护 \(\max b\) 的最小值。那么用 LCT 维护一下最小生成树，每次把路径上 \(b\) 最大的边删掉，就能维护出来答案了，复杂度 \(M \log nm\)。

但是边数是很大的，不过有很多边是没有用的，因为如果有三个点 \(A(x_1,y_1), B(x_2,y_2), C(x_3, y_3)\) 满足 \(x_1<x_2<x_3,y_1<y_2<y_3\)，那么 \(A-C\) 的边一定是不会被选到的。而这样我们只需要对每一个 \(x_i\) 做一个单调栈，就能把有用的边找出来了，这样 \(M\) 就降到了 \(O(nm)\) 的数量级，总复杂度就是 \(O(nm \log nm)\) 的。