C. 前缀

题目描述

给定一个字符串 \(S\)，你会将这个字符串无限循环，即变成 \(S+S+S+S+\dots\)。

接着给定一个字符串 \(T\)，你要求最短的一个 \(S\) 的前缀使得其中存在一个子序列 \(T\)，若 \(T_i=*\)，则这一位是什么都可以。但由于 \(T\) 太长了，所以其中有一些字符后会有数字，表示这个字符重复了这么多次。

思路

我们对每个字符记录其出现位置，然后找循环节即可。

空间复杂度 \(O(|S|+|\sum|)\)，时间复杂度 \(O(Q+(\sum|T|)\log |S|)\)。

代码

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

const int MOD = 998244353;

int q;
string s;
vector<int> ve[27];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> s >> q;
  for(int i = 0; i < int(s.size()); ++i) {
    ve[s[i] - 'a'].emplace_back(i);
    ve[26].emplace_back(i);
  }
  for(; q--; ) {
    string t;
    cin >> t;
    int pos = -1, ans = 0;
    bool op = 0;
    for(int i = 0; i < int(t.size()); ) {
      int c = (t[i] == '*' ? 26 : t[i] - 'a');
      if(ve[c].empty()) {
        op = 1;
        break;
      }
      int l = i, m = 0, res = 0;
      for(i++; i < int(t.size()) && t[i] >= '0' && t[i] <= '9'; ++i) {
        res = (10ll * res % MOD + (m * 10 + t[i] - '0') / int(ve[c].size())) % MOD;
        m = (m * 10 + t[i] - '0') % int(ve[c].size());
      }
      ans = (ans + res) % MOD;
      if(l + 1 == i) {
        m = 1;
      }
      int x = upper_bound(ve[c].begin(), ve[c].end(), pos) - ve[c].begin();
      if(int(ve[c].size()) - x >= m) {
        pos = ve[c][(x + m + ve[c].size() - 1) % int(ve[c].size())];
        if(!x && !m) {
          ans = (ans - 1 + MOD) % MOD;
        }
        continue;
      }
      m -= ve[c].size() - x;
      ans = (ans + 1) % MOD;
      pos = ve[c][m - 1];
    }
    cout << (op ? -1 : (1ll * ans * int(s.size()) % MOD + pos + 1) % MOD) << "\n";
  }
  return 0;
}

D. 移动

题目描述

有 \(N\) 个闸门，其中有 \(M\) 个事件，每个事件为：在时间 \([l,r]\) 中闸门 \(x\) 关闭。保证每一个闸门的事件时间不会有交集。

牛牛一开始在闸门 \(0\)，时刻为 \(0\)。每秒钟他可以走到左/右边的闸门或原地不动。当闸门关闭时如果牛牛还在下面那么牛牛就会变成牛排。求在不变成牛排的情况下最少要到什么时候才能到达闸门 \(N+1\)。

思路

我们可以对每个闸门处理出其没有关闭的时间段。由于一开始有 \(N+2\) 个闸门，也就是 \(N+2\) 个时间段，每多一个事件就会多一个时间段，所以总共 \(O(N+M)\) 个时间段。

我们可以在这些时间段之间连边，而边的数量可以通过感性理解发现也是 \(O(N+M)\) 的。

接着在这个图上跑最短路即可。

空间复杂度 \(O(N+M)\)，时间复杂度 \(O((N+M)\log (N+M))\)。

代码

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MAXN = 100005, MAXM = MAXN, INF = int(2e9) + 10;

struct Node {
  int u, dis;
};

struct cmp {
  bool operator()(const Node &a, const Node &b) const {
    return a.dis > b.dis;
  }
};

int n, m, l[MAXN + MAXM], r[MAXN + MAXM], tot, dist[MAXN + MAXM];
bool vis[MAXN + MAXM];
vector<int> ve[MAXN], L[MAXN], R[MAXN], id[MAXN];
vector<pii> e[MAXN + MAXM];

void add(int x, int y) {
  for(int i = 0; i < int(L[x].size()); ++i) {
    int j = lower_bound(R[y].begin(), R[y].end(), L[x][i] - 1) - R[y].begin();
    for(; j < int(R[y].size()) && L[y][j] <= R[x][i] + 1; ++j) {
      e[id[x][i]].emplace_back(id[y][j], max(L[x][i] + 1, L[y][j]));
    }
  }
}

void dij() {
  fill(dist + 1, dist + tot + 1, INF);
  priority_queue<Node, vector<Node>, cmp> pq;
  pq.push({1, 0});
  dist[1] = 0;
  for(; !pq.empty(); ) {
    auto [u, dis] = pq.top();
    pq.pop();
    if(vis[u]) {
      continue;
    }
    vis[u] = 1;
    for(auto [v, w] : e[u]) {
      if(max(dis + 1, w) <= r[v] && max(dis + 1, w) < dist[v]) {
        dist[v] = max(dis + 1, w);
        pq.push({v, max(dis + 1, w)});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  freopen("move.in", "r", stdin);
  freopen("move.out", "w", stdout);
  cin >> n >> m;
  for(int i = 0; i <= n + 1; ++i) {
    ve[i].emplace_back(-1);
    ve[i].emplace_back(INF);
  }
  for(int i = 1, x, l, r; i <= m; ++i) {
    cin >> x >> l >> r;
    ve[x].emplace_back(l);
    ve[x].emplace_back(r);
  }
  for(int i = 0; i <= n + 1; ++i) {
    sort(ve[i].begin(), ve[i].end());
    for(int j = 0; j < int(ve[i].size()); j += 2) {
      ve[i][j]++, ve[i][j + 1]--;
      if(ve[i][j] > ve[i][j + 1]) {
        continue;
      }
      L[i].emplace_back(ve[i][j]);
      R[i].emplace_back(ve[i][j + 1]);
      id[i].emplace_back(++tot);
      l[tot] = ve[i][j], r[tot] = ve[i][j + 1];
    }
  }
  for(int i = 0; i <= n + 1; ++i) {
    if(i) {
      add(i, i - 1);
    }
    if(i <= n) {
      add(i, i + 1);
    }
  }
  dij();
  cout << dist[tot];
  return 0;
}