看了看今天的题,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)\) 的。
标签:总结,max,复杂度,最小,然后,T1,维护,2022.11 From: https://www.cnblogs.com/apjifengc/p/16865492.html