洛谷四月月赛Div.2 题解

Solution

A

若二元组 ( i , j ) (i,j) (i,j) 合法,当且仅当 S i < S j S_i < S_j Si​<Sj​ 。

我们从后往前枚举 i i i ,并通过一个桶来找到最靠后的满足 S i < S j S_i<S_j Si​<Sj​ 的 j j j;若存在一个这样的 j j j,则直接输出即可。

时间复杂度 O ( n ) O(n) O(n) 。

B

我们找到黑色棋子的气,然后对于气的每一个连通块判断它的气是否为 0 0 0 即可。若气为 0 0 0 的气不超过 1 1 1 个,则答案为 NO \text{NO} NO,否则为 YES \text{YES} YES。

C

不会 ⋯ ⋯ \cdots\cdots ⋯⋯

D

考虑分治。

令当前分治区间为 [ l , r ] [l,r] [l,r],中间点为 m i d mid mid,我们需要求出所有跨越中间点的区间的最大独立集之和。

令 f i , 0 f_{i,0} fi,0​ 表示,若 a m i d a_{mid} amid​ 在独立集中,区间 [ i , m i d ] [i,mid] [i,mid] 的最大独立集。 f i , 1 f_{i,1} fi,1​ 则为 a m i d a_{mid} amid​ 无限制的情况下的最大独立集。

令 g i , 0 g_{i,0} gi,0​ 表示,若 a m i d + 1 a_{mid+1} amid+1​ 在独立集中,区间 [ m i d + 1 , i ] [mid+1,i] [mid+1,i] 的最大独立集。 g i , 1 g_{i,1} gi,1​ 同理。

若 l ≤ a ≤ m i d < b ≤ R l \le a \le mid < b \le R l≤a≤mid<b≤R,则 f ( a , b ) = max ⁡ ( f a , 0 + g b , 1 , f a , 1 + g b , 0 ) f(a,b)=\max(f_{a,0}+g_{b,1},f_{a,1}+g_{b,0}) f(a,b)=max(fa,0​+gb,1​,fa,1​+gb,0​) 。现在,关键在于求出

∑ a = l m i d ∑ a = m i d + 1 r max ⁡ ( f a , 0 + g b , 1 , f a , 1 + g b , 0 ) \sum_{a=l}^{mid} \sum_{a=mid+1}^r \max(f_{a,0}+g_{b,1},f_{a,1}+g_{b,0}) a=l∑mid​a=mid+1∑r​max(fa,0​+gb,1​,fa,1​+gb,0​)

我们枚举 a a a,并计算其贡献。直接计算较为困难,于是考虑将 max ⁡ \max max 去掉。

若 f a , 0 + g b , 1 > f a , 1 + g b , 0 f_{a,0}+g_{b,1} > f_{a,1}+g_{b,0} fa,0​+gb,1​>fa,1​+gb,0​,则显然是 f a , 0 + g b , 1 f_{a,0}+g_{b,1} fa,0​+gb,1​ 产生贡献。考虑怎样的 b b b 才能满足上述式子,不难得到

f a , 0 − f a , 1 > g b , 0 − g b , 1 f_{a,0}-f_{a,1} > g_{b,0}-g_{b,1} fa,0​−fa,1​>gb,0​−gb,1​

也就是说,我们要求出所有满足 g b , 0 − g b , 1 < f a , 0 , f a , 1 g_{b,0}-g_{b,1} < f_{a,0},f_{a,1} gb,0​−gb,1​<fa,0​,fa,1​ 的 g b , 1 g_{b,1} gb,1​ 的数量与 g b , 1 g_{b,1} gb,1​ 的和。我们可以将它“离线”下来,通过排序与双指针来求出这两个值。

f a , 1 + g b , 0 f_{a,1}+g_{b,0} fa,1​+gb,0​ 产生贡献的情况同理。

令时间复杂度为 T ( n ) T(n) T(n),则 T ( n ) = 2 T ( n 2 ) + n log ⁡ n = O ( n log ⁡ 2 n ) T(n)=2T(\frac n 2)+n \log n=O(n \log^2 n) T(n)=2T(2n​)+nlogn=O(nlog2n)。

E

Lemma

F ( i , j ) = 2 F ( i + 1 , j − 1 ) + F ( i , j − 1 ) − F ( i + 1 , j ) F(i,j)=2F(i+1,j-1)+F(i,j-1)-F(i+1,j) F(i,j)=2F(i+1,j−1)+F(i,j−1)−F(i+1,j)

观察上面的式子,不难发现:我们只需要求出第 1 1 1 列的所有 F F F 与第 m m m 列的所有 F F F ,然后直接递推就好了。

时间复杂度 O ( m 2 ) O(m^2) O(m2)。

上一篇:基于Pierre Dellacherie算法的俄罗斯方块机器人


下一篇:ENCODYAv1.1 英科迪亚 免费下载