专栏文章

AT_arc203_d の题解

aaaron0919
AT_arc203_d题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioir5hp
此快照首次捕获于
2025/12/02 19:53
3 个月前
此快照最后确认于
2025/12/02 19:53
3 个月前
查看原文

AT_arc203_d の题解

挂个博客先，博客访问更佳！！！
死磕 C 然后没想到有长为 H+WH+W 的路径于是挂了。

题意

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

分析

考虑倒着删数。
首先特判掉全为 11 的情况，然后就有以下情况：
  1. 1,11,1 很显然前后至少有一个 00 就可以删掉一个 11；
  2. 0,0,…,00,0,\dots,0 若干个 00 中间的显然可以删；
  3. 1,0,11,0,1 前后至少有一个 00 就可以删掉一个 00 和一个 11。

实现

我们这样定义 AiA_i 的贡献（与上面一一对应）：
{−1if Ai−1=1∧Ai=1−1if Ai−1=0∧Ai=0∧Ai+1=0−2if Ai−1=1∧Ai=0∧Ai+1=1\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,11,0,1 的贡献是 −2-2，因为后面那个 11 并不会经过情况一造成贡献，于是就加进 00 的贡献。
注意到 1,0,11,0,1 的情况并没有考虑到只有一个 00，所以如果答案减成了 11 就要输出 22。

code

代码自取。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...