许久没有写过博客了,让 2023 成为一个新的起点,重新开始写博客。尽量写的高质量一点,从 E 开始。
E - Don't Isolate Elements
考虑 dp,考虑如何设计状态。
不难看出,每一行变两次等于没变,每一行只对上下两行产生影响。
基于上面的两个结论,我们令 \(f[i][0/1][0/1]\) 表示当前处理到第 \(i\) 行,第 \(i\) 行是否变换,第 \(i-1\) 行是否变换,使状态合法的最小变换次数。
转移的时候只需要枚举第 \(i-2\) 行即可。
初值设定需要注意,判断合法需要注意。
code
F - Permutation Distance
分类讨论,打开绝对值,使用树状数组维护即可。
公式可以看官方题解里的。
code
G - Partial Xor Enumeration
第 \(k\) 小线性基的板子题。
套路地对线性基进行 rebuild,使每一行只有一个 \(1\),查询二进制拆分即可。
线性基
code