浅念づ昔夜's Blog

前置知识

扩展欧几里得算法（辗转相除法）

对 $\forall a,b \in \mathbb{N^+}$，有

$$\gcd(a,b)=\gcd(b, a\bmod b)$$

传送门

Solution

设两个二进制串有 $k$ 位不同，那么它们的距离 $d=k$。设与串 $i$ 的距离为 $d_i$，题目即求使得 $\min\{d_1,d_2,d_3\}$ 最大的串。

传送门

Solution

设 $f_1(x)=a_1x+b_1$，$f_2(x)=a_2x+b_2$。若 $f_1(f_2(x))<f_2(f_1(x))$，则 $a_1b_2+a_1<a_2b_1+b_2$。又因为 $b_1,b_2>0$，移项得$\dfrac{a_1-1}{b_1}<\dfrac{a_2-1}{b_2}$。

传送门

Solution

朴素算法

遍历所有点来选择询问点，每次删点后，暴力更新每个点的 $w_{\delta}$。

时间复杂度 $O(mn^2)$，可通过 CCF 原数据。

传送门

Solution

设 $fib_i$ 为斐波那契数列的第 $i$ 项，$c_i$ 为第 $i$ 格的芯片数，那么当所有 $c_i$ 确定时，无论怎么操作，都能保证 $k=\sum fib_ic_i$ 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。

传送门

Solution

有一个显然的事实：被删除的块的大小一定是 $k$ 的整数倍。因此我们不妨将原先的操作变成：挑选 $\lfloor \dfrac{n-1}{m} \rfloor$ 个不重复的，大小为 $k$ 的区间进行消除。

队伍配置

最低配置

芙宁娜 1+0，其余 0+0，共 5 金。

0 命芙不作推荐，不如胡行钟夜。

传送门

Solution

先用树状数组求逆序对，得出数组总共的逆序对数量 $tot$。设 $a_i$ 和它前面的数共组成 $inv_i$ 对逆序对。

手玩样例后不难理解，操作 $i$ 的本质，其实就是对所有 $j\le i$，若 $a_j$ 非零，则 $a_j-1$。设执行操作 $i$ 前有 $m$ 个 $a_j$ 非零，则执行操作后整个序列的逆序对数量减少 $m$。

传送门

Solution

小清新构造题。

把每一格初始化为 $-1$，接下来进行 $n$ 次操作。第 $i$ 次操作将第 $p_i$ 行为 $-1$ 的格子全部变成 $0$，然后将第 $q_{n-i+1}$ 列为 $-1$ 的格子全部变成 $1$。