题解：CF2148C Pacer

· · 题解

简要题意

你一开始位于坐标原点，每分钟可以选择跑到另一边或不跑，每一次跑到另一边可以加一分，你在第 a_i 分钟初必须位于第 b_i 边（初始边计为 0 号边，另一边计为第 1 号边）。计时到第 m 分钟停止，求最多获得多少分。本题多测。

思路

分类讨论。

首先，容易发现，只要没有限制，要想要活得最大分数，只需一直折返跑即可。

考虑处理限制。在每个时间间隔（即两个有要求的时刻之间）之内，我们折返跑要么不会产生影响，要么会使我们到另一边。这与时间长度的奇偶性有关（奇数会导致我们到另一边，偶数无影响）。如果在这个间隔中要求我们到另一边（即 b_i \not = b_{i+1} ），而时间长度恰好为奇数，或要求不到另一边而时间长度为偶，我们是无需处理限制的。反之，只需等上 1 分钟，就可以处理限制了。每次处理限制对答案的影响为 1 。

代码

#include<bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
#define pii pair<int,int>
#define db cout<<"done."<<endl;
#define endl '\n'//多测，方便检查 
using namespace std;
const int N=2e5+10;
int n,m;
struct node{
    int a,b;
}a[N];
int ans;
void solve(){
    ans=0;//多测清空好习惯 
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
    }
    for(int i=1;i<=n;i++){
        if(a[i].b==a[i-1].b){
            ans+=a[i].a-a[i-1].a//时间长度 
                -(a[i].a-a[i-1].a&1);//处理限制的代价 
        }else{
            ans+=a[i].a-a[i-1].a//时间长度
                -(!(a[i].a-a[i-1].a&1));//处理限制的代价 
        }
    }
    ans+=m-a[n].a;
    cout<<ans<<endl;
    return ;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();//多测 
    }
    return 0;
}

AC记录