题解：CF2148C Pacer

wangzhaohan2910 · 2025-09-27 10:26:55 · 题解

首先我们一看到 b_i\in\{0,1\} 就知道这是一道奇偶性的题。然后，我们发现，一分钟如果想待在同侧的话，得分最多的方案就是不跑，得 0 分。如果想跑到异侧，得分最多的方案就是直接跑过去，得 1 分。两分钟如果想到同侧的话，就跑个来回，得 2 分，如果想去到异侧的话，就跑过去，然后摸一分钟鱼，得 1 分。以此类推。

通过信息学竞赛中常用得不完全归纳法，我们可以得出，设有 k 分钟（k=a_i-a_{i-1}），得分最多的方案是：

• 如果 k 是奇数，并跑到异侧，则每分钟都用来跑步，得分为 k。
• 如果 k 是偶数，并跑到异侧，因为 k 不可能为 0（保证对于所有 i > 1，均有 a_i > a_{i-1}，所以 a_i-a_{i-1} > 0），所以必须摸一分钟鱼，然后剩下时间都用来跑步，得分为 k-1。
• 如果 k 是奇数，并跑到同侧，则也摸一分钟鱼，然后剩下的时间用来跑步，得分为 k-1。
• 如果 k 是偶数，并跑到同侧，就全力以赴，不停地折返跑，得分为 k。

接下来再解决一个问题：最后一个要求完成了，那剩下的时间（也就是 m-a_n）拿来干什么呢？摸鱼吗？

肯定不是呀，那肯定要不停的跑以获得最高的分数呀。所以最终得分还要加一个 m-a_n。

同时，作为信息学竞赛，我们还要讲究两个复杂度：时间复杂度和空间复杂度。时间复杂度显然最快也就只能是 O(n)，不可能再优化了，因为光输入就要这么长时间。那考虑优化空间复杂度。如果我们要把 a 数组和 b 数组都存下来，那么空间复杂度就是 O(n)，考虑到我们每次只需要四个数：a_i、a_{i-1}、b_i 以及 b_{i-1}，所以我们可以只保存这四个数，每次输入完后就把所谓的 a_{i-1} 与 b_{i-1} 更新一下，这样空间复杂度就是 O(1) 了。

以下见代码：

:::success[solution]

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace __gnu_debug;
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, preva{}, prevb{}, ans{};
        cin >> n >> m;
        while (n--)
        {
            int a, b;
            cin >> a >> b;
            if (b == prevb) // 同侧，所以要跑偶数次
                if (a - preva & 1) // 奇数分钟，所以要减去 1，否则会跑到异侧
                    ans += a - preva - 1;
                else // 偶数分钟，所以每分钟都要跑
                    ans += a - preva;
            else // 异侧，所以要跑奇数次
                if (a - preva & 1) // 如果时间本身就是奇数，就每分钟都要跑
                    ans += a - preva;
                else // 偶数分钟，所以要减去 1，否则会回到同侧
                    ans += a - preva - 1;
            preva = a;
            prevb = b;
        }
        // 剩下的时间都用来来回跑
        cout << m - preva + ans << endl;
    }
    return 0;
}

:::

不理解的同学可以自己跑一跑步试试。