「POI2018 R3」两根长棒 Two long candy sticks 题解

题目分析

我们需要从两支棒棒糖中各取一段，使得两段中草莓和香草的总长度完全相同，并且这两段的总长度尽可能大。

关键观察

1. 口味平衡条件：两段中草莓总长度相等，香草总长度相等
2. 段结构：每支棒棒糖由交替的草莓段和香草段组成
3. 可分割性：可以在段内任意位置分割，但必须保持段完整性

问题转化

设第一支棒棒糖的段序列为 $A$，第二支为 $B$。我们需要找到：

• 从 $A$ 中选取一个连续子序列（可跨段分割）
• 从 $B$ 中选取一个连续子序列（可跨段分割）
• 使得两个子序列的草莓总长度相等，香草总长度相等
• 最大化两个子序列的长度之和

解法思路

核心思想：前缀和 + 哈希映射

对于每支棒棒糖，我们维护一个状态向量 $(s, w)$，表示：

• $s$: 当前累计的草莓长度
• $w$: 当前累计的香草长度

由于我们可以在段内任意位置分割，每个可能的 $(s, w)$ 状态都对应一个总长度 $s + w$。

算法步骤

步骤1：预处理状态集合

对于每支棒棒糖：

1. 从起点开始扫描所有段
2. 对于每个分割点（段边界或段内任意位置），记录状态 $(s, w)$ 和对应的总长度
3. 使用哈希表存储：map[(s, w)] = max_length

优化：实际上我们只需要记录所有可能的 $(s, w)$ 状态，因为对于相同的状态，我们只关心最大长度。

步骤2：寻找匹配状态

对于两个状态集合 $S_A$ 和 $S_B$：

• 寻找所有满足 $(s_1, w_1) = (s_2, w_2)$ 的状态对
• 对于每个匹配的状态对，计算总长度 $len_A + len_B$
• 取最大值作为答案

复杂度分析

• 每支棒棒糖最多有 $O(m)$ 个关键分割点
• 状态数量：$O(m^2)$ 级别（但实际中会少很多）
• 使用哈希表查找：$O(1)$ 平均复杂度
• 总复杂度：$O(m^2)$，在 $m \leq 10^5$ 时可能过大

优化策略

由于 $m$ 可能达到 $10^5$，直接枚举所有状态不可行。我们需要更高效的方法：

优化1：离散化状态

注意到我们只关心状态的相对关系，可以将 $(s, w)$ 离散化为 $(s - w, s + w)$ 或其他形式来减少状态数量。

优化2：双指针扫描

对于每支棒棒糖，我们可以维护所有可能的差值状态 $d = s - w$，对于每个差值记录对应的最大总长度。

然后使用双指针或扫描线方法寻找匹配的差值。

优化3：数学性质利用

观察发现，如果两段要满足草莓和香草长度分别相等，那么：

• 总长度必须相等（因为 $s_A + w_A = s_B + w_B$）
• 草莓长度差必须为0（$s_A - s_B = 0$）

这提示我们可以将问题转化为寻找总长度相等且草莓长度差为0的配对。

参考实现框架

#include <bits/stdc++.h>
using namespace std;

struct Candy {
    vector<pair<char, int>> segments;
    map<pair<int, int>, int> states; // (strawberry, vanilla) -> max total length
    
    void read() {
        int m;
        cin >> m;
        segments.resize(m);
        for (int i = 0; i < m; i++) {
            cin >> segments[i].first >> segments[i].second;
        }
        preprocess();
    }
    
    void preprocess() {
        int s = 0, w = 0;
        states[{0, 0}] = 0;
        
        for (auto& seg : segments) {
            char type = seg.first;
            int len = seg.second;
            
            if (type == 'T') {
                // 草莓段
                for (int i = 1; i <= len; i++) {
                    s++;
                    states[{s, w}] = s + w;
                }
            } else {
                // 香草段  
                for (int i = 1; i <= len; i++) {
                    w++;
                    states[{s, w}] = s + w;
                }
            }
        }
    }
};

int main() {
    Candy A, B;
    A.read();
    B.read();
    
    int ans = 0;
    for (auto& stateA : A.states) {
        auto& key = stateA.first;
        int lenA = stateA.second;
        
        if (B.states.count(key)) {
            int lenB = B.states[key];
            ans = max(ans, lenA + lenB);
        }
    }
    
    cout << ans << endl;
    return 0;
}

进一步优化

对于大数据，上述方法仍会超时。实际AC代码需要：

1. 状态压缩：将 $(s, w)$ 映射为单个值，如 $s \times BASE + w$
2. 只记录关键状态：只记录每段结束时的状态，段内状态通过数学计算得到
3. 使用更高效的数据结构：如unordered_map
4. 差值匹配：转化为寻找 $s_A - w_A = s_B - w_B$ 且 $s_A = s_B$ 的配对

总结

本题的核心是将口味平衡条件转化为状态匹配问题，通过精心设计的状态表示和高效的查找算法来求解。虽然暴力方法思路简单，但要处理大数据需要深入的优化技巧。

算法标签：模拟、哈希、状态压缩、优化