CSP 模拟 1
CSP 模拟 2
F
考虑 \(x\) 只能在 \(a_1\oplus b_i\) 里选，那么分别代入暴力检验即可 .
时间复杂度 \(\tilde\Theta(n^2)\)，可以通过 .
S
考虑交换同色的部分一定不优，所以同色字符的相对位置一定是不变的 . 那么操作序列和最终局面肯定是能形成双射的 .
于是只需要考虑计数最终局面，设计一个 DP，令 \(dp_{i,j,k,c}\) 表示三种颜色分别选了 \(i,j,k\) 个，第 \(i+j+k\) 位是 \(c\) 的最小步数 .
根据前面的分析，最小步数其实就是序列的「逆序对」个数，维护每个颜色的位置和每个位置前面颜色的个数即可计算贡献 .
时间复杂度 \(O(n^3)\)，需要滚动数组以将空间复杂度优化到 \(O(n^2)\) .
Y
原题：ARC124E Pass to Next .
对于操作序列 \(\{x_n\}\)，可以发现如果能减的话给每个元素都减一得到的最终局面不变 . 称一个满足 \(\min x_i=0\) 的操作序列 \(\{x\}\) 为素操作序列，那么可以发现素操作序列和最终局面之间是存在双射的，于是只需要计算素操作序列个数 .
考虑容斥计算，即算出 \(x_i\in[0,a_i]\) 的权值和减 \(x_i\in[1,a_i]\) 的权值和 . 做法本质相同，下面以前者为例 .
首先大力写出答案：\(\displaystyle\prod_{i=1}^n(a_i-x_i+x_{i-1})\) . 那么一项一项选就行了：
- 如果选 \(a_i\)，那么这一位的贡献即为 \(a_i\) .
- 如果选 \(-x_i\)，那么这一位的贡献即为 \(-x_i\)，表现出来是一个等差数列求和的形式 .
- 如果选 \(x_{i-1}\)，如果上一位选的是 \(x_i\) 那么贡献表现为平方和，否则表现为等差数列求和 .
由于有一个上一位的限制那么开一个状态机 DP 表示就好了，具体的，维护：
然后提出 \(\prod\) 内的一项考虑转移即可 .
最后，因为是环状结构所以需要破开然后钦定断点处的选择方案 . 时间复杂度 \(\Theta(n)\)，可以通过 .
O
原题：JOI 2020 Final 火事 .
shaber，等看懂了再补 .