[ABC136D] Gathering Children 题解

yanyan2 · 2024-08-23 19:13:55 · 题解

给一个比现在讨论区更简单的题解。

如果对于一段连续的 R，每个点都会一直往右走，走到第一个 L，然后进入来回跳动的模式。对于一段连续的 L 同理，一直往左走，走到第一个 R。

设第 i 个点走到 to_i 之后进入来回跳的模式，只需要对 |to_i - i| 进行一个奇偶的分类讨论即可。

对于求解 to_i，具体用双指针 O(N) 解决。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int inline read() {
    int num = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}
int n, to[N], ans[N];
char a[N];
int main() {
    scanf("%s", a + 1), n = strlen(a + 1);
    for(int i = 1, p; i <= n; i = p) {
        p = i;
        while(a[i] == a[p])p++;
        for(int j = i; j < p; j++) {
            if(a[i] == 'L')to[j] = i;
            else to[j] = p - 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        int dis = abs(to[i] - i);
        if(dis & 1)ans[to[i] + (a[i] == 'L' ? -1 : 1)]++;
        else ans[to[i]]++;
    }
    for(int i = 1; i <= n; i++)printf("%d ", ans[i]);
    return 0;
}