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

· · 题解

有点强度的一道题，建议升黄（花了半个小时才AC）

直接暴力模拟肯定是会TLE的。我们使用链表解决。

我们记转向点为 # 和 x。

对于每一个转向点，我们使用一个链表节点对其进行标记，并记录它的前一个和后一个转向点。

然后进行模拟。从位置 A 开始进行模拟。对于每一次模拟，如果当前的方向为右，就找到它的后继，然后给结果加上后继节点与当前的节点的差。随后，改变它的方向。额外地，如果这个转向点是 #，我们就记录已经走过的 # 的数量，即 cnt++;，然后删除这个节点，即删除这个 #。当 cnt = N 时，代表我们已经走完所有 # 了，此时的 ans 就是答案。

特别地，ans 要开 long long。

代码如下：


#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
enum Way // 定义一个只有left和right两个值的类型，用于表示方向 
{
    W_left = 0,
    W_right
};
const int N = 2e5 + 10;
char s[N];
int n, a, cnt;
struct Node // 链表，储存前驱和后继
{
    int pre, nxt;
}lst[N];

int main()
{
    scanf("%d %d %s", &n, &a, s + 1);
    s[0] = s[n + 1] = 'x';
    int pre = 0, nxt = n + 1;
    // 建链表 
    for(int i = 1; i <= n + 1; i ++)
    {
        lst[i].pre = pre;
        if(s[i] == '#') pre = i, cnt ++;
    }
    for(int i = n; i >= 0; i --)
    {
        lst[i].nxt = nxt;
        if(s[i] == '#') nxt = i;
    }
    //循环模拟 
    Way way = W_right;
    LL ans = 0;
    while(cnt)
    {
        if(way == W_right)
        {
            ans += lst[a].nxt - a;
            way = W_left;
            a = lst[a].nxt;
            if(a != n + 1)
                cnt --,
                lst[lst[a].nxt].pre = lst[a].pre,
                lst[lst[a].pre].nxt = lst[a].nxt;
        }
        else
        {
            ans += a - lst[a].pre;
            way = W_right;
            a = lst[a].pre;
            if(a != 0)
                cnt --,
                lst[lst[a].pre].nxt = lst[a].nxt,
                lst[lst[a].nxt].pre = lst[a].pre;
        }
    }
    cout << ans << endl; 

    return 0;
}