CF2148C 题解

RyanLi · 2025-09-22 16:04:04 · 题解

传送门：洛谷 CF2148C Pacer | Codeforces C. Pacer

更佳的阅读体验：CF2148C 题解

简要题意：FJ 第 0 分钟位于第 0 边（另一边记为第 1 边），每分钟 FJ 可以选择是否跑到另一边——每次跑到另一边记 1 分，直到第 m 分钟结束。要求在第 a_i 分钟时，FJ 必须位于第 b_i 边，求满足条件的最大得分。

因为保证条件按时间顺序给出，因此我们考虑对于第 i 条限制进行分类讨论：

• 如果 b_i = b_{i - 1}：
  • 如果 a_i - a_{i - 1} 是奇数，那么 FJ 有一分钟是不能动的，答案就是 a_i - a_{i - 1} - 1。
  • 如果 a_i - a_{i - 1} 是偶数，那么 FJ 可以一直跑，答案就是 a_i - a_{i - 1}。
• 如果 b_i \neq b_{i - 1}：
  • 如果 a_i - a_{i - 1} 是奇数，那么 FJ 可以一直跑，答案就是 a_i - a_{i - 1}。
  • 如果 a_i - a_{i - 1} 是偶数，那么 FJ 有一分钟是不能动的，答案就是 a_i - a_{i - 1} - 1。

把这些答案加起来即可。因为没有要求第 m 分钟时需要在哪一边，我们只需要再给答案加上 m - a_n 即可。

#include <iostream>
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
int t, n, m, a[N], b[N];
ll ans;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
        for (int i = 1; i <= n; ++i) {
            if (b[i] == b[i - 1]) {
                if (a[i] - a[i - 1] & 1) ans += a[i] - a[i - 1] - 1;
                else ans += a[i] - a[i - 1];
            } else {
                if (a[i] - a[i - 1] & 1) ans += a[i] - a[i - 1];
                else ans += a[i] - a[i - 1] - 1;
            }
        } ans += m - a[n];
        cout << ans << '\n';
    } return 0;
}