题解：CF2148C Pacer

简要题意

你一开始位于坐标原点，每分钟可以选择跑到另一边或不跑，每一次跑到另一边可以加一分，你在第

a_i

分钟初必须位于第

b_i

边（初始边计为

0

号边，另一边计为第

1

号边）。计时到第

m

分钟停止，求最多获得多少分。本题多测。

思路

分类讨论。

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

考虑处理限制。在每个时间间隔（即两个有要求的时刻之间）之内，我们折返跑要么不会产生影响，要么会使我们到另一边。这与时间长度的奇偶性有关（奇数会导致我们到另一边，偶数无影响）。如果在这个间隔中要求我们到另一边（即

b_i \not = b_{i+1}

），而时间长度恰好为奇数，或要求不到另一边而时间长度为偶，我们是无需处理限制的。反之，只需等上

1

分钟，就可以处理限制了。每次处理限制对答案的影响为

1

。

代码

CPP

#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记录

文章操作

简要题意

思路

代码

相关推荐

评论

题解：CF2148C Pacer