COCI 2014.11.29 T6 KAMIONI 题解

题目理解

有 $N$ 辆卡车在数轴上移动，每辆卡车以相同速度（$1$ 单位/分钟）行驶。每辆卡车的路线由 $K_i$ 个点 $A_1, A_2, \dots, A_{K_i}$ 描述，卡车在这些点之间往返行驶。给出 $M$ 个询问，每个询问要求计算两辆卡车在行驶过程中相遇的次数。

关键约束：

• 相遇可以在非整数位置发生
• 不会在初始时刻或转弯时刻相遇
• 不会在一辆车被外星人带走时相遇

问题转化

将卡车的运动轨迹表示为分段线性函数，问题转化为计算两个分段线性函数在有效时间区间内的交点个数。

运动轨迹建模

对于每辆卡车 $i$：

• 预处理每个路径点的时间戳：$t_0 = 0, t_j = t_{j-1} + |A_j - A_{j-1}|$
• 轨迹由线段组成：$[t_{j-1}, t_j]$ 时间内从 $A_{j-1}$ 线性移动到 $A_j$

核心思路

双指针扫描算法

对于询问 $(a, b)$：

1. 选择路径段数较少的卡车进行扫描
2. 对卡车 $a$ 的每个路段，找到卡车 $b$ 在对应时间区间内的路段
3. 检查两个路段是否相交

关键函数

• go(x, y, z)：计算从 $x$ 向 $y$ 移动 $z$ 时间后的位置
• jiao(a, b, c, d)：判断区间 $[a,b]$ 和 $[c,d]$ 是否有交集
• bh(p, q, l, r)：判断区间 $[l,r]$ 是否包含在 $[p,q]$ 内

算法实现

数据结构

vector<pair<int, int>> vec[maxn]; // vec[i][j] = (时间, 位置)

预处理

for (int i = 1, k; i <= n; i++) {
    cin >> k;
    vec[i].resize(k);
    for (auto &j : vec[i]) cin >> j.second;
    // 计算每个路径点的时间戳
    for (int j = 1; j < k; j++)
        vec[i][j].first = vec[i][j-1].first + 
                         abs(vec[i][j].second - vec[i][j-1].second);
}

查询处理

while (m--) {
    int a, b; cin >> a >> b;
    if (vec[a].size() > vec[b].size()) swap(a, b);
    
    // 记忆化
    if (mp.count({a, b})) {
        cout << mp[{a, b}] << '\n';
        continue;
    }
    
    int x = upper_bound(vec[b].begin(), vec[b].end(), 
                       make_pair(vec[a][0].first, 1000000000ll)) - 
            vec[b].begin() - 1;
    int ans = 0;
    
    // 扫描卡车a的每个路段
    for (int i = 1; i < vec[a].size(); i++) {
        // 更新卡车b的路段指针
        int y = x;
        if (vec[a].size() >= 200) {
            while (y != vec[b].size()-1 && vec[b][y+1].first < vec[a][i].first)
                y++;
        } else {
            y = upper_bound(vec[b].begin(), vec[b].end(),
                           make_pair(vec[a][i].first, 1000000000ll)) - 
                vec[b].begin() - 1;
        }
        
        // 计算路段端点位置
        int l = go(vec[b][x].second, vec[b][x+1].second,
                  vec[a][i-1].first - vec[b][x].first);
        int r;
        int p = vec[a][i-1].second, q = vec[a][i].second;
        
        if (y == vec[b].size()-1) {
            // 特殊处理最后一个路段
            if (vec[a][i].first - vec[b][y-1].first > 
                abs(vec[b][y].second - vec[b][y-1].second)) {
                r = vec[b][y].second;
                q = go(q, p, vec[a][i].first - vec[b][y-1].first - 
                       abs(vec[b][y].second - vec[b][y-1].second));
            } else {
                r = go(vec[b][y-1].second, vec[b][y].second,
                      vec[a][i].first - vec[b][y-1].first);
            }
        } else {
            r = go(vec[b][y].second, vec[b][y+1].second,
                  vec[a][i].first - vec[b][y].first);
        }
        
        // 检查是否相交
        if ((p <= q && l >= r && jiao(p, q, r, l)) ||
            (p >= q && l <= r && jiao(q, p, l, r)) ||
            ((p <= q) == (l <= r) && bh(p, q, l, r))) {
            ans++;
        }
        
        x = y;
        if (x == vec[b].size()-1) break;
    }
    
    cout << ans << '\n';
    mp[{a, b}] = ans;
}

复杂度分析

• 预处理：$O(\sum K_i)$，其中 $\sum K_i \leq 3 \times 10^5$
• 每次查询：$O(\min(K_a, K_b))$，通过双指针优化
• 记忆化：避免重复计算相同询问
• 总复杂度：$O(\sum K_i + M \cdot \min(K_i))$

算法标签

• 计算几何 - 线段相交检测
• 双指针 - 同步扫描两条路径
• 记忆化 - 避免重复计算
• 预处理 - 计算路径点时间戳
• 离散化 - 处理大规模坐标

总结

本题的关键在于：

1. 将卡车运动建模为分段线性轨迹
2. 使用双指针同步扫描两条路径
3. 高效判断线段在时间-空间域内的相交
4. 通过记忆化优化重复查询

这种方法避免了暴力枚举所有可能相遇点，在时间和空间复杂度上都达到了最优。