VP 记录 - 2023 ICPC 亚洲区域赛 (网络预选赛 Ⅰ)

发表于 更新于 分类于 ， ， 合著者：Foi 本文字数： 514 阅读时长 ≈ 2 分钟

比赛链接

进度: 5 / 11

题目概览

题号 1标题 2做法
AQualifiers Ranking Rules签到
*BString自动机，线段树合并
*CMultiply Then Plus线段树，凸壳二分
DTransitivityDFS
*EMagical Pair数论 (CRT, Pollard-Rho)
*FAlice and Bob博弈论
GSpanning Tree并查集
*HRange Periodicity Query线段树
IPa?sWorDDP, 滚动数组
JMinimum Manhattan Distance计算几何
KMinimum Euclidean Distance计算几何 (凸包), 积分
LKaChang!签到

官方题解

https://zhuanlan.zhihu.com/p/656872940

A - Qualifiers Ranking Rules

解题思路

复杂度

代码参考

Show code

A.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)

void solve() {
  int n, m;
  cin >> n >> m;
  map<string, bool> M;
  vector<string> Q1, Q2, Q3;
  Rep(i, 1, n) {
    string S;
    cin >> S;
    if (M.find(S) == M.end()) Q1.push_back(S), M[S] = 1;
  }
  M.clear();
  Rep(i, 1, m) {
    string S;
    cin >> S;
    if (M.find(S) == M.end()) Q2.push_back(S), M[S] = 1;
  }
  M.clear();
  int a = 0, b = 0;
  while (a != Q1.size() || b != Q2.size()) {
    if (a != Q1.size()) {
      if (M.find(Q1[a]) == M.end()) Q3.push_back(Q1[a]), M[Q1[a]] = 1;
      ++a;
    }
    if (b != Q2.size()) {
      if (M.find(Q2[b]) == M.end()) Q3.push_back(Q2[b]), M[Q2[b]] = 1;
      ++b;
    }
  }
  for (auto x : Q3) cout << x << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

B - String

解题思路

复杂度

代码参考

Show code

C - Multiply Then Plus

解题思路

复杂度

代码参考

Show code

D - Transitivity

解题思路

复杂度

代码参考

Show code

D.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)
#define inc(i) (++(i))

void solve() {
  int n, m, sz = 0;
  cin >> n >> m;
  vector<vector<int>> E(n + 1);
  vector<int> col(n + 1, 0);
  vector<int> a;
  vector<int> sz1, sz2;
  for_(i, 1, m) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  function<void(int)> dfs = [&](int u) {
    a.push_back(u), col[u] = sz, inc(sz1[sz]);
    for (auto v : E[u])
      if (!col[v]) dfs(v);
  };
  auto C = [](int n) -> ll { return 1ll * n * (n - 1) / 2; };
  sz1.push_back(0), sz2.push_back(0);
  Rep(i, 1, n)
    if (!col[i]) {
      a.clear(), inc(sz), sz1.push_back(0), sz2.push_back(0);
      dfs((int)i);
      for (auto x : a) sz2[sz] += E[x].size();
      sz2[sz] /= 2;
    }
  int flag = 1;
  ll ans = 0;
  int min1 = n, min2 = n;
  Rep(i, 1, sz) {
    if (C(sz1[i]) != sz2[i]) flag = 0, ans += C(sz1[i]) - sz2[i];
    else if (sz1[i] < min1) min2 = min1, min1 = sz1[i];
    else if (sz1[i] < min2) min2 = sz1[i];
  }
  if (flag) {
    cout << C(min2 + min1) - C(min1) - C(min2);
  } else cout << ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

E - Magical Pair

解题思路

复杂度

代码参考

Show code

F - Alice and Bob

解题思路

复杂度

代码参考

Show code

G - Spanning Tree

解题思路

复杂度

代码参考

Show code

G.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)
#define pii pair<int, int>

void solve() {
  int n;
  const int mod = 998244353;
  auto KSM = [&](int x, int p) {
    int ret = 1;
    while (p) {
      if (p & 1) ret = 1ll * ret * x % mod;
      x = 1ll * x * x % mod, p >>= 1;
    }
    return ret;
  };
  cin >> n;
  vector<pii> e(n);
  vector<int> fa(n + 1), dep(n + 1), f(n + 1), sz(n + 1, 1);
  vector<vector<int>> E(n + 1);
  iota(fa.begin(), fa.end(), 0);
  function<int(int)> GF = [&](int x) {
    return x == fa[x] ? x : fa[x] = GF(fa[x]);
  };
  Rep(i, 1, n - 1) cin >> e[i].first >> e[i].second;
  Rep(i, 1, n - 1) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v), E[v].push_back(u);
  }
  function<void(int, int)> DFS = [&](int u, int fa) {
    f[u] = fa, dep[u] = dep[fa] + 1;
    for (auto v : E[u])
      if (v != fa) DFS(v, u);
  };
  DFS(1, 0);
  int ans = 1;
  Rep(i, 1, n - 1) {
    int u = e[i].first, v = e[i].second;
    int fu = GF(u), fv = GF(v);
    if (dep[fu] > dep[fv]) swap(u, v), swap(fu, fv);
    if (GF(f[fv]) != fu) {
      cout << 0;
      return;
    }
    ans = 1ll * ans * sz[fu] % mod * sz[fv] % mod;
    sz[fu] += sz[fv];
    fa[fv] = fu;
  }
  cout << KSM(ans, mod - 2);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

H - Range Periodicity Query

解题思路

复杂度

代码参考

Show code

I - Pa?sWorD

解题思路

复杂度

代码参考

Show code

I.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)
#define inc(i) (++(i))
constexpr i64 MOD = 998244353;

void solve() {
  int n;
  string str;
  cin >> n >> str;
  i64 f[2][62][2][2][2];
  memset(f, 0, sizeof(f));
  i64 sum[2][2][2];
  memset(sum, 0, sizeof(sum));
  sum[0][0][0] = 1;
  int now = 0;
  for (int i = 0; i < n; ++i) {
    int lst = now;
    now ^= 1;
    memset(f[now], 0, sizeof(f[now]));
    if ('A' <= str[i] && str[i] <= 'Z') {
      int cur = str[i] - 'A' + 36;
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          f[now][cur][1][j][k] =
            ((sum[1][j][k] - f[lst][cur][1][j][k] + sum[0][j][k]) % MOD + MOD) %
            MOD;
        }
      }
    } else if ('0' <= str[i] && str[i] <= '9') {
      int cur = str[i] - '0';
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          f[now][cur][j][k][1] =
            ((sum[j][k][1] - f[lst][cur][j][k][1] + sum[j][k][0]) % MOD + MOD) %
            MOD;
        }
      }
    } else if ('a' <= str[i] && str[i] <= 'z') {
      int cur = str[i] - 'a' + 36;
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          f[now][cur][1][j][k] =
            ((sum[1][j][k] - f[lst][cur][1][j][k] + sum[0][j][k]) % MOD + MOD) %
            MOD;
        }
      }
      cur = str[i] - 'a' + 10;
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          f[now][cur][j][1][k] =
            ((sum[j][1][k] - f[lst][cur][j][1][k] + sum[j][0][k]) % MOD + MOD) %
            MOD;
        }
      }
    } else {
      for (int cur = 0; cur < 10; ++cur) {
        for (int j = 0; j < 2; ++j) {
          for (int k = 0; k < 2; ++k) {
            f[now][cur][j][k][1] =
              ((sum[j][k][1] - f[lst][cur][j][k][1] + sum[j][k][0]) % MOD +
               MOD) %
              MOD;
          }
        }
      }
      for (int cur = 10; cur < 36; ++cur) {
        for (int j = 0; j < 2; ++j) {
          for (int k = 0; k < 2; ++k) {
            f[now][cur][j][1][k] =
              ((sum[j][1][k] - f[lst][cur][j][1][k] + sum[j][0][k]) % MOD +
               MOD) %
              MOD;
          }
        }
      }
      for (int cur = 36; cur < 62; ++cur) {
        for (int j = 0; j < 2; ++j) {
          for (int k = 0; k < 2; ++k) {
            f[now][cur][1][j][k] =
              ((sum[1][j][k] - f[lst][cur][1][j][k] + sum[0][j][k]) % MOD +
               MOD) %
              MOD;
          }
        }
      }
    }
    memset(sum, 0, sizeof(sum));
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        for (int t = 0; t < 2; ++t) {
          for (int cur = 0; cur < 62; ++cur)
            sum[j][k][t] = (sum[j][k][t] + f[now][cur][j][k][t]) % MOD;
        }
      }
    }
  }
  cout << sum[1][1][1] << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

J - Minimum Manhattan Distance

解题思路

复杂度

代码参考

Show code

J.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)

#define MULCAS
void solve() {
  ll x11, y11, x12, y12, x21, y21, x22, y22;
  cin >> x11 >> y11 >> x12 >> y12 >> x21 >> y21 >> x22 >> y22;
  long double s =
    fabsl((x21 + x22) - (x11 + x12)) / 2 + fabsl((y21 + y22) - (y11 + y12)) / 2;
  long double r =
    sqrtl((x21 - x22) * (x21 - x22) + (y21 - y22) * (y21 - y22)) * sqrtl(2) / 2;
  cout << min(abs(s + r), abs(s - r)) << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

K - Minimum Euclidean Distance

解题思路

复杂度

代码参考

Show code

K.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = ll;
using ull = unsigned long long;
using u64 = ull;
using ldb = long double;

#define for_(i, l, r) for (ll i = (l), i##ed__ = (r); i <= i##ed__; ++i)
#define Rep(i, l, r) for_(i, l, r)

constexpr ldb eps = 1e-6;

struct P {
  ldb x, y;

  explicit P(ldb x = 0, ldb y = 0): x(x), y(y) {}

  bool operator==(const P &r) const {
    return abs(x - r.x) < eps && abs(y - r.y) < eps;
  }
  P operator-(const P &r) const { return P{x - r.x, y - r.y}; }
  P operator*(ldb d) const { return P{x * d, y * d}; }
  ldb dist2() const { return x * x + y * y; }
  ldb dot(const P &r) const { return x * r.x + y * r.y; }
  ldb cross(const P &r) const { return x * r.y - y * r.x; }
  ldb cross(const P &a, const P &b) const {
    return (a - *this).cross(b - *this);
  }
};

ldb segdist2(P const &s, P const &e, P const &p) {
  if (s == e) return (p - s).dist2();
  ldb d = (e - s).dist2(), t = min(d, max(0.l, (p - s).dot(e - s)));
  return ((p - s) * d - (e - s) * t).dist2() * 1.l / d / d;
}

bool on_seg(P const &s, P const &e, P const &p) {
  return segdist2(s, e, p) < eps;
}

int nxt(int x, int n) { return (++x) == n ? 0 : x; };
bool in_poly(vector<P> const &p, P const &a) {
  int cnt = 0, n = p.size();
  for_(i, 0, n - 1) {
    P const &q = p[nxt(i, n)];
    if (on_seg(p[i], q, a)) return true;
    cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
  }
  return cnt;
}

void solve() {
  int n, q;
  cin >> n >> q;

  vector<P> poly(n);
  for (auto &[x, y] : poly) cin >> x >> y;

  for_(i, 1, q) {
    P p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    P c{(p1.x + p2.x) / 2, (p1.y + p2.y) / 2};
    ldb r2 = (p1 - p2).dist2() / 4;
    if (in_poly(poly, c)) {
      cout << r2 / 2 << '\n';
      continue;
    }
    ldb d = 1e4514l;
    for_(i, 0, n - 1) d = min(d, segdist2(poly[i], poly[nxt(i, n)], c));
    cout << d + r2 / 2 << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
#ifdef MULCAS
  int t = 0;
  cin >> t;
  for (int i = 0; i < t; ++i)
#endif
    solve();
  return 0;
}

L - KaChang!

解题思路

复杂度

代码参考

Show code

L.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  int mx = 0;
  for (int i = 0, x; i < n; ++i) {
    cin >> x;
    mx = max(mx, x);
  }
  cout << max(2, (mx + m - 1) / m) << '\n';
}

  1. 打 * 的是还没写题解的题↩︎

  2. 带超链接的是找到了原题或原型↩︎