2024.4 做题记录

4.7

CF1648D

设 $dp_i$ 为从 $(1,1)$ 到 $(2,i)$ 的最小代价。答案为 $\max dp_i+s3_n-s3_{i-1}$ 。

dp_i=max(\max_{l_x\le i} dp_{l_x-1}+s2_i-s2_{l_x-1}-w_x,\max_{l_x\le j\le i} s1_j+s2_i-s2_{j-1}-w_x)

前面线段树维护 dp 值，按转移顺序区间 max，单点查。后面从后往前枚举 $i$ ，不断加入区间，维护 $\max_{x\le y} a(x)+b(y)$ 。另一个线段树分别维护 $maxa,maxb,maxv$ 。

CF1949F

不合法情况要么完全包含要么不交，建立树形结构。按 $k_i$ 大小从小到大排序。实时记录每个爱好 $j$ 对应的最后的人 $f_j$ 。枚举 $i$ 的每个爱好 $j$ ，如果最后不合法意味着每个 $f_j$ 的爱好都被 $i$ 完全包含，否则找到一组解。如果最后不合法，所有 $f_j$ 的爱好数之和为 $k_i$ 。

4.16

CF1951F

对于 $i<j$ ，如果 $p_i$ >p_j$ ，无论顺序逆序对贡献为 $1$ ；否则一个逆序对贡献为 $2$ ，顺序对贡献为 $0$ 。构造一些位置上的逆序对数为 $\frac{k−inv(p)}{2}$ 。

abc348g

有决策单调性，主席树上二分。

4.18

CF1542E2

枚举前 $i-1$ 位相同， $p_i=x$ 且 $q_i=y$ 。逆序对数的差异只与后 $n-i-1$ 的排列有关。 $dp_{i,j}$ 表示 $i$ 个数有 $j$ 个逆序对。

ans=\sum_{i=0}^{n-1} A_n^i \sum_{x=1}^{n-i-1}\sum_{y=x+1}^{n-i-1} \sum_{j=0}^{n^2}\sum_{k=0}^{j+x-y-1} dp_{n-i-1,j}\times dp_{n-i-1,k}

记 $f_j=\sum dp_k$ 。

ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n^2}dp_{n-i-1,j}\sum_{x=1}^{n-i-1}\sum_{y=x+1}^{n-i-1} f_{j+x-y-1}

记 $g_j=\sum f_k$ 。

ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n^2}dp_{n-i-1,j}\times(g_{j-2}\times(n-i-1)-\sum_{x=1}^{n-i-1}g_{j+x-n+i-2})

记 $h_j=\sum g_k$ 。

ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n^2}dp_{n-i-1,j}\times(g_{j-2}\times(n-i-1)-h_{j-2}+h_{j-n+i-2})

abc349g

最直接的就是并查集倍增将两段区间并起来。

可以用类似马拉车的思路得到一个贪心算法。枚举 $i$ ，用 $ban_{i,j}$ 记录 $i$ 不能是 $j$ ，维护 $r$ 表示当前已知 $b_1\dotsb b_r$ 。如果 $i+a_i\ge r$ 就把 $r$ 更新到 $i+a_i$ ，否则什么也不做。最后在 hash 判断所有 $a_i$ 是不是都满足条件。