传送门：洛谷 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;
}