VP 记录 - 2021 ICPC 亚洲区域赛 (澳门)

发表于 2023-09-09 更新于 2023-12-05 分类于算法竞赛，题解， ICPC 合著者：Foi 本文字数： 477 阅读时长 ≈ 2 分钟

进度: 7 / 11

题目概览

题号 ¹	标题 ²	做法
A	So I'll Max Out My Constructive Algorithm Skills
*B	the Matching System
C	Laser Trap
*D	Shortest Path Fast Algorithm
E	Pass the Ball!
F	Sandpile on Clique
G	Cyclic Buffer
*H	Permutation on Tree
I	LCS Spanning Tree
*J	Colorful Tree
K	Link-Cut Tree

D 题的附带代码

Show code

spfa.cppview raw

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

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> e[MAXN];
int dis[MAXN], vis[MAXN];

void spfa(int n, int s) {
  for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0;

  priority_queue<pair<int, int>> pq;
  dis[s] = 0, vis[s] = 1;
  pq.push(make_pair(-dis[s], s));

  int cnt = 0;
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    vis[u] = 0, ++cnt;
    for (size_t i = 0; i < e[u].size(); i++) {
      int v = e[u][i].first, w = e[u][i].second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (vis[v] == 0) {
          pq.push({-dis[v], v});
          vis[v] = 1;
        }
      }
    }
  }
  printf("%d\n", cnt);
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    e[u].push_back(make_pair(v, w));
    e[v].push_back(make_pair(u, w));
  }
  spfa(n, 1);
  return 0;
}

官方题解

A - So I'll Max Out My Constructive Algorithm Skills

解题思路

复杂度

代码参考

Show code

A.cppview raw

#include <bits/stdc++.h>
using ll = long long;
template <class Tp>
using vc = std::vector<Tp>;
template <class Tp>
using vvc = std::vector<std::vector<Tp>>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define fors_(i, l, r, s, v...) \
  for (ll i = (l), i##e = (r), ##v; i <= i##e; i += s)
template <typename... Ts>
void dec(Ts &...x) {
  ((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
  ((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
  int n;
  cin >> n;
  vvc<int> mp(n, vc<int>(n));
  for (auto &i : mp)
    for (auto &j : i) cin >> j;
  fors_(i, 1, n - 1, 2) reverse(mp[i].begin(), mp[i].end());
  vc<int> seq;
  seq.reserve(n * n);
  for (auto &&i : mp)
    for (auto j : i) seq.push_back(j);
  int cnt = 0;
  for_(i, 1, n * n - 1) cnt += seq[i] > seq[i - 1];
  if (cnt > (n * n - 1) - cnt) reverse(seq.begin(), seq.end());
  for_(i, 0, n * n - 1) cout << seq[i] << " \n"[i == n * n - 1];
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

B - the Matching System

解题思路

复杂度

代码参考

Show code

C - Laser Trap

解题思路

复杂度

代码参考

Show code

C.cppview raw

#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
template <class Tp>
using vc = std::vector<Tp>;
template <typename... Ts>
void dec(Ts &...x) {
  ((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
  ((++x), ...);
}
using namespace std;
constexpr int sgn(i64 x) { return x < 0 ? -1 : x > 0 ? 1 : 0; }
struct Point {
  i64 x, y;
  explicit Point(i64 x = 0, i64 y = 0): x(x), y(y) {}
  constexpr static int QUAD__[9] = {5, 6, 7, 4, 0, 0, 3, 2, 1};
  int quad() const { return QUAD__[(sgn(y) + 1) * 3 + sgn(x) + 1]; }
  i64 operator^(const Point &r) const { return x * r.y - y * r.x; }
  bool operator<(const Point &r) const {
    return quad() == r.quad() ? (*this ^ r) > 0 : quad() < r.quad();
  }
};
void solve(int t_ = 0) {
  int n;
  cin >> n;
  vc<Point> ps(n);
  for (auto &[x, y] : ps) cin >> x >> y;
  if (n < 2) {
    cout << "0\n";
    return;
  }
  sort(ps.begin(), ps.end());
  int ans = n + 1;
  auto nxt = [n](int x) { return (++x) == n ? 0 : x; };
  for (int l = 0, r = 1, cntl = 0; l < n; ++l, --cntl) {
    i64 _;
    while (r != l && (_ = ps[l] ^ ps[r]) >= 0) {
      r = nxt(r);
      ++cntl;
    }
    if (l == r) {
      ans = 0;
      break;
    }
    ans = min(ans, cntl);
  }
  cout << ans << '\n';
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

D - Shortest Path Fast Algorithm

解题思路

复杂度

代码参考

Show code

E - Pass the Ball!

解题思路

复杂度

代码参考

Show code

E.cppview raw

#include <bits/stdc++.h>
#include <unordered_map>
using ll = long long;
using ull = unsigned long long;
using u64 = ull;
template <class Tp>
using vc = std::vector<Tp>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <typename... Ts>
void dec(Ts &...x) {
  ((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
  ((++x), ...);
}
using namespace std;
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}
int bsf(unsigned int n) { return __builtin_ctz(n); }
constexpr long long safe_mod(long long x, long long m) {
  x %= m;
  if (x < 0) x += m;
  return x;
}
struct barrett {
  unsigned int _m;
  unsigned long long im;
  barrett(unsigned int m): _m(m), im((unsigned long long)(-1) / m + 1) {}
  unsigned int umod() const { return _m; }
  unsigned int mul(unsigned int a, unsigned int b) const {
    unsigned long long z = a;
    z *= b;
    unsigned long long x =
      (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
    unsigned int v = (unsigned int)(z - x * _m);
    if (_m <= v) v += _m;
    return v;
  }
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
  if (m == 1) return 0;
  unsigned int _m = (unsigned int)(m);
  unsigned long long r = 1;
  unsigned long long y = safe_mod(x, m);
  while (n) {
    if (n & 1) r = (r * y) % _m;
    y = (y * y) % _m;
    n >>= 1;
  }
  return r;
}
constexpr bool is_prime_constexpr(int n) {
  if (n <= 1) return false;
  if (n == 2 || n == 7 || n == 61) return true;
  if (n % 2 == 0) return false;
  long long d = n - 1;
  while (d % 2 == 0) d /= 2;
  constexpr long long bases[3] = {2, 7, 61};
  for (long long a : bases) {
    long long t = d;
    long long y = pow_mod_constexpr(a, t, n);
    while (t != n - 1 && y != 1 && y != n - 1) {
      y = y * y % n;
      t <<= 1;
    }
    if (y != n - 1 && t % 2 == 0) { return false; }
  }
  return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
  a = safe_mod(a, b);
  if (a == 0) return {b, 0};
  long long s = b, t = a;
  long long m0 = 0, m1 = 1;
  while (t) {
    long long u = s / t;
    s -= t * u;
    m0 -= m1 * u;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if (m0 < 0) m0 += b / s;
  return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
  if (m == 2) return 1;
  if (m == 167772161) return 3;
  if (m == 469762049) return 3;
  if (m == 754974721) return 11;
  if (m == 998244353) return 3;
  int divs[20] = {};
  divs[0] = 2;
  int cnt = 1;
  int x = (m - 1) / 2;
  while (x % 2 == 0) x /= 2;
  for (int i = 3; (long long)(i)*i <= x; i += 2) {
    if (x % i == 0) {
      divs[cnt++] = i;
      while (x % i == 0) { x /= i; }
    }
  }
  if (x > 1) { divs[cnt++] = x; }
  for (int g = 2;; g++) {
    bool ok = true;
    for (int i = 0; i < cnt; i++) {
      if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
        ok = false;
        break;
      }
    }
    if (ok) return g;
  }
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
template <class T>
using is_signed_int128 =
  typename std::conditional<std::is_same<T, __int128_t>::value ||
                              std::is_same<T, __int128>::value,
                            std::true_type,
                            std::false_type>::type;
template <class T>
using is_unsigned_int128 =
  typename std::conditional<std::is_same<T, __uint128_t>::value ||
                              std::is_same<T, unsigned __int128>::value,
                            std::true_type,
                            std::false_type>::type;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                is_signed_int128<T>::value ||
                                                is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                  is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;
template <class T>
using is_unsigned_int =
  typename std::conditional<(is_integral<T>::value &&
                             std::is_unsigned<T>::value) ||
                              is_unsigned_int128<T>::value,
                            std::true_type,
                            std::false_type>::type;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
struct static_modint_base {};
}  // namespace internal
template <int m, std::enable_if_t<(1 <= m)> * = nullptr>
struct static_modint: internal::static_modint_base {
  using mint = static_modint;

public:
  static constexpr int mod() { return m; }
  static mint raw(int v) {
    mint x;
    x._v = v;
    return x;
  }
  static_modint(): _v(0) {}
  template <class T, internal::is_signed_int_t<T> * = nullptr>
  static_modint(T v) {
    long long x = (long long)(v % (long long)(umod()));
    if (x < 0) x += umod();
    _v = (unsigned int)(x);
  }
  template <class T, internal::is_unsigned_int_t<T> * = nullptr>
  static_modint(T v) {
    _v = (unsigned int)(v % umod());
  }
  unsigned int val() const { return _v; }
  mint &operator++() {
    _v++;
    if (_v == umod()) _v = 0;
    return *this;
  }
  mint &operator--() {
    if (_v == 0) _v = umod();
    _v--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint &operator+=(const mint &rhs) {
    _v += rhs._v;
    if (_v >= umod()) _v -= umod();
    return *this;
  }
  mint &operator-=(const mint &rhs) {
    _v -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  mint &operator*=(const mint &rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
  mint operator+() const { return *this; }
  mint operator-() const { return mint() - *this; }
  mint pow(long long n) const {
    assert(0 <= n);
    mint x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  mint inv() const {
    if (prime) {
      assert(_v);
      return pow(umod() - 2);
    } else {
      auto eg = internal::inv_gcd(_v, m);
      assert(eg.first == 1);
      return eg.second;
    }
  }
  friend mint operator+(const mint &lhs, const mint &rhs) {
    return mint(lhs) += rhs;
  }
  friend mint operator-(const mint &lhs, const mint &rhs) {
    return mint(lhs) -= rhs;
  }
  friend mint operator*(const mint &lhs, const mint &rhs) {
    return mint(lhs) *= rhs;
  }
  friend mint operator/(const mint &lhs, const mint &rhs) {
    return mint(lhs) /= rhs;
  }
  friend bool operator==(const mint &lhs, const mint &rhs) {
    return lhs._v == rhs._v;
  }
  friend bool operator!=(const mint &lhs, const mint &rhs) {
    return lhs._v != rhs._v;
  }

private:
  unsigned int _v;
  static constexpr unsigned int umod() { return m; }
  static constexpr bool prime = internal::is_prime<m>;
};
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class mint, internal::is_static_modint_t<mint> * = nullptr>
void butterfly(std::vector<mint> &a) {
  static constexpr int g = internal::primitive_root<mint::mod()>;
  int n = int(a.size());
  int h = internal::ceil_pow2(n);
  static bool first = true;
  static mint sum_e[30];
  if (first) {
    first = false;
    mint es[30], ies[30];
    int cnt2 = bsf(mint::mod() - 1);
    mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
    for (int i = cnt2; i >= 2; i--) {
      es[i - 2] = e;
      ies[i - 2] = ie;
      e *= e;
      ie *= ie;
    }
    mint now = 1;
    for (int i = 0; i <= cnt2 - 2; i++) {
      sum_e[i] = es[i] * now;
      now *= ies[i];
    }
  }
  for (int ph = 1; ph <= h; ph++) {
    int w = 1 << (ph - 1), p = 1 << (h - ph);
    mint now = 1;
    for (int s = 0; s < w; s++) {
      int offset = s << (h - ph + 1);
      for (int i = 0; i < p; i++) {
        auto l = a[i + offset];
        auto r = a[i + offset + p] * now;
        a[i + offset] = l + r;
        a[i + offset + p] = l - r;
      }
      now *= sum_e[bsf(~(unsigned int)(s))];
    }
  }
}
template <class mint, internal::is_static_modint_t<mint> * = nullptr>
void butterfly_inv(std::vector<mint> &a) {
  static constexpr int g = internal::primitive_root<mint::mod()>;
  int n = int(a.size());
  int h = internal::ceil_pow2(n);
  static bool first = true;
  static mint sum_ie[30];
  if (first) {
    first = false;
    mint es[30], ies[30];
    int cnt2 = bsf(mint::mod() - 1);
    mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
    for (int i = cnt2; i >= 2; i--) {
      es[i - 2] = e;
      ies[i - 2] = ie;
      e *= e;
      ie *= ie;
    }
    mint now = 1;
    for (int i = 0; i <= cnt2 - 2; i++) {
      sum_ie[i] = ies[i] * now;
      now *= es[i];
    }
  }
  for (int ph = h; ph >= 1; ph--) {
    int w = 1 << (ph - 1), p = 1 << (h - ph);
    mint inow = 1;
    for (int s = 0; s < w; s++) {
      int offset = s << (h - ph + 1);
      for (int i = 0; i < p; i++) {
        auto l = a[i + offset];
        auto r = a[i + offset + p];
        a[i + offset] = l + r;
        a[i + offset + p] =
          (unsigned long long)(mint::mod() + l.val() - r.val()) * inow.val();
      }
      inow *= sum_ie[bsf(~(unsigned int)(s))];
    }
  }
}
}  // namespace internal
template <class mint, internal::is_static_modint_t<mint> * = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
  int n = int(a.size()), m = int(b.size());
  if (!n || !m) return {};
  if (std::min(n, m) <= 60) {
    if (n < m) {
      std::swap(n, m);
      std::swap(a, b);
    }
    std::vector<mint> ans(n + m - 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) { ans[i + j] += a[i] * b[j]; }
    }
    return ans;
  }
  int z = 1 << internal::ceil_pow2(n + m - 1);
  a.resize(z);
  internal::butterfly(a);
  b.resize(z);
  internal::butterfly(b);
  for (int i = 0; i < z; i++) { a[i] *= b[i]; }
  internal::butterfly_inv(a);
  a.resize(n + m - 1);
  mint iz = mint(z).inv();
  for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
  return a;
}
template <unsigned int mod = 998244353,
          class T,
          std::enable_if_t<internal::is_integral<T>::value> * = nullptr>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b) {
  int n = int(a.size()), m = int(b.size());
  if (!n || !m) return {};
  using mint = static_modint<mod>;
  std::vector<mint> a2(n), b2(m);
  for (int i = 0; i < n; i++) { a2[i] = mint(a[i]); }
  for (int i = 0; i < m; i++) { b2[i] = mint(b[i]); }
  auto c2 = convolution(move(a2), move(b2));
  std::vector<T> c(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) { c[i] = c2[i].val(); }
  return c;
}
std::vector<long long> convolution_ll(const std::vector<long long> &a,
                                      const std::vector<long long> &b) {
  int n = int(a.size()), m = int(b.size());
  if (!n || !m) return {};
  static constexpr unsigned long long MOD1 = 754974721;
  static constexpr unsigned long long MOD2 = 167772161;
  static constexpr unsigned long long MOD3 = 469762049;
  static constexpr unsigned long long M2M3 = MOD2 * MOD3;
  static constexpr unsigned long long M1M3 = MOD1 * MOD3;
  static constexpr unsigned long long M1M2 = MOD1 * MOD2;
  static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
  static constexpr unsigned long long i1 =
    internal::inv_gcd(MOD2 * MOD3, MOD1).second;
  static constexpr unsigned long long i2 =
    internal::inv_gcd(MOD1 * MOD3, MOD2).second;
  static constexpr unsigned long long i3 =
    internal::inv_gcd(MOD1 * MOD2, MOD3).second;
  auto c1 = convolution<MOD1>(a, b);
  auto c2 = convolution<MOD2>(a, b);
  auto c3 = convolution<MOD3>(a, b);
  std::vector<long long> c(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    unsigned long long x = 0;
    x += (c1[i] * i1) % MOD1 * M2M3;
    x += (c2[i] * i2) % MOD2 * M1M3;
    x += (c3[i] * i3) % MOD3 * M1M2;
    long long diff =
      c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
    if (diff < 0) diff += MOD1;
    static constexpr unsigned long long offset[5] = {
      0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
    x -= offset[diff % 5];
    c[i] = x;
  }
  return c;
}
}  // namespace atcoder
using namespace atcoder;
void solve(int t_ = 0) {
  int n, q;
  cin >> n >> q;
  vc<int> p(n + 1);
  for_(i, 1, n) cin >> p[i];
  vc<bool> vis(n + 1);
  unordered_map<ll, vector<ll>> polys;
  for_(i, 1, n, j) {
    if (vis[j = i]) continue;
    vc<ll> pp;
    do {
      pp.push_back(j);
      vis[j] = 1;
    } while (!vis[j = p[j]]);
    vc<ll> p2 = pp;
    for (auto i : pp) p2.push_back(i);
    reverse(p2.begin(), p2.end());
    auto _ = convolution_ll(pp, p2);
    if (polys[pp.size()].empty()) polys[pp.size()] = _;
    else
      for_(i, 0, _.size() - 1) polys[pp.size()][i] += _[i];
  }
  for_(i, 1, q, k) {
    cin >> k;
    u64 ans = 0;
    for (auto &[key, poly] : polys) ans += poly[k % key + key - 1];
    cout << ans << '\n';
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  solve(i_);
  return 0;
}

F - Sandpile on Clique

解题思路

复杂度

代码参考

Show code

F.cppview raw

#include <bits/stdc++.h>
#include <queue>
#include <vector>
using ll = long long;
using pii = std::pair<int, int>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define Rep for_
template <typename... Ts>
void dec(Ts &...x) {
  ((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
  ((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  priority_queue<pair<int, int>> Q;
  Rep(i, 1, n) cin >> a[i], Q.emplace(a[i], i);
  bool flag = 1;
  int ret;
  Rep(i, 1, n) {
    int top = Q.top().first, id = Q.top().second;
    Q.pop();
    if (top + (i - 1) < n - 1) {
      Q.emplace(top, id);
      flag = 0;
      ret = i - 1;
      break;
    }
    top -= n;
    Q.emplace(top, id);
  }
  if (flag) cout << "Recurrent";
  else {
    vector<pair<int, int>> ans;
    while (!Q.empty()) ans.emplace_back(Q.top()), Q.pop();
    sort(
      ans.begin(), ans.end(), [](pii a, pii b) { return a.second < b.second; });
    cout << ans[0].first + ret;
    Rep(i, 1, ans.size() - 1) cout << ' ' << ans[i].first + ret;
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  solve(i_);
  return 0;
}

G - Cyclic Buffer

解题思路

复杂度

代码参考

Show code

G.cppview raw

#include <bits/stdc++.h>
#define Rep(i, a, b, vars...)                                               \
  for (std::make_signed_t<decltype(a + b)> i = (a), i##Limit = (b), ##vars; \
       i <= i##Limit;                                                       \
       ++i)
#define rep(i, a, b, vars...)                                               \
  for (std::make_signed_t<decltype(a + b)> i = (a), i##Limit = (b), ##vars; \
       i >= i##Limit;                                                       \
       --i)
using i32 = int;
using i64 = long long;
using namespace std;

constexpr i32 inf = INT32_MAX;
i32 n, k;
vector<i32> t;
void build(i32 x, i32 l, i32 r, vector<i32> const &a) {
  if (l == r) return void(t[x] = a[l > n ? l - n : l]);
  i32 mid = l + (r - l) / 2;
  build(x << 1, l, mid, a), build(x << 1 | 1, mid + 1, r, a);
  t[x] = min(t[x << 1], t[x << 1 | 1]);
}
void update(i32 x, i32 l, i32 r, i32 pos) {
  if (l == r) return void(t[x] = inf);
  i32 mid = l + (r - l) / 2;
  if (pos <= mid) update(x << 1, l, mid, pos);
  else update(x << 1 | 1, mid + 1, r, pos);
  t[x] = min(t[x << 1], t[x << 1 | 1]);
}
i32 query(i32 x, i32 l, i32 r, i32 L, i32 R) {
  if (L > R) return inf;
  if (L <= l && R >= r) return t[x];
  i32 mid = l + (r - l) / 2, ret = inf;
  if (L <= mid) ret = query(x << 1, l, mid, L, R);
  if (R > mid) ret = min(ret, query(x << 1 | 1, mid + 1, r, L, R));
  return ret;
}
i32 dis(i32 u, i32 v) {
  if (u > v) swap(u, v);
  return min(v - u, u + n - v);
}

void solve(int _t = 0) {
  cin >> n >> k;
  vector<i32> a(n + 1), p(n + 1);
  t = vector<i32>(n * 4 + 1, 0);
  for (int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i;
  build(1, 1, n, a);
  vector<vector<i64>> dp(n + 1, vector<i64>(2, 1000'000'000'000));
  i64 ans = 1000'000'000'000;
  i32 t = query(1, 1, n, k + 1, n);
  if (t == inf) {
    cout << "0\n";
    return;
  }
  dp[t][0] = dis(p[t], 1), dp[t][1] = dis(p[t], k);
  Rep(i, 1, n) {
    update(1, 1, n, p[i]);
    if (i < t) continue;
    // 1    p[i], p[i] + k - 1   n
    i32 nex0 = min(query(1, 1, n, max(1, p[i] + k - n), p[i] - 1),
                   query(1, 1, n, p[i] + k, n));
    if (nex0 == inf) ans = min(ans, dp[i][0]);
    else {
      dp[nex0][0] = min(dp[nex0][0], dp[i][0] + dis(p[i], p[nex0]));
      dp[nex0][1] = min(dp[nex0][1], dp[i][0] + dis(p[i] + k - 1, p[nex0]));
    }
    // 1    p[i] - k + 1, p[i]   n
    i32 nex1 = min(query(1, 1, n, 1, p[i] - k),
                   query(1, 1, n, p[i] + 1, min(n, p[i] + n - k)));
    if (nex1 == inf) ans = min(ans, dp[i][1]);
    else {
      dp[nex1][0] = min(dp[nex1][0], dp[i][1] + dis(p[i] - k + 1, p[nex1]));
      dp[nex1][1] = min(dp[nex1][1], dp[i][1] + dis(p[i], p[nex1]));
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  Rep(i, 1, t) solve(i);
  return 0;
}

H - Permutation on Tree

解题思路

复杂度

代码参考

Show code

I - LCS Spanning Tree

解题思路

复杂度

代码参考

Show code

I.cppview raw

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

vector<vector<u32>> pos(1);
template <u32 SZ = 26>
class ex_suffix_automaton {
  // super root is 0
  struct YYZ {
    u32 len, link;
    std::array<u32, SZ> nex{};
  };

public:
  u32 sz;
  vector<YYZ> st;
  ex_suffix_automaton(): sz(1), st(1) { st[0].len = 0, st[0].link = -1; }
  u32 extend(u32 last, char c) {
    if (st[last].nex[c]) {
      u32 p = last, q = st[p].nex[c];
      if (st[p].len + 1 == st[q].len) return q;
      else {
        u32 clone = sz++;
        st.push_back(YYZ()), pos.push_back(vector<u32>());
        st[clone].len = st[p].len + 1;
        st[clone].link = st[q].link;
        st[clone].nex = st[q].nex;
        while (p != -1u && st[p].nex[c] == q)
          st[p].nex[c] = clone, p = st[p].link;
        st[q].link = clone;
        return clone;
      }
    }
    u32 cur = sz++, p = last;
    st.push_back(YYZ()), pos.push_back(vector<u32>());
    st[cur].len = st[last].len + 1;
    while (p != -1u && !st[p].nex[c]) st[p].nex[c] = cur, p = st[p].link;
    if (p == -1u) st[cur].link = 0;
    else {
      u32 q = st[p].nex[c];
      if (st[p].len + 1 == st[q].len) st[cur].link = q;
      else {
        u32 clone = sz++;
        st.push_back(YYZ()), pos.push_back(vector<u32>());
        st[clone].len = st[p].len + 1;
        st[clone].link = st[q].link;
        st[clone].nex = st[q].nex;
        while (p != -1u && st[p].nex[c] == q)
          st[p].nex[c] = clone, p = st[p].link;
        st[q].link = st[cur].link = clone;
      }
    }
    return cur;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  u32 n;
  cin >> n;
  ex_suffix_automaton sam;
  string s;
  for (u32 i = 0, last = 0; i < n; ++i, last = 0) {
    cin >> s;
    for (auto c : s) last = sam.extend(last, c - 'a'), pos[last].push_back(i);
  }
  vector<vector<u32>> e(sam.sz);
  for (u32 i = 1; i < sam.sz; ++i) e[sam.st[i].link].push_back(i);
  vector<u32> a(sam.sz), root(sam.sz, -1u), fa(n, -1u);
  iota(a.begin(), a.end(), 0);
  sort(a.begin(), a.end(), [&](u32 a, u32 b) {
    return sam.st[a].len > sam.st[b].len;
  });
  u64 ans = 0;
  auto gf = [&](auto &&gf, u32 x) -> u32 {
    return fa[x] == -1u ? x : fa[x] = gf(gf, fa[x]);
  };
  auto merge = [&](u32 x, u32 y) {
    x = gf(gf, x), y = gf(gf, y);
    if (x == y) return 0;
    return fa[x] = y, 1;
  };
  for (u32 i = 0; i < sam.sz - 1; i++) {
    u32 root_ = -1u;
    for (auto v : pos[a[i]])
      if (root_ == -1u) root_ = v;
      else if (merge(root_, v)) ans += sam.st[a[i]].len;
    for (auto x : e[a[i]])
      if (root[x] != -1u) {
        if (root_ == -1u) root_ = root[x];
        else if (merge(root_, root[x])) ans += sam.st[a[i]].len;
      }
    root[a[i]] = root_;
  }
  cout << ans << '\n';
  return 0;
}

J - Colorful Tree

解题思路

复杂度

代码参考

Show code

K - Link-Cut Tree

解题思路

复杂度

代码参考

Show code

K.cppview raw

#include <bits/stdc++.h>
#include <vector>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define Rep for_
template <typename... Ts>
void dec(Ts &...x) {
  ((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
  ((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
  if (t_ > 0) cout << '\n';
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> E(n + 1);
  vector<int> Fa(n + 1);
  vector<int> in(n + 1);
  vector<bool> sign(m + 1);
  Rep(i, 1, n) Fa[i] = i;
  auto Add = [&](int u, int v, int w) {
    E[u].push_back(make_pair(v, w)), E[v].push_back(make_pair(u, w));
  };
  function<int(int)> GF = [&](int x) -> int {
    return x == Fa[x] ? x : Fa[x] = GF(Fa[x]);
  };
  auto merge = [&](int u, int v) {
    u = GF(u), v = GF(v);
    if (u != v) return Fa[u] = v, 1;
    return 0;
  };
  bool flag = 1;
  Rep(i, 1, m) {
    int u, v;
    cin >> u >> v;
    if (flag) {
      inc(in[u], in[v]);
      sign[i] = 1;
      Add(u, v, i);
      if (!merge(u, v)) flag = 0;
    }
  }
  if (flag) cout << "-1";
  else {
    queue<int> Q;
    Rep(i, 1, n) {
      if (in[i] == 1) Q.push(i);
    }
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto [v, w] : E[u])
        if (in[v]) {
          sign[w] = 0;
          dec(in[v], in[u]);
          if (in[v] == 1) Q.push(v);
        }
    }
    Rep(i, 1, n) {}
    vector<int> ans;
    Rep(i, 1, m)
      if (sign[i] == 1) ans.push_back(i);
    cout << ans[0];
    Rep(i, 1, ans.size() - 1) cout << ' ' << ans[i];
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

打 * 的是还没写题解的题↩︎
带超链接的是找到了原题或原型↩︎