POI 2012 Stage 1「Letters」题解

题目理解

我们有两个长度相同的字符串 $A$ 和 $B$，都由大写英文字母组成，且保证 $A$ 和 $B$ 中每种字母出现的次数相同。我们只能通过交换 $A$ 中相邻两个字符的操作，将 $A$ 变成 $B$。

关键性质：相邻交换的最小次数等于两个字符串对应位置的逆序对数。

问题转化思路

1. 建立映射关系

对于 $B$ 中的每个字符，我们需要找到它在 $A$ 中对应的位置。由于字符串中可能有重复字符，我们需要建立一对一的映射关系。

示例分析：

• $A = \text{"ABC"}$
• $B = \text{"BCA"}$

建立映射关系：

• $B[0] = \text{'B'} \rightarrow A[1] = \text{'B'}$
• $B[1] = \text{'C'} \rightarrow A[2] = \text{'C'}$
• $B[2] = \text{'A'} \rightarrow A[0] = \text{'A'}$

得到位置序列：$[1, 2, 0]$

2. 为什么是逆序对问题？

如果我们把 $A$ 中的字符按 $B$ 的顺序重新排列，需要的相邻交换次数就是这个新序列的逆序对数。

对于序列 $[1, 2, 0]$：

• $(1, 0)$ 是逆序对（$1 > 0$ 且 $1$ 在 $0$ 前面）
• $(2, 0)$ 是逆序对（$2 > 0$ 且 $2$ 在 $0$ 前面）

总共 $2$ 个逆序对，所以答案是 $2$。

算法实现详解

数据结构：树状数组 (Fenwick Tree)

struct bit {
    vector<int> tr;
    
    // 初始化
    bit(int n) { init(n); }
    void init(int n) { tr = vector<int>(n + 1); }
    
    // 单点更新：在位置x增加v
    void add(uint32_t x, int v) {
        x++;
        while (x < size(tr)) {
            tr[x] += v;
            x += x & (-x);  // 向上更新
        }
    }
    
    // 前缀和查询：返回[0, x]的和
    int ask(uint32_t x) {
        x++;
        int res = 0;
        while (x) {
            res += tr[x];
            x &= x - 1;  // 最低位1置0
        }
        return res;
    }
};

算法流程

步骤1：预处理每个字符在 $A$ 中的位置

vector<int> s(n);  // 存储A的字符
vector pos(26, vector<int>());  // 26个字母的位置列表

for (int i = 0; i < n; ++i) {
    char c;
    cin >> c;
    s[i] = c - 'A';
    pos[s[i]].emplace_back(i);  // 记录该字符出现位置
}

// 反转每个字符的位置列表，方便从后往前取
for (auto &i : pos)
    ranges::reverse(i);

对于 $A = \text{"ABC"}$：

• $\text{pos}[\text{'A'}] = [0]$
• $\text{pos}[\text{'B'}] = [1]$
• $\text{pos}[\text{'C'}] = [2]$

步骤2：处理 $B$ 并计算答案

long long ans = 0;
bit b(n);  // 树状数组，记录已使用的元素

for (int i = 0; i < n; ++i) {
    char x;
    cin >> x;
    x -= 'A';
    
    // 取出该字符在A中的对应位置
    int p = pos[x].back();
    pos[x].pop_back();
    
    // 计算实际位置偏移
    int tp = p + i - b.ask(p);
    ans += abs(i - tp);
    
    // 标记该位置已使用
    b.add(p, 1);
}

核心计算原理详解

tp = p + i - b.ask(p) 的含义：

• p：字符在原始 $A$ 中的位置
• b.ask(p)：在位置 p 之前已经有多少个元素被使用了
• i - b.ask(p)：由于前面的元素被使用后产生的空位数量
• tp：调整后的实际位置（考虑到已使用字符的空位）

为什么这样计算？

当我们按顺序处理 $B$ 的每个字符时，$A$ 中已经被使用的字符会"消失"，后面的字符会向前移动。我们需要计算这种移动后的新位置。

数学表达： 设当前处理到 $B$ 的第 $i$ 个字符，对应 $A$ 中的原始位置为 $p$，在 $p$ 之前有 $k$ 个位置已被使用，那么：

• 实际位置 = 原始位置 $p$ + 移动的空位数 $(i - k)$
• 其中 $i$ 是期望位置，$k$ 是前面已使用的元素数

时间复杂度分析

• 预处理：$O(n)$
• 树状数组操作：每次 $O(\log n)$
• 总复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

对于 $n \leq 1,000,000$ 的数据规模完全可行。

详细样例验证

以样例 $A = \text{"ABC"}$, $B = \text{"BCA"}$ 为例：

初始化：

• $\text{pos} = \{[0], [1], [2]\}$
• 树状数组初始为全0

执行过程：

1. 处理 $B[0] = \text{'B'}$：

   • $p = 1$（B在A中的位置）
   • $b.ask(1) = 0$（位置1之前没有已使用元素）
   • $tp = 1 + 0 - 0 = 1$
   • $ans += |0 - 1| = 1$
   • 标记位置1已使用：$b.add(1, 1)$

2. 处理 $B[1] = \text{'C'}$：

   • $p = 2$（C在A中的位置）
   • $b.ask(2) = 1$（位置2之前有1个已使用元素：位置1）
   • $tp = 2 + 1 - 1 = 2$
   • $ans += |1 - 2| = 1$
   • 标记位置2已使用：$b.add(2, 1)$

3. 处理 $B[2] = \text{'A'}$：

   • $p = 0$（A在A中的位置）
   • $b.ask(0) = 0$（位置0之前没有已使用元素）
   • $tp = 0 + 2 - 0 = 2$
   • $ans += |2 - 2| = 0$
   • 标记位置0已使用：$b.add(0, 1)$

最终答案：$1 + 1 + 0 = 2$ ✓

算法正确性证明

该算法的核心在于将问题转化为逆序对计数问题：

1. 映射建立：通过记录每个字符在 $A$ 中的所有出现位置，并按照 $B$ 的顺序依次取出，建立了从 $B$ 到 $A$ 的一一映射。

2. 位置调整：由于在处理过程中，$A$ 中已被使用的字符会产生空位，导致后续字符位置发生变化。通过树状数组动态维护已使用的位置，可以准确计算每个字符当前的实际位置。

3. 交换次数计算：$|i - tp|$ 实际上计算的是当前字符从实际位置移动到期望位置需要的交换次数，累加起来就是总的相邻交换次数。

总结

这道题的关键在于：

1. 问题转化：相邻交换次数 → 逆序对数
2. 位置映射：建立 $B$ 到 $A$ 的字符对应关系
3. 动态维护：使用树状数组高效统计已使用的位置
4. 位置调整：考虑已使用元素对位置的影响

代码通过巧妙的树状数组应用，避免了显式计算逆序对，直接得到了最终答案，是一个既高效又优雅的解决方案。