「USACO 2025 US Open Platinum」Package Pickup 题解

题目大意

Farmer John 在数轴上分布奶牛和包裹：

• 选定一个数字 $M$（$1 \le M \le 10^{18}$）
• $N$ 个奶牛区间 $[L_i, R_i]$，奶牛位于 $L_i, L_i+M, L_i+2M, \dots, R_i$
• $P$ 个包裹区间 $[A_j, B_j]$，包裹位于 $A_j, A_j+M, A_j+2M, \dots, B_j$
• 每秒可以移动一头奶牛一个单位距离
• 求捡起所有包裹的最短时间

解题思路

关键观察

1. 模 $M$ 分组：所有奶牛和包裹的位置都可以表示为 $r + kM$ 的形式，其中 $r = x \bmod M$。因此可以按余数 $r$ 分组，每组独立处理。

2. 问题转化：对于每个余数组，问题转化为在一条直线上有若干奶牛区间和包裹区间，求用最少的移动步数让所有包裹都被奶牛访问到。

3. 区间合并：可以使用动态规划来合并区间信息，但直接合并复杂度太高，需要优化。

算法设计

状态设计

使用 $4 \times 4$ 的矩阵来表示状态转移代价：

• 状态 0：区间左端点在奶牛位置
• 状态 1：区间左端点在包裹位置
• 状态 2：区间右端点在奶牛位置
• 状态 3：区间右端点在包裹位置

矩阵 $f[i][j]$ 表示从状态 $i$ 到状态 $j$ 的最小代价。

矩阵合并

对于两个相邻的区间，它们的合并通过矩阵乘法实现：

• 基本矩阵 bd(z) 表示间隔为 $z$ 时的转移代价
• 区间信息通过 * 运算符合并，考虑了区间间距的影响

数据结构优化

1. 线段树：使用线段树维护每个余数组内的区间信息，支持快速插入、删除和查询
2. 快速幂：对于跨块的区间合并，使用矩阵快速幂来加速
3. 离散化处理：用 map 记录关键点，分段处理

算法流程

1. 输入处理：读入所有奶牛和包裹区间
2. 按余数排序：将所有区间按 $l \bmod M$ 排序
3. 建立关键点：用 map 记录所有区间的起点和终点对应的块编号
4. 线段树维护：
   • 插入区间时更新线段树
   • 删除区间时清空对应节点
   • 通过线段树合并区间信息
5. 跨块合并：对于每个块区间，使用矩阵快速幂合并信息
6. 答案提取：从最终矩阵的状态 2、3 到状态 0、1 中取最小值作为答案

复杂度分析

• 排序：$O((N+P)\log(N+P))$
• 线段树操作：$O((N+P)\log(N+P))$
• 矩阵乘法：$O(k^3)$，其中 $k=4$
• 总复杂度：$O((N+P)\log(N+P) \cdot k^3)$，可以处理 $N,P \le 2\times 10^4$ 的数据

代码实现要点

// 矩阵定义
struct Mat {
    ll f[4][4];
    // 初始化为无穷大
};

// 基础转移矩阵
Mat bd(ll z) {
    // 根据间隔 z 构造转移矩阵
    // 不同状态间的转移代价不同
}

// 区间信息结构体
struct info {
    ll l, r;
    Mat f;
    // 合并运算符重载
};

样例分析

样例 1：

M=100, 奶牛: [10,10], [20,20], [30,30]
包裹: [7,7], [11,11], [13,13], [17,17], [24,24], [26,26], [33,33]

按余数分组后，在同一组内计算最小移动代价，最终得到 22。

样例 2：

M=2, 奶牛: [1,5], 包裹: [2,6]

奶牛位置：1,3,5；包裹位置：2,4,6。最优方案需要 3 步。

总结

本题的难点在于：

1. 发现模 $M$ 分组的性质
2. 设计合适的状态表示和转移矩阵
3. 使用线段树和快速幂优化合并过程

通过将问题分解为独立余数组，并在每组内使用矩阵优化的动态规划，最终高效解决了这个看似复杂的问题。

标签：离散化、线段树、矩阵快速幂、动态规划、模运算分组