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

比赛链接

进度: 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. 带超链接的是找到了原题或原型↩︎