专栏文章

题解:P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku

P14330题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@minf19ov
此快照首次捕获于
2025/12/02 01:21
3 个月前
此快照最后确认于
2025/12/02 01:21
3 个月前
查看原文
吐槽:我的复杂度似乎不太对,限制是 1s1s 就超时了

P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku

分析

直接暴力的话,恭喜你,4040 分。
那我们就用 vector 记录一下每个 # 的位置,每次二分查找棋子下一个 # 的位置(将 x 看作 #),ansans 加上这个位置减去棋子位置的绝对值。如果这个位置是 x,那棋子还得往前走一步,ansans11。不是的话就删去这个这个位置。最后没有 # 的时候,就输出 ansans

上代码!!!

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a,b=1,ans,sum;
char s[200001];
vector<int>e;
int main() {
//	freopen("a.in","r",stdin);
	scanf(" %d %d\n%s",&n,&a,s+1);
	e.push_back(0);//记录第一个x
	for(int i=1; i<=n; i++)if(s[i]=='#')e.push_back(i);
	e.push_back(n+1);//这一步必须在把#的位置记录完过后,再记录第二个x,不然还得排序
	while(1) {
		vector<int>::iterator x;
		if(b)x=lower_bound(e.begin(),e.end(),a);
		else x=upper_bound(e.begin(),e.end(),a)-1;
		ans+=abs((*x)-a);//记得abs
		b=!b;
		a=*x;
		if(a==n+1) {
			a--;
			ans++;//ans记得加1
		} else if(a==0) {
			a++;
			ans++;//同上
		}
		if((*x!=0)&&(*x!=n+1))/*是#就删除*/e.erase(x);
		if(e.size()==2)/*判断是否等于2,是因为还剩下两个x*/return printf("%d",ans),0;
	}
	return 0;
}
求赞qwp

评论

2 条评论,欢迎与作者交流。

正在加载评论...