1111

jyh8221 · 2025-11-11 19:08:23 · 个人记录

t1

二分答案，贪心匹配（当前如果匹配，一定是上一个匹配的组+1）

t2

考虑预处理，将奇数位反转。 这样限制变成了ab->bb , ba -> aa。

考虑相邻字符不同的位置：

• 用差分数组 a 和 b 表示 X 和 Y 的边界：
  • a[i] = 1$ 表示 $X_i \neq X_{i-1}
  • b[i] = 1$ 表示 $Y_i \neq Y_{i-1}

X 能转换为 Y 当：

• 对于任意前缀 [1, k]，X 的边界数 \geq Y 的边界数。
  即：\forall k \in [1, n], \sum a[i] \geq \sum b[i]

• 等价于：$\bigoplus_1^n a_i = \bigoplus_1^n b_i

使用线段树维护数组：

题目条件等价于：

• 前缀： \min_{k=1}^n d[k] \geq 0
• 整体： 维护 \bigoplus_1^n a_i 和 \bigoplus_1^n b_i

当翻转原始字符串的第 p 个字符时：

更新X：

1. 翻转 a[p]
2. 更新线段树：
   • 翻转 a[p]：对区间 [1, p] 加 \Delta（\Delta = 1 如果 a[p] \to 1 ，否则为-1）
   • 翻转 a[p+1]
3. 更新 ca：ca \leftarrow ca \oplus 1（如果 p=n）

更新Y： 同理，翻转同时维护 b[p] 和 b[p+1]

每次更新后，检查：

• 最小值 \geq 0
• ca = cb

  即可。

  cf1763c

  分类讨论。

• n>4$时，$ans=\max a_i

  考虑1 1 4 5 1 4 -> 1 1 4 5 3 3 -> 1 1 4 5 0 0(造0)
  ->1 1 4 5 5 5-> 0 0 4 5 5 5 -> 5 5 5 5 5 5
  在右断点造0，把max传播到右端点，在对左端点做一遍即可。

• n=2$ , $ans=\max(a_1+a_2,2*|a_1-a_2|)

  显然只有两种情况。

• n=3,\max \in \{a_1,a_3\}$ : 同$n>3
• - $(1,3)$ : $3|a_3-a_1| \to ans
  • (1,2)$ : $3\cdot\max(|a_2-a_1|,a_3) \to ans

    做完后有|a_2-a_1|,a_3两个值，可以取最大的。

  • (2,3)$ : $3\cdot\max(|a_3-a_2|,a_1) \to ans

    cf2124e

    先考虑什么情况无解：

• \sum a_i = 1(\bmod 2)