CF1553 C~I 题解

上红了纪念下，都写写完。

C - Penalty

考虑贪心，若第一组胜，那么将其？都换为1，对手?都换为0，就能求最早轮数。类似算一次第二组胜的情况去最小即可。复杂度$O(n)$ .my code

$O(2^nn)$​暴力也能过。

D - Backspace

观察一下，能产生的序列满足，删掉任意长度的前缀，然后删若干对连续的两个。

逆序贪心，能匹配就匹配即可。

证明：考虑第$i$​​个字符与原串第$j$​个位置能匹配，但我们跳过去匹配$j-2k$​,那么$i-1$​能匹配的位置就变成了贪心方法的子集，即贪心方法有更多机会。

复杂度$O(n)$​.My code

E - Permutation Shift

考虑暴力怎么做。

枚举$i\in [0,n-1]$ 判断shift $i$次之后能否合法。考虑以最终该去的位置重标号，就变成了将一个排列变成有序需要的最小交换次数。

这是一个经典问题：对于该排列的每个轮换$cyc$​​​,都要交换$|cyc|-1$​​次。故check的复杂度是 $O(n)$​ 的。

但是要枚举所有shift的结果，变成$O(n^2)$​无法接受。

观察$m\le \lfloor\frac{n}3 \rfloor$​，记shift后的结果与给定序列匹配位置数$L$,至少交换$\lfloor\frac{n-L}2\rfloor$ 次，故有希望的排列要满足

$$\lfloor\frac{n-L}2\rfloor\le m\le\lfloor\frac{n}3 \rfloor\Rightarrow L\ge \lfloor\frac{n}3 \rfloor$$
而shift的每个位置都不同，所以只需检查至多4个排列，用上面方法check即可。

复杂度$O(n)$ My code

F - Pairwise Modulo

套路题（做法不唯一）。$x\mod y=x-\lfloor\frac{x}y\rfloor y$，有个整除就很套路了。

考虑加入$a_i,$求$\sum_{j<i}a_i\mod a_j$​和$\sum_{j<i}a_j\mod a_i$

前者直接整除分块，求$O(\sqrt n)$次区间和以及单点修改，用值域分块平衡复杂度可以做到共$O(n\sqrt n)$.

后者根号分治，$a_i<\sqrt V$​的维护$\sqrt V\times \sqrt V$​的表，$\ge \sqrt V$​的暴力枚举倍数，同样用值域分块平衡复杂度做到$O(n\sqrt n )$​

My code

G - Common Divisor Graph

首先答案不超过2.

判断答案是否为0：对每个素数建点，原图上的点与其素因子都连上边，用并查集维护，$s$与$t$在同一集合则为0。

判断答案是否为1：枚举$i$​​,考虑$a_i+1$​​的素因子对$(p_i,p_j)$​​，$p_i$​​所在连通块中所有点与$p_j$所在连通块中所有点的答案都可以是1.一种做法是直接将$p_i,p_j$连通块的根都暴力插入std::set 然后直接询问。

在数互不相同意义下素因子个数是$O(\log \log V)$的，复杂度为$O(n(\log\log V)^2\log n)$

My code

H - XOR and Distance

题解做法是Trie上乱搞太屑了，讲一下评论区老哥给出的高明做法。

考虑FWT的过程，从低位往高位考虑。设考虑到第$k$位。

$ans(k,x)$​​表示$x$​​的答案 ,$fi(k,x)$​​表示高位与$x$​​相同的数的最小值，$fx(k,x)$​​表示高位与$x$​​相同的数的最大值。

考虑FWT时的一对$(x,y)$只需：
$$ans(k,x)=\min\{ans(k-1,x),ans(k-1,y),fi(y)+2^k-fx(x)\}$$
$ans(k,y),fi(k,x),fx(k,x)$之类都同理更新。

根据FWT的原理，$k$这一维可以略去，时间复杂度$O(2^kk)$空间$O(2^k)$.

My code(shortest)

I - Stairs

$\text{Lemma}:$​​ 所有极长连续 递增/递减 段不交。

反证即可。所以原序列是由若干段数组成，每段长度与其中所有元素大小相等（若不符就是0）。

设段数为$x$，看上去答案是$x!2^\text{大于1的段数}$ ，其实不是。因为可能会有不极长的情况，也就是$[1,2,3][4,5,6]\Rightarrow [1,2,3,4,5,6]$ 这种。

考虑容斥与dp，$f(i,j)$表示考虑前$i$段，真正分开了$j$段，且最后一段长度大于1的贡献和（贡献和就是给每一个大于1的段都乘2）$g(i,j)$表示最后一段长度恰为1的贡献和。

这样就能$O(n^2)$了。

考虑生成函数后将转移式子用矩阵描述，分治NTT求即可。复杂度$O(n\log^2n)$ .

My code

Bonus1: Benq代码跑的很快，比我快就算了，甚至吊打了有technology的yhx,他的代码中似乎没有出现矩阵是怎么回事？

Bonus2: 矩阵只有两种，是否存在更低复杂度的方法？注意矩阵只有一种的时候可以对单位根插值最后IDFT的。