题解：P6995 [NEERC2014] Knockout Racing

mycbxzd · 2024-04-06 21:58:30 · 题解

题目翻译

背景

在潘多拉星球，赛车比以往任何时候都更受欢迎。但这些比赛相当不寻常。有 n 辆汽车参加在直线赛道上的比赛。每辆汽车以每秒 1 米的速度移动。赛道上的坐标以米为单位。

第 i 辆汽车在坐标为 a_{i} 和 b_{i} 的两点之间移动，从第二秒开始从点 a_{i} 出发。汽车从 a_{i} 移动到 b_{i}，然后从 b_{i} 移动到 a_{i}，再从 a_{i} 移动到 b_{i}，依此类推。

英俊的迈克想要用炸药淘汰一些汽车。因此，他有 m 个问题。第 j 个问题是：从开始后 t_{j} 秒后，坐标在 x_{j} 和 y_{j} 之间的汽车数量是多少（包括边界）？

你的任务是回答迈克的问题。

输入格式

输入文件的第一行包含两个整数 n 和 m (1 \le n , m \le 1000) -- 比赛中汽车的数量和问题的数量。

接下来的 n 行中，每行包含一辆汽车的描述：两个整数 a_{i} 和 b_{i} (0 \le a_{i}, b_{i} \le 10^{9}, a_{i} ≠ b_{i}) -- 汽车 i 移动的两个点的坐标。

接下来的 m 行中，每行包含一个问题的描述：三个整数 x_{j} , y_{j} , 和 t_{j} (0 \le x_{j} \le y_{j} \le 10^{9}, 0 \le t_{j} \le 10^{9}) -- 问题 j 的坐标范围和时间。

输出格式

写入输出文件 m 行。每行必须包含一个整数 -- 对应输入文件中给定的问题的答案。

解题

思路:

其实整个题目的核心就是三行代码解决

if ((t / (b[j] - a[j])) % 2 == 1) {l = b[j] - t % (b[j] - a[j]);
else l = a[j] + t % (b[j] - a[j]);
if (l >= x && l <= y)ans++;

• 计算在给定时间 t 后，位于坐标范围 [x, y] 内的车辆数量，并将结果存储在 ans 中。
• 首先，声明了一个名为 l 的 long long 类型变量，用于存储每辆车在给定时间 t 后的位置。
• 然后，通过 if-else 条件语句，根据每辆车在奇数或偶数往返周期内的不同，计算每辆车在给定时间 t 后的位置 l。如果车辆在奇数往返周期内，则 l 被赋值为 b[j] - t % (b[j] - a[j])，否则 l 被赋值为 a[j] + t % (b[j] - a[j])。
• 接着，通过条件判断 if (l >= x && l <= y)，检查每辆车在给定时间 t 后的位置 l 是否在指定的坐标范围 [x, y] 内。若在范围内，则将 ans 加一，表示有一辆车在该时间范围内位于指定的坐标范围内。

式子解释(不知道叫啥了就叫式子吧):

b[j] - t % (b[j] - a[j])

它计算了在给定时间 t 后，位于奇数往返周期内的车辆的位置。具体来说，b[j] - a[j] 表示车辆从起始坐标 a[j] 到结束坐标 b[j] 的距离，而 t % (b[j] - a[j]) 则表示当前往返周期内已经行驶的时间。因为车辆是以每秒 1 米的速度行驶的，所以 (b[j] - t % (b[j] - a[j])) 表示从结束坐标 b[j] 开始倒退，倒退的距离为当前往返周期内已行驶的时间，从而得到了车辆在奇数往返周期内的位置。

a[j] + t % (b[j] - a[j])

它计算了在给定时间 t 后，位于偶数往返周期内的车辆的位置。同样，a[j] 表示车辆的起始坐标，而 t % (b[j] - a[j]) 则表示当前往返周期内已经行驶的时间。因为车辆是以每秒 1 米的速度行驶的，所以 (a[j] + t % (b[j] - a[j])) 表示从起始坐标 a[j] 开始继续向前行驶，行驶的距离为当前往返周期内已行驶的时间，从而得到了车辆在偶数往返周期内的位置。

判断原因解释:

if (l >= x && l <= y)

它用于判断每辆车在给定时间 t 后的位置 l 是否在指定的坐标范围 [x, y] 内。如果车辆的位置 l 大于等于 x 并且小于等于 y，则说明该车辆在指定的坐标范围内，条件成立。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n, m, a[100010], b[1000010], x, y, t,ans,l;
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];
    // 对于每个问题，计算解决方案
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> t;
        ans = 0; 
        for (int j = 1; j <= n; j++) {
            if ((t / (b[j] - a[j])) % 2 == 1) {
                // 如果车辆在奇数往返周期内
                l = b[j] - t % (b[j] - a[j]);
            } else {
                // 如果车辆在偶数往返周期内
                l = a[j] + t % (b[j] - a[j]);
            }
            if (l >= x && l <= y)ans++;
        }
        cout << ans << endl;
    }
}