2023 暑假集训模拟赛题解

Jijidawang / 2023-07-21 / 原文

CSP 模拟 1
CSP 模拟 2
- F
- S
- Y
- O

CSP 模拟 1

来自学长的馈赠 2 .

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 表示就好了，具体的，维护：

\[\begin{aligned}&f(n)=\sum_x\prod_{i=1}^n(a_i-x_i+x_{i-1})\\&g(n)=\sum_xx_n\prod_{i=1}^n(a_i-x_i+x_{i-1})\end{aligned} \]

然后提出 \(\prod\) 内的一项考虑转移即可 .

最后，因为是环状结构所以需要破开然后钦定断点处的选择方案 . 时间复杂度 \(\Theta(n)\)，可以通过 .

O

原题：JOI 2020 Final 火事 .

考虑每个点的影响写成四元组 \((p,t,t',d)\) 的形式，表示从 \(p\) 位置，\(t\sim t'\) 时刻，产生 \(+d\) 的贡献 .

对于一次询问，拆成两个前缀和相减，假设目前询问是 \((x,i)\) 表示查 \(i\) 时刻的前缀和 \(1\dots x\)，那么写出来贡献就是：

\[v=d\cdot(\min\{p+i-t,x\}-\min\{p,x\})=d\cdot(i+\min\{p-t,x-i\}-\min\{p,x\}) \]

由于询问部分和操作部分独立了，所以按 \(i\) 扫描线，\(p-t,p\) 开下标上里面记贡献，然后统计的时候就是区间求和了，线段树即可 . 时间复杂度 \(O((n+q)\log n)\)，可以通过 .

详细解释 (Delov) .