卜算子·唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉
唉唉唉唉唉唉唉
唉唉唉唉唉
2025/06/12 - 更新：增加了 C 题的题解。
补题链接
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;
}
|
C - Toxel 与宝可梦图鉴
Description
Toxel 共有 $n$ 只宝可梦，初始编号数组为 $a[1\ldots n]$。他进行了 $m$ 次交换操作：每次给定区间 $[l,r]$ 和新起始编号 $d$，将
$$
a_l,\,a_{l+1},\dots,a_r
$$依次替换为
$$
d,\,d+1,\dots,d+(r-l).
$$在最开始（第 0 次操作前）以及每次操作之后，都要报告当前出现次数最多的编号 $x$ 及其出现次数；若有并列，取最小的编号。
Solution
本题关键在于同时支持：
- 区间 $[l,r]$ 赋值为等差序列
- 动态维护 各编号出现次数的「众数」并快速查询
我们用两套数据结构协同完成：
ODT（Chtholly 树）
- 把数组拆成若干不相交的「等差区间」$[L,R)$，每段存一个起始值
v，表示
$$
a_i = v + (i - L),\quad i\in[L,R).
$$ split(pos)：在 pos 处把区间切开，保证边界对齐。assign_range(l,r,d)：先 split(r), split(l)，删除旧区间，再插入 $[l,r)$ 起始值 d。
半开区间线段树 $[0,V)$
- 维护数组
$$
f[x] = -\bigl|\{\,i:a_i=x\}\bigr|
$$
支持区间加法和全局最小值／最左位置查询。全局最小的 x 即出现次数最多且编号最小的宝可梦。
操作流程：
初始化
- 建 ODT，把每个位置当长度 1 区间插入；
- 建线段树，所有 $f[x]=0$；然后遍历初始 $a[i]$，对区间 $[a[i]-1,a[i])$ 执行 $-1$ 操作。
每次赋值 $[l,r]\to d,\dots$
1
2
3
4
5
6
7
8
9
10
11
| // 半开 [l-1, r)
auto itr = split(r), itl = split(l-1);
// “撤销”旧区间在 seg 上的 -1
for (auto it = itl; it != itr; ++it) {
int L = it->l, R = it->r, V = it->v;
seg.rangeAdd(V-1, V+(R-L)-1, +1);
}
odt.erase(itl, itr);
// 插入新区间并 “扣除” 新编号的计数
odt.insert({l-1, r, d});
seg.rangeAdd(d-1, d+(r-l)-1, -1);
|
查询
1
2
3
| auto ans = seg.query();
int x = ans.pos + 1; // 恢复 1-based 编号
int cnt = -ans.mn; // 出现次数
|
整体复杂度 $O((n+m)\log n)$，能轻松通过 $n,m\le2\times10^5$ 的约束。
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
| #include <bits/stdc++.h>
using namespace std;
// ---- 半开线段树 ----
struct Info { int mn, pos; };
Info operator+(Info a, Info b) {
if (a.mn < b.mn || (a.mn == b.mn && a.pos < b.pos)) return a;
return b;
}
struct SegTree {
int n; vector<Info> t; vector<int> lz;
SegTree(int _n):n(_n),t(4*n),lz(4*n){ build(1,0,n); }
void build(int p,int l,int r){
if(r-l==1){ t[p]={0,l}; return; }
int m=(l+r)>>1;
build(p<<1,l,m); build(p<<1|1,m,r);
t[p]=t[p<<1]+t[p<<1|1];
}
void apply(int p,int v){ t[p].mn+=v; lz[p]+=v; }
void push(int p){
if(lz[p]){ apply(p<<1,lz[p]); apply(p<<1|1,lz[p]); lz[p]=0; }
}
void upd(int p,int l,int r,int ql,int qr,int v){
if(qr<=l||r<=ql) return;
if(ql<=l&&r<=qr){ apply(p,v); return; }
push(p); int m=(l+r)>>1;
upd(p<<1, l,m,ql,qr,v);
upd(p<<1|1,m,r,ql,qr,v);
t[p]=t[p<<1]+t[p<<1|1];
}
void rangeAdd(int l,int r,int v){ if(l<r) upd(1,0,n,l,r,v); }
Info query() const{ return t[1]; }
};
// ---- ODT 部分 ----
struct Node { int l,r,v; bool operator<(Node const& o)const{return l<o.l;} };
set<Node> odt;
auto split(int pos){
auto it=odt.lower_bound({pos,0,0});
if(it!=odt.end()&&it->l==pos) return it;
--it;
int L=it->l,R=it->r,V=it->v;
odt.erase(it);
odt.insert({L,pos,V});
return odt.insert({pos,R,V+(pos-L)}).first;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin>>T;
while(T--){
int n,m; cin>>n>>m;
vector<int>a(n);
for(int i=0;i<n;i++) cin>>a[i];
int V = 2*n+5;
SegTree seg(V);
odt.clear();
for(int i=0;i<n;i++) odt.insert({i,i+1,a[i]});
odt.insert({n,n,0});
// 初始计数
for(int i=0;i<n;i++)
seg.rangeAdd(a[i]-1,a[i],-1);
// 第 0 次查询
{
auto z=seg.query();
cout<<z.pos+1<<" "<<-z.mn<<"\n";
}
// m 次操作
while(m--){
int l,r,d; cin>>l>>r>>d;
auto itr = split(r), itl = split(l-1);
for(auto it=itl;it!=itr;++it){
int L=it->l,R=it->r,V=it->v;
seg.rangeAdd(V-1,V+(R-L)-1,+1);
}
odt.erase(itl,itr);
odt.insert({l-1,r,d});
seg.rangeAdd(d-1,d+(r-l)-1,-1);
auto ans=seg.query();
cout<<ans.pos+1<<" "<<-ans.mn<<"\n";
}
}
return 0;
}
|