题解：P12574 [UOI 2021] 机器人

· · 题解

这题居然没有题解，来交一发吧。

提示

  • 提示 1：当 t 足够大时，怎样的结构可以使机器人不会走出边界？
  • 提示 2：可以怎样编码这个字符串，使得可以快速找到每一块 L 或 R？
  • 答案 1：RL。
  • 答案 2：通过频数编码，例如 RRRLLRRRRR 编码为 (R, 3) (L, 2) (R, 5)。

    思路

    看到这题 t 的范围，蒟蒻先想到的是矩阵快速幂，但是 n 的范围又不行……然后我们发现机器人必然沿着“传送带”（一块 L 或者 R）走出边界或走入陷阱（RL）。所以我们首先将字符串频数处理，随后处理两头会导致机器人走出边界的传送带，最后处理通向陷阱（RL）的传送带，复杂度 O(n)。

    代码

// Problem: P12574 [UOI 2021] 机器人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P12574
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
int n;
long long t;
int ans[1000005];
char a[1000005];
struct Vec {
  char c;
  int cnt, st, ed;
};
vector<Vec> e;
// RRRRRRRRRRRRLLLLLLLLLLLLLLLL
//   9876543210123456789
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> t;
  char c = a[1];
  int cnt = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] == c) {
      cnt++;
      continue;
    }
    e.push_back((Vec){c, cnt, i - cnt, i - 1});
    c = a[i];
    cnt = 1;
  }
  e.push_back((Vec){c, cnt, n + 1 - cnt, n});
  // for (Vec v : e) cout << v.c << v.cnt << " " << v.st << " " << v.ed << endl;
  int st = 0, ed = e.size() - 1;
  if (e[0].c == 'L') {
    if (t < e[0].cnt)
      for (int i = t + 1; i <= e[0].cnt; i++) ans[i - t]++;
    st = 1;
  }
  if (e[ed].c == 'R') {
    if (t < e[ed].cnt)
      for (int i = n - e[ed].cnt + 1; i <= n - t; i++) ans[i + t]++;
    ed--;
  }
  for (int i = st; i <= ed; i += 2) {
    int pos = e[i].ed;
    for (int j = e[i].st; j <= e[i].ed; j++)
      if (t >= pos - j)
        ans[pos + (t - pos + j) % 2]++;
      else
        ans[j + t]++;
    for (int j = e[i + 1].st; j <= e[i + 1].ed; j++)
      if (t >= j - pos)
        ans[pos + (t - j + pos) % 2]++;
      else
        ans[j - t]++;
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}