「POI2010」罪犯 题解

题目概述

两个强盗 Bitie 和 Bytie 分别从两端开始抢劫房子：

• Bitie 从低编号到高编号抢劫
• Bytie 从高编号到低编号抢劫
• 他们在某个房子相遇后停止
• 已知他们起始房子的颜色相同（但不知道具体颜色）
• 每个强盗对每种颜色的房子最多抢劫一次
• 已知每个强盗抢劫的颜色序列（不包括起始房子）

要求找出所有可能的相遇点。

解题思路

关键观察

1. 起始条件：两个强盗起始房子的颜色必须相同
2. 路径限制：每个强盗必须按照给定的颜色序列抢劫
3. 相遇条件：Bitie 从左边能到达相遇点，Bytie 从右边能到达相遇点
4. 颜色匹配：相遇点的颜色必须是两个强盗序列的最后一个颜色（即 x1[m1] = x2[m2]）

算法步骤

1. 预处理颜色映射

将颜色序列转换为位置索引，便于后续处理：

• mp1[color] 表示颜色在 Bitie 序列中的位置
• mp2[color] 表示颜色在 Bytie 序列中的位置

2. 正向处理（Bitie 方向）

对于每个位置 i，计算：

• F1[i]：从左边开始，能够完整抢劫 Bitie 序列的最右起始位置
• G1[i]：当前颜色在序列中的前一个颜色的最近位置

使用动态规划和单调队列维护信息。

3. 反向处理（Bytie 方向）

对于每个位置 i，计算：

• F2[i]：从右边开始，能够完整抢劫 Bytie 序列的最左起始位置
• G2[i]：当前颜色在序列中的前一个颜色的最近位置

4. 处理起始颜色约束

计算每种颜色的最左出现位置 G1[color] 和最右出现位置 G2[color]，建立约束关系。

5. 验证相遇点

对于每个可能的相遇点 i（颜色为序列最后一个颜色）：

• 检查 Bitie 能否从左边到达 i（F1[i] != INF）
• 检查 Bytie 能否从右边到达 i（F2[i] != INF）
• 检查起始颜色约束：存在某种颜色，其最左位置在 Bitie 路径左侧，最右位置在 Bytie 路径右侧

复杂度分析

• 预处理：$O(n)$，每个位置只被处理常数次
• 查询：$O(n)$，遍历所有可能的相遇点
• 总复杂度：$O(n)$，适合 $n \leq 10^6$ 的数据规模

代码实现

#include <bits/stdc++.h>
#define maxn 1000005
#define INF 0x3f3f3f3f
using namespace std;

int n, k, m1, m2, c[maxn], b[maxn], x1[maxn], mp1[maxn], x2[maxn], mp2[maxn];
int F1[maxn], F2[maxn], G1[maxn], G2[maxn], q[maxn];

int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -f;
        ch = getchar();
    }
    while (isdigit(ch))
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++)
        c[i] = read(), b[i] = c[i];
    
    m1 = read(), m2 = read();
    
    // 建立颜色到序列位置的映射
    for (int i = 1; i <= m1; i++)
        x1[i] = read(), mp1[x1[i]] = i;
    for (int i = 1; i <= m2; i++)
        x2[i] = read(), mp2[x2[i]] = i;
    
    // 正向处理 Bitie 路径
    for (int i = 1; i <= n; i++)
        c[i] = mp1[c[i]];
    
    F1[0] = G1[0] = INF;
    for (int i = 1; i <= n; i++) {
        if (!c[i]) {  // 颜色不在 Bitie 序列中
            F1[i] = F1[i - 1];
            G1[i] = INF;
            continue;
        }
        
        if (c[i] == 1)
            G1[i] = i;  // 序列第一个颜色
        else
            G1[i] = G1[q[c[i] - 1]];  // 前一个颜色的最近位置
        
        if (c[i] == m1)
            F1[i] = G1[i];  // 完整序列的起始位置
        else
            F1[i] = F1[i - 1];
        
        q[c[i]] = i;  // 更新当前颜色的最新位置
    }
    
    // 反向处理 Bytie 路径
    for (int i = 1; i <= n; i++)
        c[i] = mp2[b[i]];
    
    F2[n + 1] = G2[n + 1] = INF;
    for (int i = n; i >= 1; i--) {
        if (!c[i]) {  // 颜色不在 Bytie 序列中
            F2[i] = F2[i + 1];
            G2[i] = INF;
            continue;
        }
        
        if (c[i] == 1)
            G2[i] = i;  // 序列第一个颜色
        else
            G2[i] = G2[q[c[i] - 1]];  // 前一个颜色的最近位置
        
        if (c[i] == m2)
            F2[i] = G2[i];  // 完整序列的起始位置
        else
            F2[i] = F2[i + 1];
        
        q[c[i]] = i;  // 更新当前颜色的最新位置
    }
    
    // 处理起始颜色约束
    memset(G1, 0, sizeof(G1));
    memset(G2, 0, sizeof(G2));
    memset(q, 0, sizeof(q));
    
    // 计算每种颜色的最左和最右出现位置
    for (int i = 1; i <= n; i++)
        if (!G1[b[i]]) G1[b[i]] = i;
    for (int i = n; i >= 1; i--)
        if (!G2[b[i]]) G2[b[i]] = i;
    
    // 建立约束：对于颜色i，如果起始位置在j，则Bytie起始位置至少为G2[i]
    for (int i = 1; i <= k; i++)
        q[G1[i]] = max(q[G1[i]], G2[i]);
    for (int i = 1; i <= n; i++)
        q[i] = max(q[i], q[i - 1]);
    
    // 统计答案
    int ans = 0;
    vector<int> result;
    
    for (int i = 1; i <= n; i++) {
        if (b[i] != x1[m1]) continue;  // 相遇点必须是序列最后一个颜色
        
        if (F1[i] == INF || F2[i] == INF) continue;  // 路径不完整
        
        // 检查是否存在起始颜色满足约束
        if (q[F1[i] - 1] >= F2[i] + 1) {
            ans++;
            result.push_back(i);
        }
    }
    
    // 输出结果
    printf("%d\n", ans);
    for (int pos : result)
        printf("%d ", pos);
    
    return 0;
}

样例解释

对于样例：

15 7
2 5 6 2 4 7 3 3 2 3 7 5 3 6 2
3 2
4 7 3
5 3

可能的起始颜色是 2 或 6：

• 颜色 2：Bitie 可从位置 1 或 4 开始，Bytie 从位置 15 开始
• 颜色 6：Bitie 从位置 3 开始，Bytie 从位置 14 开始

相遇点必须颜色为 3（序列最后一个颜色），且满足路径完整性约束，最终找到位置 7、8、10。

总结

本题的关键技巧：

1. 双向动态规划：分别处理两个方向的路径约束
2. 颜色映射：将颜色转换为序列位置便于处理
3. 约束传递：通过前缀最大值处理起始颜色约束
4. 相遇点验证：综合检查路径完整性和起始约束

这种双向处理的方法在解决路径相遇问题时非常有效。