VP 记录 - 2022 ICPC 亚洲区域赛 (杭州)

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

进度: 8 / 13

题目概览

题号 ¹	标题 ²	做法
A	Modulo Ruins the Legend	数论，exgcd
*B	Useful Algorithm	线段树 / 分块
C	No Bug No Game	DP
D	Money Game	简单结论
*E	Oscar is All You Need	BFS, (Splay)
F	Da Mi Lao Shi Ai Kan De	签到 (模拟)
G	Subgraph Isomorphism	树 Hash
*H	RPG Pro League	二分图，网络流，Hall 定理，拟阵
I	Guess Cycle Length	概率，BSGS
*J	Painting	二分，LCA
K	Master of Both	Trie
*L	Levenshtein Distance	后缀数组
M	Please Save Pigeland	DP, DFS

官方题解

A - Modulo Ruins the Legend

解题思路

复杂度

代码参考

Show code

A.cppview raw

#include <bits/stdc++.h>
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 <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}
using namespace std;
#define int long long
void exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
void solve(int t_ = 0) {
  int n, m, a, b, c = 0;
  cin >> n >> m;
  Rep(i, 0, n - 1) cin >> a, c += a;
  a = n, b = n * (n + 1) / 2;
  int g1 = gcd(a, b), g2 = gcd(g1, m), ans = c % g2;
  int x, y;
  exgcd(g1, m, x, y);
  int k = ((ans - c) / g2) % m * x % m;
  exgcd(a, b, x, y);
  cout << ans << '\n';
  cout << (x * k % m + m) % m << ' ' << (y * k % m + m) % m;
}
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;
}

B - Useful Algorithm

解题思路

复杂度

代码参考

Show code

C - No Bug No Game

解题思路

复杂度

代码参考

Show code

C.cppview raw

#include <bits/stdc++.h>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define rfor_(i, r, l, v...) for (ll i = (r), i##e = (l), ##v; i >= i##e; --i)
#define Rep for_
#define rep rfor_
template <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}
using namespace std;
void solve(int t_ = 0) {
  int n, k;
  cin >> n >> k;
  vector<int> p(n + 1);
  vector<vector<int>> w(n + 1, vector<int>(11));
  int s = 0, sp = 0;
  Rep(i, 1, n) {
    cin >> p[i];
    Rep(j, 1, p[i]) cin >> w[i][j];
    s += w[i][p[i]], sp += p[i];
  }
  if (sp <= k) {
    cout << s;
    return;
  }
  vector<vector<array<int, 2>>> Dp(
    n + 1, vector<array<int, 2>>(k + 1, array<int, 2>{-300000000, -300000000}));
  auto ckmax = [](int &a, int b) {
    if (b > a) a = b;
  };
  Rep(i, 0, n) Dp[i][0] = {0, 0};
  Rep(i, 1, n) {
    rep(j, k, 0) {
      Dp[i][j][0] = Dp[i - 1][j][0];
      Dp[i][j][1] = Dp[i - 1][j][1];
      if (j >= p[i])
        ckmax(Dp[i][j][0], Dp[i - 1][j - p[i]][0] + w[i][p[i]]),
          ckmax(Dp[i][j][1], Dp[i - 1][j - p[i]][1] + w[i][p[i]]);
      Rep(q, 1, p[i] - 1)
        if (j >= q) ckmax(Dp[i][j][1], Dp[i - 1][j - q][0] + w[i][q]);
    }
  }
  cout << max(Dp[n][k][0], Dp[n][k][1]);
}
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;
}

D - Money Game

解题思路

复杂度

代码参考

Show code

D.cppview raw

#include <bits/stdc++.h>
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 <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}
using namespace std;
void solve(int t_ = 0) {
  double S, ans;
  int n, a;
  cin >> n;
  Rep(i, 1, n) cin >> a, S += a;
  ans = S / (1.0 + n);
  cout << fixed << setprecision(8) << ans * 2;
  Rep(i, 2, n) cout << ' ' << fixed << setprecision(8) << ans;
}
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;
}

E - Oscar is All You Need

解题思路

复杂度

代码参考

Show code

F - Da Mi Lao Shi Ai Kan De

解题思路

复杂度

代码参考

Show code

F.cppview raw

#include <bits/stdc++.h>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}
using namespace std;
void solve(int t_ = 0) {
  int n;
  cin >> n;
  set<string> g0;
  for_(i, 1, n, m) {
    cin >> m;
    vector<string> picked;
    string s;
    for_(i, 1, m) {
      cin >> s;
      if (s.find("bie") != string::npos && !g0.count(s)) {
        g0.insert(s);
        picked.push_back(s);
      }
    }
    if (picked.empty()) {
      cout << "Time to play Genshin Impact, Teacher Rice!\n";
      continue;
    }
    for (auto &&i : picked) cout << i << '\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;
}

G - Subgraph Isomorphism

解题思路

复杂度

代码参考

Show code

G.cppview raw

#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;

#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)
#define rfor_(i, r, l, v...) for (ll i = (r), i##e = (l), ##v; i >= i##e; --i)
#define rfors_(i, r, l, s, v...) \
  for (ll i = (r), i##e = (l), ##v; i >= i##e; i -= s)
#define forit_(it, cont) \
  for (auto it = (cont).begin(); it != (cont).end(); ++it)
#define foritr_(it, cont, l, r) \
  for (auto it = (cont).begin() + l; it != (cont).begin() + r; ++it)
#define rforit_(it, cont) \
  for (auto it = (cont).rbegin(); it != (cont).rend(); ++it)
#define rforitr_(it, cont, l, r) \
  for (auto it = (cont).rbegin() + l; it != (cont).rbegin() + r; ++it)
#define Rep for_
#define rep rfor_
template <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}

template <class Tp>
inline void debug(Tp x) {
#ifdef LOCAL_
  std::cerr << x << std::endl;
#endif
}
template <class Tp, class... Ts>
inline void debug(Tp x, Ts... args) {
#ifdef LOCAL_
  std::cerr << x << ' ';
  debug(args...);
#endif
}
#define debug_line_ (std::cerr << __LINE__ << ' ' << __FUNCTION__ << std::endl)
#define debug_withname_(var) debug(#var, var)

using namespace std;

const int N = 100000 + 7;
bool Cut[N];
//! vertex ID start from 0
template <class Tp>
uint64_t rooted_tree_hash(std::vector<std::vector<Tp>> const &g,
                          size_t now = 0,
                          size_t fa = 0) {
  auto f = [](uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  };
  uint64_t ans = 1;
  for (auto to : g[now])
    if (to != fa && !Cut[to]) ans += f(rooted_tree_hash(g, to, now));
  return ans;
}

#define USE_CIN
#define MULTI_CASES
inline void solve(int t_ = 0) {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> E(n);
  Rep(i, 1, m) {
    int u, v;
    cin >> u >> v;
    dec(u), dec(v);
    E[u].push_back(v), E[v].push_back(u);
  }
  if (m == n - 1) {
  YES:
    cout << "YES\n";
    return;
  }
  if (m > n) {
  NO:
    cout << "NO\n";
    return;
  }
  vector<int> Fa(n), DFN(n), cy;
  vector<uint64_t> hash(n);
  int dfn = 0, flag = 0;
  function<void(int, int)> DFS = [&](int u, int fa) {
    Fa[u] = fa, DFN[u] = inc(dfn);
    for (auto v : E[u])
      if (v != fa) {
        if (DFN[v]) {
          Fa[v] = u, flag = 1, cy.push_back(u), Cut[u] = 1;
          return;
        }
        DFS(v, u);
        if (flag) return;
      }
    if (flag) return;
  };
  DFS(0, -1);
  int Now = Fa[cy[0]], cnt = 0;
  while (Now != cy[0]) {
    cy.push_back(Now), Cut[Now] = 1;
    Now = Fa[Now];
  }
  flag = 0;
  Rep(i, 0, cy.size() - 1) {
    hash[i] = rooted_tree_hash(E, cy[i], cy[i]);
    if (cy.size() & 1) {
      if (hash[i] != hash[0]) {
        flag = 1;
        break;
      }
    } else {
      if (hash[i] != hash[i % 2]) {
        flag = 1;
        break;
      }
    }
  }
  for (auto x : cy) Cut[x] = 0;
  if (flag) goto NO;
  else goto YES;
}

signed main() {
#ifdef LOCAL_
  auto CLOCK_ST_ = std::chrono::high_resolution_clock::now();
#endif
#ifdef USE_CIN
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
#endif
  int i_ = 0;
#ifdef MULTI_CASES
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_)
#endif
    debug("Case", i_), solve(i_);
#ifdef LOCAL_
  auto CLOCK_ED_ = std::chrono::high_resolution_clock::now();
  std::clog << "\n---\nTime used: "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(CLOCK_ED_ -
                                                                    CLOCK_ST_)
                   .count() *
                 1e-6l
            << " ms" << std::endl;
#endif
  return 0;
}

H - RPG Pro League

解题思路

复杂度

代码参考

Show code

I - Guess Cycle Length

解题思路

复杂度

代码参考

Show code

I.cppview raw

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

int main() {
  mt19937 rad(time(0));
  int m = 0;
  auto walk = [](int x) {
    cout << "walk " << x << '\n';
    cout.flush();
    int ret = 0;
    cin >> ret;
    return ret;
  };
  int k = 3333;
  for (int i = 1; i <= k; i++) m = max(m, walk(rad() % 1000000000));
  unordered_map<int, int> a;
  auto guess = [](int x) {
    cout << "guess " << x << '\n';
    exit(0);
  };
  for (int i = 1; i < k; i++) {
    int x = walk(1);
    if (a[x]) guess(i - 1);
    a[x] = i;
  }
  int x = walk(m), step = k - 1 + m;
  if (a[x]) guess(step - a[x]);
  for (int i = 1; i <= k; i++) {
    x = walk(k - 1), step += k - 1;
    if (a[x]) guess(step - a[x]);
  }
  return 0;
}

J - Painting

解题思路

复杂度

代码参考

Show code

K - Master of Both

解题思路

复杂度

代码参考

Show code

K.cppview raw

#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
template <class Tp>
Tp dec(Tp &i) {
  return --i;
}
template <class Tp>
Tp inc(Tp &i) {
  return ++i;
}
using namespace std;
const int N = 1000010;
int n, Q, cnt, ch[N][27], sz[N], num[N];
i64 sum = 0;
i64 ss[27][27];
void ins(int p, string s) {
  for (int i = 0; i < s.length(); ++i) {
    for (int j = 0; j < 26; ++j) {
      if (j != s[i] - 'a') { ss[j][s[i] - 'a'] += sz[ch[p][j]]; }
    }
    if (ch[p][s[i] - 'a']) {
      p = ch[p][s[i] - 'a'];
    } else {
      ch[p][s[i] - 'a'] = ++cnt;
      p = cnt;
    }
    sz[p]++;
  }
  num[p]++;
  sum += sz[p] - num[p];
}
void solve(int t_ = 0) {
  cin >> n >> Q;
  int root = 0;
  for (int i = 1; i <= n; ++i) {
    string S;
    cin >> S;
    ins(root, S);
  }
  for (int i = 1; i <= Q; ++i) {
    string S;
    cin >> S;
    i64 ans = sum;
    for (int j = 0; j < 26; ++j) {
      for (int k = j + 1; k < 26; ++k) { ans += ss[S[k] - 'a'][S[j] - 'a']; }
    }
    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;
}

L - Levenshtein Distance

解题思路

复杂度

代码参考

Show code

M - Please Save Pigeland

解题思路

复杂度

代码参考

Show code

M.cppview raw

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

int n, k;
i64 ans;
struct tree {
  int tot;
  vector<vector<pair<int, int>>> e;
  vector<i64> s, d;
  vector<int> dfn, cnt, de, sz, node;
  tree(int n)
    : tot(0), e(n), s(n), d(n), dfn(n), cnt(n), de(n), sz(n), node(n) {}
  void add(int u, int v, int w) {
    e[u].emplace_back(v, w), e[v].emplace_back(u, w);
  }
  void dfs1(int u, int fa) {
    dfn[u] = tot++, node[dfn[u]] = u, cnt[u] = de[u], sz[u] = 1;
    for (auto [v, w] : e[u])
      if (v != fa) {
        d[v] = d[u] + w;
        dfs1(v, u);
        cnt[u] += cnt[v];
        s[u] += s[v] + 1ll * cnt[v] * w;
        sz[u] += sz[v];
      }
  }
  void dfs2(int u, int fa, i64 dis_) {
    for (auto [v, w] : e[u])
      if (v != fa) {
        dfs2(
          v, u, dis_ + s[u] - s[v] - 1ll * cnt[v] * w + 1ll * (k - cnt[v]) * w);
      }
    s[u] += dis_;
  }
};
struct segment {
  vector<i64> t;
  segment(int n): t(n * 4) {}
  void build(int x, int l, int r, vector<i64> const &a) {
    if (l == r) {
      t[x] = a[l];
      return;
    }
    int mid = l + (r - l) / 2;
    build(x << 1, l, mid, a), build(x << 1 | 1, mid + 1, r, a);
    t[x] = gcd(t[x << 1], t[x << 1 | 1]);
  }
  void update(int x, int l, int r, int pos, i64 k) {
    if (l == r) {
      t[x] += k;
      return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid) update(x << 1, l, mid, pos, k);
    else update(x << 1 | 1, mid + 1, r, pos, k);
    t[x] = gcd(t[x << 1], t[x << 1 | 1]);
  }
};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  vector<int> c(k), dfnc(k);
  tree tr(n);
  for (auto &x : c) cin >> x, --x, tr.de[x] = 1;
  Rep(i, 1, n - 1) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    tr.add(u, v, w);
  }
  tr.dfs1(0, 0), tr.dfs2(0, 0, 0);
  sort(c.begin(), c.end(), [&](int a, int b) { return tr.dfn[a] < tr.dfn[b]; });
  vector<i64> a(k);
  for (int i = 0; i < k; ++i) a[i] = tr.d[c[i]], dfnc[i] = tr.dfn[c[i]];
  for (int i = k - 1; i; --i) a[i] = a[i] - a[i - 1];
  segment seg(k);
  seg.build(1, 0, k - 1, a);
  ans = INT64_MAX;
  dfnc.push_back(INT32_MAX);
  auto dfs = [&](auto &&dfs, int u, int fa) -> void {
    if (seg.t[1]) ans = min(ans, abs(tr.s[u] / seg.t[1]));
    else ans = 0;
    for (auto [v, w] : tr.e[u])
      if (v != fa) {
        int a;
        // dfn[v] .. dfn[v] + sz[v] - 1
        if (tr.dfn[v] <= dfnc[0] && dfnc[0] <= tr.dfn[v] + tr.sz[v] - 1)
          seg.update(1, 0, k - 1, 0, -w);
        else {
          seg.update(1, 0, k - 1, 0, w);
          a = lower_bound(dfnc.begin(), dfnc.end(), tr.dfn[v]) - dfnc.begin();
          if (a < k) seg.update(1, 0, k - 1, a, -2 * w);
        }
        a = upper_bound(dfnc.begin(), dfnc.end(), tr.dfn[v] + tr.sz[v] - 1) -
            dfnc.begin();
        if (a < k) seg.update(1, 0, k - 1, a, 2 * w);

        dfs(dfs, v, u);

        if (tr.dfn[v] <= dfnc[0] && dfnc[0] <= tr.dfn[v] + tr.sz[v] - 1)
          seg.update(1, 0, k - 1, 0, w);
        else {
          seg.update(1, 0, k - 1, 0, -w);
          a = lower_bound(dfnc.begin(), dfnc.end(), tr.dfn[v]) - dfnc.begin();
          if (a < k) seg.update(1, 0, k - 1, a, 2 * w);
        }
        a = upper_bound(dfnc.begin(), dfnc.end(), tr.dfn[v] + tr.sz[v] - 1) -
            dfnc.begin();
        if (a < k) seg.update(1, 0, k - 1, a, -2 * w);
      }
  };
  dfs(dfs, 0, 0);
  cout << ans * 2;
  return 0;
}

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