专栏文章

CF2148C 题解

RRyanLi要开心
CF2148C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintlp0p
此快照首次捕获于
2025/12/02 08:08
3 个月前
此快照最后确认于
2025/12/02 08:08
3 个月前
查看原文
传送门：洛谷 CF2148C Pacer | Codeforces C. Pacer
更佳的阅读体验：CF2148C 题解
简要题意：FJ 第 00 分钟位于第 00 边（另一边记为第 11 边），每分钟 FJ 可以选择是否跑到另一边——每次跑到另一边记 11 分，直到第 mm 分钟结束。要求在第 aia_i 分钟时，FJ 必须位于第 bib_i 边，求满足条件的最大得分。
因为保证条件按时间顺序给出，因此我们考虑对于第 ii 条限制进行分类讨论：
  • 如果 bi=bi−1b_i = b_{i - 1}：
    • 如果 ai−ai−1a_i - a_{i - 1} 是奇数，那么 FJ 有一分钟是不能动的，答案就是 ai−ai−1−1a_i - a_{i - 1} - 1。
    • 如果 ai−ai−1a_i - a_{i - 1} 是偶数，那么 FJ 可以一直跑，答案就是 ai−ai−1a_i - a_{i - 1}。
  • 如果 bi≠bi−1b_i \neq b_{i - 1}：
    • 如果 ai−ai−1a_i - a_{i - 1} 是奇数，那么 FJ 可以一直跑，答案就是 ai−ai−1a_i - a_{i - 1}。
    • 如果 ai−ai−1a_i - a_{i - 1} 是偶数，那么 FJ 有一分钟是不能动的，答案就是 ai−ai−1−1a_i - a_{i - 1} - 1。
把这些答案加起来即可。因为没有要求第 mm 分钟时需要在哪一边，我们只需要再给答案加上 m−anm - a_n 即可。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...