题目理解

我们有一个长度为 $N$ 的字符串 $S$，包含字符 A、B、C 和 ?。首尾字符固定为 A。需要将 ? 替换为 A、B 或 C，满足给定的 $X,Y,Z$ 数量约束，最小化相邻字符不同的位置数量。

关键观察

1. 问题转化

最小化相邻字符不同的数量等价于最大化连续相同字符的段数。

2. 基本结构

字符串被已知字符分割成若干段：

• 已知字符之间的 ? 段
• 不同已知字符之间的过渡段

算法核心

贪心策略 + 动态规划

代码使用了复杂的贪心策略和预处理技术来处理大规模数据。

算法流程

步骤1：预处理段信息

for i = 2 to n:
    if S[i] != '?':
        O = i - st - 1  // ?段长度
        x = S[st], y = S[i]
        
        if x == y:
            // 添加到对应A1,A2,A3
        else:
            P++  // 基础不同计数
            // 添加到对应B1,B2,B3

这里将 ? 段分为6类：

• A1: A...A 之间的段
• A2: B...B 之间的段
• A3: C...C 之间的段
• B1: A...B 或 B...A 之间的段
• B2: A...C 或 C...A 之间的段
• B3: B...C 或 C...B 之间的段

步骤2：排序和前缀和

sort(C + 1, C + 1 + len, cmp)  // 按某种权重排序
// 计算前缀和 SU1, SU2, SU3

步骤3：动态规划预处理

使用 bitset 优化背包问题：

F[0] = 1  // 初始状态
for each segment length:
    // 二进制分组优化多重背包
    G = (F << (x*i)) | F
    H = G ^ F
    // 更新stt数组

步骤4：旋转处理

由于问题关于 A,B,C 对称，代码通过旋转处理三种情况：

for v = 0 to 2:
    pre()  // 预处理
    for each query: sol(i)
    // 旋转字符和查询
    A->B->C->A
    X->Y->Z->X

步骤5：查询处理

void sol(ci i):
    // 检查三种字符的约束是否都能满足
    if 都能满足:
        ans = P + (A1.sol(X[i]) + A2.sol(Y[i]) + A3.sol(Z[i])) * 2
    else if 两种能满足:
        // 使用soll函数处理复杂情况
    else if 一种能满足:
        // 使用预处理信息计算

关键函数分析

1. soll 函数

处理两种约束满足、一种不满足的情况：

• 通过二分查找找到需要调整的段
• 计算需要减少的贡献值

2. 排序比较函数

cmp(ND x, ND y):
    return x.len * (1 + (y.bel <= 2)) > y.len * (1 + (x.bel <= 2))

这个比较函数体现了贪心策略：优先处理长度大且类型重要的段。

3. 二进制分组优化

while o > 0:
    int x = (o + 1) / 2
    sta[++le] = x
    o >>= 1

将多重背包问题通过二进制分组转化为 0-1 背包，提高效率。

算法正确性

1. 对称性利用

通过旋转处理 A,B,C 的对称性，将问题规约为有限种情况。

2. 贪心选择

按段长度和类型权重排序，优先处理能提供更大收益的段。

3. 动态规划优化

使用 bitset 和 ST 表优化状态转移和查询。

时间复杂度

• 预处理: $O(N \log N)$
• 动态规划: $O(N \sqrt{N})$（二进制分组优化）
• 查询处理: $O(Q \log N)$

由于 $N \leq 300000$, $Q \leq 200000$，算法在合理时间内运行。

关键数据结构

1. 段分类: A1,A2,A3,B1,B2,B3 存储不同类型段
2. 排序数组: C[] 统一处理所有段
3. bitset: F,G,H 用于动态规划状态压缩
4. ST表: stt[][] 快速查询最小值

算法优势

1. 问题分解: 将复杂问题分解为段处理
2. 对称性利用: 通过旋转减少情况分析
3. 高效预处理: 使用现代数据结构优化
4. 贪心优化: 合理选择处理顺序

算法标签

• 贪心算法
• 动态规划
• 字符串处理
• 组合优化
• 对称性利用
• 二进制分组

总结

该算法通过巧妙的段分类和贪心策略，结合动态规划和对称性处理，解决了复杂的字符串分配问题。核心思想是将最小化相邻不同转化为最大化连续相同，通过预处理和高效查询处理大规模数据。算法设计精妙，充分利用了问题的组合结构，是该类约束优化问题的优秀解法。