#PQJ1930x10150. QOJ 1930_10150

    ID: 2757 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十六省联合省选2025排序

QOJ 1930_10150

2025 联合省选 第二试推箱子(move) 推箱子(move) 【题目描述】 在一条无穷长的数轴上摆放着n 个箱子。第i (1 ≤i ≤n) 个箱子在时刻0 位于数 轴ai 处,而你希望在时刻ti 以及.之.后.的.所.有.时.刻,这个箱子处在数轴的bi 处。保证序 列[a1, . . . , an] 和[b1, . . . , bn] .单.调.递.增。 为此,从时刻0 开始的每个单位时间里,你可以将某个箱子在数轴上移动一个单位 长度,也可以什么都不做。你需要保证任意时刻每个点上都只有一个箱子。形式化地, 每个单位时间里你可以按照以下方式进行一次操作,也可以不进行操作:

  1. 选择任意一个箱子。记其编号为i,它目前的位置为pi。
  2. 选择一个方向d ∈{±1},其中d = 1 代表向右,d = −1 代表向左。你需要保证 数轴上(pi + d) 处没有箱子。
  3. 将i 号箱子从点pi 移动到点(pi + d) 处。 你想知道,是否存在一种操作方法同时满足所有箱子的要求,即对于任意1 ≤i ≤n, 第i 个箱子在时刻ti 以及之后的所有时刻都处于数轴的bi 处。 【输入格式】 从文件move.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据,第一行一个整数n,表示箱子的个数,接下来n 行,第i (1 ≤ i ≤n) 行三个整数ai, bi, ti,分别表示第i 个箱子的初始位置、目标位置和时刻要求。 【输出格式】 输出到文件move.out 中。 对于每组测试数据,输出一行一个字符串Yes 或No,表示是否存在一种操作方法 同时满足所有箱子的要求。 【样例1 输入】 1 0 2 2 2 3 4 5 1 4 6 7 1 5 3 6 4 5 3 第2 页 共11 页

2025 联合省选 第二试推箱子(move) 7 7 6 1 8 10 8 4 【样例1 输出】 1 No 2 Yes 【样例1 解释】 该组样例共有2 组测试数据。 • 对于第一组测试数据,答案是否定的。将1 号箱子由点4 移动到点5,并将2 号 箱子由点6 移动到点7,至少需要两个单位时间,因此不可能在时刻1 同时满足 两个箱子的条件。 • 对于第二组测试数据,答案是肯定的,例如如下方法同时满足了所有箱子的要求: – 在时刻0 至时刻1 的一个单位时间,将2 号箱子由点7 移动到点6; – 在时刻1 至时刻2 的一个单位时间,将3 号箱子由点10 移动到点9; – 在时刻2 至时刻3 的一个单位时间,将1 号箱子由点4 移动到点5; – 在时刻3 至时刻4 的一个单位时间,将3 号箱子由点9 移动到点8; – 在之后的所有单位时间,什么都不做。 【样例2】 见选手目录下的move/move2.in 与move/move2.ans。 该组样例共有6 组测试数据,所有数据均满足特殊性质A。其中每组测试数据的n 分别为7、7、7、200、3, 000、2 × 105,且测试数据1 ∼3 满足ai, bi ≤15,测试数据4 满足ai, bi ≤3, 000。 【样例3】 见选手目录下的move/move3.in 与move/move3.ans。 该组样例共有6 组测试数据,所有数据均满足特殊性质B。其中每组测试数据的n 分别为7、7、7、200、3, 000、2 × 105,且测试数据1 ∼3 满足ai, bi ≤15,测试数据4 满足ai, bi ≤3, 000。 【样例4】 见选手目录下的move/move4.in 与move/move4.ans。 第3 页 共11 页

2025 联合省选 第二试推箱子(move) 该组样例共有6 组测试数据,所有数据均满足特殊性质C。其中每组测试数据的n 分别为7、7、7、200、3, 000、2 × 105,且测试数据1 ∼3 满足ai, bi ≤15,测试数据4 满足ai, bi ≤3, 000。 【样例5】 见选手目录下的move/move5.in 与move/move5.ans。 该组样例共有6 组测试数据。其中每组测试数据的n 分别为7、7、7、200、3, 000、 2 × 105,且测试数据1 ∼3 满足ai, bi ≤15,测试数据4 满足ai, bi ≤3, 000。 【子任务】 对于所有测试点, • 1 ≤T ≤6, • 1 ≤n ≤2 × 105, • ∀1 ≤i ≤n, 1 ≤ai, bi ≤109, 0 ≤ti ≤1016, • ∀1 ≤i < n, ai < ai+1, bi < bi+1。 测试点编号 n ≤ ai, bi ≤ 特殊性质 1 7 15 A 2, 3 无 4 200 3,000 A 5 B 6, 7 无 8 3,000 109 A 9 B 10, 11 无 12 8 ×104 5 ×105 A 13 B 14, 15 C 16 ∼18 无 19, 20 2 ×105 109 B 21, 22 C 23 ∼25 无 特殊性质A:∀1 ≤i < j ≤n, ti = tj。 特殊性质B:∀1 ≤i ≤n, ai ≤bi 且∀1 ≤i < n, bi < ai+1。 特殊性质C:∀1 ≤i ≤n, ai ≤bi。 第4 页 共11 页