卜算子·唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉唉唉
唉唉唉唉唉
D - 2025
Description
判断 $y$ 是否是完全平方数，且 $y$ 各位数字之和是否是完全平方数。
Solution
首先开场就注意到了一道很签的 D 题。然后队友一发过了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
string s;
cin >> s;
i64 s1 = 0, s2 = 0;
for (auto ch : s) {
s1 += ch - '0';
s2 = s2 * 10 + ch - '0';
}
auto check = [](i64 x) {
int sx = sqrt(x);
return sx * sx == x;
};
if (check(s1) and check(s2))
cout << "Yes\n";
else
cout << "No\n";
|
题外话：听说 louisdlee 开这题的时候 WA 了一发。
J - Ring Trick
Description
给出一个字符串，判断其凯撒移位后串中最多能有多少个「洞」。
Solution
纯模拟，队友开完 D 我就上去写了。
1
2
3
4
5
6
7
8
9
10
11
12
|
int holes_cnt[26] = {1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < 26; i++) {
int cur = 0;
for (auto ch : s) {
cur += holes_cnt[(ch - 'A' + i) % 26];
}
ans = max(ans, cur);
}
cout << ans << "\n";
|
M - 川陀航空学院
Description
给出 $n$ 个节点和 $m$ 条无向边，求需要多少次添加或删除边使得这 $n$ 个节点能构成一颗无向树。
Solution
使用 Kruskal 算法求最小生成树，并记录每棵树，所含的节点个数 $cnt_i$，和树的个数 $size$。答案就是：
$$
size-1+m-\sum_{i=1}^{size}cnt_i-1
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int n, m;
cin >> n >> m;
DSU dsu(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
dsu.merge(u, v);
}
set<int> st;
i64 ans = 0;
for (int i = 0; i < n; i++) {
st.insert(dsu.find(i));
}
for (auto x : st) {
ans += dsu.siz[x] - 1;
}
cout << st.size() + m - ans - 1 << "\n";
|
H - 树论函数
Description
有无穷个孤立的节点，每个节点编号为 $i(i\ge 1)$
定义函数 $f(n)=n \cdot (n+1)$，若 $f(n)=f(a)\cdot f(b)$，则由节点 $n$ 出发，分别向节点 $a,b$ 连接一条无向边。
求从节点 $s$ 出发，在 $[l,r]$ 中有多少节点可达。
Solution
这道题是我做的……
首先注意到 $1 \le s, l, r \le 10^9$，因此必然存在某种规律使得我们可以 $O(1)$ 地解决此问题。
然后打表找规律，使用 Python 程序：
1
2
3
4
5
6
7
8
|
f = [0]
for i in range(1, 10000):
f.append(i * (i + 1))
for a in range(1, 100):
for b in range(a, 100):
for n in range(b, 100):
if f[a] * f[b] == f[n]:
print(a, b, n)
|
使用 Python 的好处是可以直接在 Vim 里面输入 !python3 % 来运行……
然后发现对于每一个 $i$ 都与 $i+1$ 联通，因此可以得出每一个点都可达。
答案就是 $r-l+1$
代码略
Proof of $\ \ \forall a, b\ (1 \le a,\ b = a+1),\ \exists n \ [f(n) = f(a)\cdot f(b)] $:
Let $f(x) = x(x+1)$, and suppose $b = a + 1$.
Then we have:
$$f(a) \cdot f(b) = a(a+1) \cdot (a+1)(a+2) = (a^2 + 2a)(a^2 + 2a + 1)$$
Let $n = a^2 + 2a$.
Then:
$$f(n) = n(n+1) = (a^2 + 2a)(a^2 + 2a + 1)$$
Hence,
$$f(a) \cdot f(b) = f(n)$$
$\blacksquare$
F - 幻形之路
唉唉唉唉唉唉唉，唉唉唉唉唉唉唉。
Description
给定一个 $n\times m$ 的二维迷宫，迷宫中有若干障碍（用 # 表示障碍，用 . 表示空地），可以至多使用一次操作让操作后连续 $k$ 步可以忽略障碍，最小化从 $(1,1)$ 到 $(n,m)$ 的 $k$ 值。
Solution
首先，我们可以注意到，对于一个不和起终点联通的 .，其本质上和 # 没有区别。
所以我们只需要关注和起终点联通的 . 即可，对每一个与起点联通的 . 跑单源最短路，然后对每一个和终点联通的 . 跑单源最短路，遍历迷宫取二者相加最小值即可。
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
|
#include <bits/stdc++.h>
using namespace std;
using i8 = int8_t;
constexpr int inf = 1e9;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void solve() {
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (int i = 0; i < n; ++i) {
cin >> grid[i];
}
auto vis_s = vector(n, vector<i8>(m));
auto vis_t = vector(n, vector<i8>(m));
auto check = [&](int x, int y) {
return x >= 0 and x < n and y >= 0 and y < m;
};
queue<pair<int, int>> q;
vis_s[0][0] = true;
q.emplace(0, 0);
while (not q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) and not vis_s[nx][ny] and grid[nx][ny] == '.') {
vis_s[nx][ny] = true;
q.emplace(nx, ny);
}
}
}
vis_t[n - 1][m - 1] = true;
q.emplace(n - 1, m - 1);
while (not q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) and not vis_t[nx][ny] and grid[nx][ny] == '.') {
vis_t[nx][ny] = true;
q.emplace(nx, ny);
}
}
}
auto dist_s = vector(n, vector<int>(m, inf));
auto dist_t = vector(n, vector<int>(m, inf));
queue<pair<int, int>> qs, qt;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis_s[i][j]) {
dist_s[i][j] = 0;
qs.emplace(i, j);
}
if (vis_t[i][j]) {
dist_t[i][j] = 0;
qt.emplace(i, j);
}
}
}
while (not qs.empty()) {
auto [x, y] = qs.front();
qs.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) and dist_s[nx][ny] > dist_s[x][y] + 1) {
dist_s[nx][ny] = dist_s[x][y] + 1;
qs.emplace(nx, ny);
}
}
}
while (!qt.empty()) {
auto [x, y] = qt.front();
qt.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) and dist_t[nx][ny] > dist_t[x][y] + 1) {
dist_t[nx][ny] = dist_t[x][y] + 1;
qt.emplace(nx, ny);
}
}
}
int ans = inf;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ans = min(ans, dist_s[i][j] + dist_t[i][j] - 1);
}
}
ans = max(ans, 0);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
G - 直径与最大独立集
Description
构造一颗树使得其直径（最长的两点之间的简单路径的长度）与最大独立集的大小（最多的能选出的两两不相邻的点的个数）相等。
Solution
基本构造
我们首先注意到，可以构造一个割点，使得在移除该点后，图被恰好分割为若干个连通分量。其中，恰有 $A$ 个连通分量是孤立点（仅包含一个顶点），另有一个连通分量是一个包含 $B$ 个节点的链状结构（即一条简单路径）。
对于这样一个图，其最大独立集的大小为 $A + \lceil B/2 \rceil$，而其直径的长度为 $B + 1$。
数值构造
我们令 $A = \lceil (n-1)/3 \rceil$，则此时的 $B$ 为 $(n - 1) - A$。我们考察此时的情况：
- 当 $n-1\equiv0(\bmod 3)$ 时，$A=(n-1)/3$
- 当 $n-1\equiv1(\bmod 3)$ 时，$A=(n+1)/3$
- 当 $n-1\equiv2(\bmod 3)$ 时，$A=n/3$
逐项考察
第一种情况
$$ B=(n - 1) - (n - 1)/3=\frac{2(n-1)}{3} ，B\equiv 0(\bmod 2)$$
则我们可以得到，此时最大独立集大小为
$$ A+B/2=\frac{2(n-1)}{3}=B$$
同时考虑到，其直径的长度恒为 $B + 1$，因此最大独立集大小不等于其直径长度。
有没有办法呢？有的兄弟，有的。
我们把链最后的一个节点取下，然后连上链的第一个节点，独立集的个数变化为
$$A+1+\lceil (B-1)/2 \rceil=A+1+(B-2)/2=A+B/2$$
因此此操作不会导致独立集个数的变化，但是直径减少了 $1$，这样我们就使得等式成立了。
第二种情况
$$ B=(n-1)-(n+1)/3=\frac{2(n+1)}{3}-2, B\equiv0(\bmod2) $$
有最大独立集大小：
$$A+B/2=\frac{n+1}{3}+\frac{n+1}{3}-1=\frac{2(n+1)}{3}-2+1=B+1$$
因此等式成立。
第三种情况
$$ B=n-1-n/3=2n/3-1, B\equiv1(\bmod2) $$
最大独立集大小：
$$A+(B+1)/2=n/3+n/3=2n/3=B+1$$
等式成立
故当 $n-1\equiv0(\bmod3)$ 时，构造一个「 $A$ 个点连在 $1$ 节点上，剩下 $B-1$ 个节点构成一条与 $1$ 节点联通的链，最后一个节点 $n$ 连接到链上与 $1$ 节点相连」的树即可。
其他情况直接构造一个「 $A$ 个节点连在 $1$ 上，其余构成一条链并与 $1$ 相连」的树即可。
另外需要注意的是，对于 $n\le4$ 的情况，我们需要特判一下。
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
|
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n == 2) {
cout << "1 2\n";
continue;
}
if (n == 3) {
cout << "1 2\n2 3\n";
continue;
}
if (n == 4) {
cout << "-1\n";
continue;
}
int a = ((n - 1) + 2) / 3;
int b = n - a - 1;
if ((n - 1) % 3 == 0) {
int cur = 2;
for (int i = 0; i < a; i++) {
cout << "1 " << cur++ << "\n";
}
int rem = cur;
cout << "1 " << rem << '\n';
for (int i = 1; i < b - 1; i++) {
cout << cur << " " << ++cur << "\n";
}
cout << rem << " " << ++cur << "\n";
continue;
} else {
int cur = 2;
for (int i = 0; i < a; i++) {
cout << 1 << " " << cur++ << "\n";
}
cout << "1 " << cur << "\n";
for (int i = 1; i < b; i++) {
cout << cur << " " << ++cur << "\n";
}
}
}
return 0;
}
|
E - 双生魔咒
Description
给定 $2n$ 个字符串 $s_i$，将 $s_i$ 分成数量相等的两部分后，最大化两两配对形成的 $n^2$ 种组合的最长公共前缀之和。
Solution
常识上来说，若要最大化这个值，我们需要尽量把拥有公共前缀的字符串分到两边。
因为需要计算大量的字符串的公共前缀，我们使用了一个字典树来维护这些信息。并用一个数组 val[] 来维护字典树的某个节点的次数。
我们可以发现这个最大的值就是「每一个节点划分成两部分，两部分数量的乘积」之和。
我们令 $n=a+b$，其中 $n$ 是节点的次数，$a$ 和 $b$ 是被划分的两部分的次数。我们要最大化 $ab$，根据基本不等式有 $ab\le(a+b)^2/4$，当 $a=b$ 取等号。
因此我们令 $a=b=n/2,n\equiv0(\bmod2)$ 或者 $a=(n-1)/2,b=(n+1)/2,n\equiv1(\bmod2)$ 即可。
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
|
#include <bits/stdc++.h>
using namespace std;
constexpr int maxlen = 1e6;
int trie[maxlen][26], tot;
int val[maxlen];
int newNode() {
tot++;
fill(trie[tot], trie[tot] + 26, 0);
val[tot] = 0;
return tot;
}
void strInsert(const string& s) {
int p = 1;
for (auto ch : s) {
int x = ch - 'a';
if (!trie[p][x]) {
trie[p][x] = newNode();
}
p = trie[p][x];
val[p]++;
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
tot = 0;
newNode();
for (int i = 0; i < 2 * n; i++) {
string s;
cin >> s;
strInsert(s);
}
long long ans = 0;
for (int i = 0; i < maxlen; i++) {
ans += 1ll * (val[i] / 2) * (val[i] / 2 + val[i] % 2);
}
cout << ans << "\n";
return 0;
}
|