AtCoder Beginner Contest 257

给一个有/(n/)个节点/(m/)条边的无向图，边集中有一部分边只确定了一端，记这部分边的集合为/(S/)。

对于/(i = 1, 2, /dots, n/)，问当/(S/)中的边的不确定的那一端均为/(i/)时，从点/(1/)到点/(n/)的最短路长度。

其中，/(2 /le n /le 3 /times {10}^5, 1 /le m /le 3 /times {10}^5/)。

新增一个虚拟节点/(n + 1/)，将/(S/)中的边的不确定的那一段都看成是/(n + 1/)。

在询问/(i/)时，可以看成是在/(i/)和/(n + 1/)之间连一条长度为/(0/)的边。

此时的最短路，要么不包含/(S/)中的边，要么是/(1 /to n + 1 /to i /to n/)或/(1 /to i /to n + 1 /to n/)。

然后就是dijkstra板子了。

// Problem: F - Teleporter Setting
// Contest: AtCoder - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest
// 257）
// URL: https://atcoder.jp/contests/abc257/tasks/abc257_f
// Memory Limit: 1024 MB Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

template <typename DistanceType>
struct Edge {
  int v_;
  DistanceType w_;
  Edge() {}
  Edge(int v, DistanceType w) : v_(v), w_(w) {}
};

template <typename DistanceType>
std::vector<DistanceType> Dijkstra(const std::vector<std::vector<Edge<DistanceType>>>& g, int s) {
  using Node = std::pair<DistanceType, int>;
  const DistanceType INF = std::numeric_limits<DistanceType>::max();
  const int n = g.size();

  std::vector<DistanceType> dis(n, INF);
  std::vector<bool> vis(n, false);

  std::priority_queue<Node, std::vector<Node>, std::greater<Node>> q;
  dis[s] = 0;
  q.push(Node(dis[s], s));
  while (!q.empty()) {
    auto [c, u] = q.top();
    q.pop();

    if (vis[u])
      continue;
    vis[u] = true;

    for (auto [v, w] : g[u]) {
      if (dis[v] > c + w) {
        dis[v] = c + w;
        q.push(Node(dis[v], v));
      }
    }
  }
  return dis;
}

void solve_case(int Case) {
  int n, m;
  std::cin >> n >> m;

  std::vector<std::vector<Edge<int>>> g(n + 1);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    if (u == 0) {
      u = n + 1;
    }
    --u, --v;
    g[u].push_back(Edge(v, 1));
    g[v].push_back(Edge(u, 1));
  }

  std::vector<int> ds = Dijkstra(g, 0);
  std::vector<int> dt = Dijkstra(g, n - 1);
  const int INF = std::numeric_limits<int>::max();

  for (int i = 0; i < n; ++i) {
    int mi = ds[n - 1];
    if (ds[n] != INF && dt[i] != INF)
      mi = std::min(mi, ds[n] + dt[i]);
    if (ds[i] != INF && dt[n] != INF)
      mi = std::min(mi, ds[i] + dt[n]);

    if (mi == INF)
      mi = -1;
    std::cout << mi << " ";
  }
}

给两个字符串/(s/)和/(t/)，问最少用多个/(s/)的前缀能拼出/(t/)。

其中/(1 /le |s|, |t| /le 5 /times {10}^5/)。

记/(dp_i/)表示最少用多少个/(s/)的前缀能够拼出/(t/)长度为/(i/)的前缀。

然后猜了个结论，就是把令/(z = s + /# + t/)，然后跑kmp求出/(z/)每个位置的最长border长度记为数组/(p/)，则/(dp_i/)只从/(dp_{i – p_i}/)处转移即可。

// Problem: G - Prefix Concatenation
// Contest: AtCoder - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest
// 257）
// URL: https://atcoder.jp/contests/abc257/tasks/abc257_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

std::vector<int> kmp(const std::string& s) {
  int n = s.size();
  std::vector<int> p(n);

  p[0] = 0;
  for (int i = 1; i < n; ++i) {
    int j = p[i - 1];
    while (j > 0 && s[j] != s[i])
      j = p[j - 1];
    if (s[i] == s[j])
      ++j;
    p[i] = j;
  }

  return p;
}

void solve_case(int Case) {
  std::string s;
  std::string t;
  std::cin >> s;
  std::cin >> t;
  int n = s.size(), m = t.size();

  s = s + "#" + t;
  auto p = kmp(s);

  std::vector<int> dp(m + 1, 0x3f3f3f3f);
  dp[0] = 0;
  for (int i = 1; i <= m; ++i) {
    int l = p[n + i];
    dp[i] = std::min(dp[i], dp[i - l] + 1);
  }
  if (dp[m] == 0x3f3f3f3f)
    dp[m] = -1;
  std::cout << dp[m] << "/n";
}