AT_arc203_d の题解

· · 题解

AT_arc203_d の题解

挂个博客先，博客访问更佳！！！

死磕 C 然后没想到有长为 H+W 的路径于是挂了。

题意

给定一个由 0 和 1 组成的长度为 N 的序列 A，处理 Q 次查询。每次查询翻转 A 中一个位置的数值。每次查询后，求满足条件的最小序列 B 的长度：通过多次在 B 的相邻元素间插入它们的异或结果，最终能得到当前的 A 序列。

分析

考虑倒着删数。

首先特判掉全为 1 的情况，然后就有以下情况：

实现

我们这样定义 A_i 的贡献（与上面一一对应）：

\begin{cases} -1 & \text{if } A_{i-1}=1\land A_i=1 \\ -1 & \text{if } A_{i-1}=0\land A_i=0 \land A_{i+1}=0 \\ -2 & \text{if } A_{i-1}=1\land A_i=0 \land A_{i+1}=1 \\ \end{cases}

为什么 1,0,1 的贡献是 -2，因为后面那个 1 并不会经过情况一造成贡献，于是就加进 0 的贡献。

注意到 1,0,1 的情况并没有考虑到只有一个 0，所以如果答案减成了 1 就要输出 2。

code

代码自取。