SS秋季训练3

training

A

source : AT_arc154_c

不同的元素个数减少，将 \(b\) 按权值连续段分段，有一段长度超过 \(2\) 就可以“旋转”。枚举 \(a\) 每个对应位置。

B

source : AT_arc160_c

两个合成一个等价于“进位”，顺序无关，从低往高做dp，\(dp_{i,j}\) 表示到第 \(i\) 位，进位了 \(j\)，状态数 \(O(n\log n)\)，可以记搜，但是转移还是会寄，搞个前缀和优化。

C

source : AT_arc144_c

打表找规律：最后 \(2k\) 个空留出来特殊处理，前面 \(n-2k\) 个空每 \(k\) 个一段，一段填 \(i+k\) 一段填 \(i-k\)，最后 \(2k\) 个里前 \(k\) 个填 \(i+k\)，剩下的空就将剩下的数排序放进去。

D

source : CF1725L

奇妙题，\(a_i := -a_i\) 实际上是 \(a_i:=a_i-2a_i\)，每次操作总和不变，可以想到转化成前缀和的变化，不难算出前缀和的变化是 \(\operatorname{swap}(s_i, s_{i-1})\)，让所有元素非负就是让前缀和不降，特判边界，答案就是前缀和逆序对数。

E

source : CF1725J

答案是所有边的和的两倍减掉两条链，其中这两条链要么交于一点要么相离，对于交于一点的情况，换根dp求出到每个点最近的四条路径，对于相离的情况，换根dp求出每条边祖先向和后代向的直径。

F

source : CF1767E

\(m \le 40\) 可以想到 meet in middle， 由序列可以得到一堆限制，对于前一半的子集 \(S\) ，求出其所有超集中可行的最小费用 \(f_S\)，枚举后一半的合法子集合并。

源神说可以爆搜，复杂度似乎是 \(O(F_n)\) 的，似乎能跑过。。

G

source : CF1725K

对于每个值，建一个点表示，将为这个值的元素在并查集上链到这个点上，外层拿个 set 找出修改的区间的点。

H

source : CF1762F

I

source : AT_arc142_e

神奇网络流，首先将 \(a_x,a_y\) 都补到 \(\min(b_x,b_y)\)，然后扔掉那些已经满足的限制，那么剩下的都满足 \(a_x \ge b_x\) 或 \(a_y \ge b_x\)，所以可以分成两类：\(a_x<b_x\) 和 \(a_x \ge b_x\)，对于这两类点给它整成一个二分图，对于第二类点可以切糕式拆点（权值很小），向汇点连一条权值为 \(1\) 的边，第一类点从源点连一条权值为 \(b_x-a_x\) 的边，有限制的从 \(x\) 到 \((y,b_x-a_x)\) 连一条权值为 \(inf\) 的边，第二类点的相邻权值点连权值为 \(inf\) 的边。这样就可以强制割两边之一。

J

source : AT_wtf22_day1_b

将所有置换环跑出来，环与环之间插一个 \((1,1)\) 让每个环独立，然后置换环上满足限制的操作顺序长得“非常”像一个单调栈踢人或者说笛卡尔树的过程（？？？），不会。