2021.4.11 - 4.17 一周小结

CF1513F. Swapping Problem

题意：

$A$ $B$ $B$ $\sum |A_i-B_i|$ 。

题解：

$|A-B|+|C-D|>|A-C|+|C-B|$ $A<C$ $\max(A,D)<\min(B,C)$ 。

$A<C$ $A<B$ $D<B$ $D<C$ 来处理。

$A<C$ $A$ 排序从大到小扫一遍。

$A<B$ $D<C$ $A_i<B_i$ 则在线段树里查询；否则执行插入操作。

$D<B$ ：这个可以是线段树里维护的东西。

$\min(B,C)-\max(A,D)$ ，分类讨论一下：

$A>D$ $A>D$ $B$ $C$ $\min$ 。

$A<D$ $C<B$ $C-A$ 的最小值。

$O(n\log^2n)$ 。

评测链接：AC submission.

CF1503E. 2-coloring

题意：

$n\times m$ $n,m\le 2$ 021。

题解：

经过一系列的思考，我们发现一个方案合法，几乎当且仅当：

一种颜色被另一种颜色分成了两部分，并且这种被分开的颜色，会存在一条垂直于这种颜色对应方向的分界线，使得这个上方的峰值恰好到达分界线，下方的峰值刚好到达分界线；并且上下的这种颜色的部分都是单峰的；两边的峰值段不相交。

$C_{n+m}^n$ $h,u,v,l,r$ $h$ $u,v$ $l,r$ 是上方的)。

\begin{pmatrix}h+u-1\\h-1\end{pmatrix}\cdot\begin{pmatrix}n-v+h-1\\h-1\end{pmatrix} \cdot \begin{pmatrix}m-h+l-1\\m-h-1\end{pmatrix}\cdot\begin{pmatrix}n-r+m-h-1\\m-h-1\end{pmatrix}

$h,v,l$ ，并使用前缀和优化一下；对行和列各算一遍，这时就可以得到粗略答案。

$O(nm)$ 。

评测链接：AC submission.

CF1436F. Sum Over Subsets

题意：

$S$ $2\times 10^5$ ）
$Sum= \sum_{A\subseteq S}\sum_{B\subseteq S} \left[\gcd(A_1,A_2,A_3,...A_n)=1\right]\cdot\left[B\subseteq A\right]\cdot \left[|B|=|A|-1\right]\cdot \left(\sum_{x\in A}x\right)\left(\sum_{x\in B}x\right)$

题解：

首先做一个转化：

Sum=\sum_{A\subseteq S}[\gcd(A_1,A_2,...A_n)=1]\cdot \left(\sum_{x\in A}x\right)^2\cdot(|A|-1)

莫比乌斯反演一波：

Sum=\sum_{d}\mu(d)\sum_{A\subseteq S,d|A_i}\left(\sum_{x\in A}x\right)^2\cdot(|A|-1)

$n\ln n$ 计算，只需考虑右边这部分如何计算；我们分类讨论一下：

$2^{|A|-2}\cdot(|A|-1)$ $2^{|A|-3}\cdot(|A|-2)+2^{|A|-1}$ $O(n\log n)$ 计算了。

评测链接：AC submission.

CF1511G. Chips on a Board

题意：

$n$ $c$ $\forall i,c_i\le m$ $q$ $l,r$ ，请判断：
$\bigoplus_{i=1}^n [l\le a_i \le r](a_i-l)$
$0$ $0$ 请输出 AB $n,m\le 2\times 10^5$ 。

题解：

$0$ ，这些操作在省选联考的《树》这一题中已经有所使用，因此不再赘述。

$n\sqrt n\log n$ 的做法，几乎可以草过去。然后如何卡常？

1.奇偶位排序。

2.用非递归写法实现 Trie 和整体加一操作（真的不好写）///

$50000$ 则暴力求解；否咋再加入莫队；这样可以大大减小常数。

评测链接：AC submission.

CF1503D. Flip the Cards

题意：

$n$ $1\sim 2n$ $n\le 2\times 10^5$ 。

题解：

$1$ $n$ $[a_i>n]=[b_i>n]$ 的牌，一旦存在则无解。

$f(k)$ $k\in[1,n]$ $[n+1,2n]$ $f$ 序列划分成两个分别递减的序列并且最小化花费。

$\min_{j\le i-1}f(j)>\max_{j\ge i}f(j)$ 来分段，每一段内的取值方案只有互反的两种。证明：

$\min$ $\max$ $\max$ $\min$ 。
$k_1$ $k_2$ $k_1<k_2$ $f_i$ 。
$f_i<k_1$ $f_i$ $k_1$ 大的值。
$f_i>k_1$ ，则必须加入第二个序列；若不能加入，则 return 0*puts("-1")。

评测链接：AC submission.

CF1500C. Matrix Sorting

题意：

$n\times m$ Excel $A$ $b$ 。
$n,m\le1500$ .

题解：

首先有一个显然的暴力的从后向前枚举操作序列的 dfs：设当前需要区分的连续的子区间有这一些，选择一个没有选择过的、满足在这些关键位置的值都满足大于等于的关系的列，按它排序一下，然后更新一下没有区分开的这些关键段，往下递归……

$S$ ,我们先选哪个其实没有影响，因为每一次选择结果仅仅是把条件放宽，大不了在更深层我再选择那个落选的嘛……

dfs $O(nm^2)$ ，利用 bitset 优化即可草过去。

评测链接：AC submission. （论滥用 STL 的最高境界）。

CF1499F. Diameter Cuts

题意：

$k$ 。
$n,k\le5000$ $998244353$ 取模。

题解：

树形DP $f_{i,j}$ $i$ $j$ 的方案数。

于是有转移方程

f_{fa,i}\cdot f_{u,j}\rightarrow f_{fa,\max(i,j+1)}\ \ \ \ \ (i+j+1\le k)

DP $O(n^2)$ 的。

评测链接：AC submission.

CF1497E2. Square-free division (hard version)

题意：

$a$ $n$ 个正整数构成。你需要将它们分割成最小数量的连续子段，使得每一个子段中的任意两个数（不同位置）的乘积不为完全平方数。
$k$ 次修改操作。
在一次修改操作中，你可以选择数组中的某个位置的数，将该位置的数变为任意正整数。
$k$ $n\le2\times10^5$ $k\le20$ 。

题解：

将每个数的完全平方因子全部除掉，只剩下出现奇数次的质因子的乘积，问题就变成了分成若干段使得一段中没有相同的两个数。

$f_{i,j}$ $i$ $j$ 个数的最小段数，于是有状态转移方程：

f_{i,j}=\min_{k\le i}\{f_{k,j-calc(k+1,j)}+1\}

$k\le20$ $calc$ $k$ 个增长点，每次 DP 取每个区间的左端点（DP 数组递增）。

$i$ $lst_i$ vector $O(nk^2)$ 。

评测链接：AC submission.

CF1497D. Genius

题意：

$n$ $i$ $n$ $i$ $c_i=2^i$ $tag_i$ $s_i$ $i$ $j$ $IQ\le|c_i-c_j|$ $tag_i\neq tag_j$ $i$ $j$ $IQ$ $|c_i-c_j|$ $|s_i-s_j|$ 分。
$IQ=0$ $n\le5000$ 。

题解：

一个重要的结论是，当往左跳了一步后，就不能再往左跳了。

$f_{i,j}$ $i$ $j$ $i$ $j$ $f_{j,\le i}$ $\min$ $f$ $h_i=\max\{f_{j,i}\}$ $f_{i}$ $h$ $f_{i,j}(i,j)$ 的值。

$tag$ $if$ $O(n^2)$ 。

评测链接：AC submission.