专栏文章
题解:P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku
P14330题解参与者 2已保存评论 2
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @minf19ov
- 此快照首次捕获于
- 2025/12/02 01:21 3 个月前
- 此快照最后确认于
- 2025/12/02 01:21 3 个月前
P14330 [JOI2021 预选赛 R2] 往返滑道 / Round Sugoroku
分析
直接暴力的话,恭喜你, 分。
那我们就用
那我们就用
vector 记录一下每个 # 的位置,每次二分查找棋子下一个 # 的位置(将 x 看作 #), 加上这个位置减去棋子位置的绝对值。如果这个位置是 x,那棋子还得往前走一步, 加 。不是的话就删去这个这个位置。最后没有 # 的时候,就输出 。上代码!!!
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;
}
相关推荐
评论
共 2 条评论,欢迎与作者交流。
正在加载评论...