题解：CF2148C Pacer

首先我们一看到

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)

了。

以下见代码：

solution

CPP

#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;
}

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

文章操作

相关推荐

评论

题解：CF2148C Pacer