算法题解

Atcoder abc476 | 题解

2026-09-20 #atcoder#字符串#集合#二分#排序#线段树#前缀和

比赛:JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
比赛时间:2026-09-19 20:00 ~ 21:40
比赛时长:100 分钟

比赛概况

这场 ABC 476 一共 7 道题,这里总结了前五题:

题目 名称 分值 核心知识点
A Appender 100 字符串、分类讨论
B Wild Card 200 字符串匹配、通配符
C Third Largest Number 300 multiset、动态维护
D Automat 425 排序、前缀和、二分
E Min-Max Swap 450 线段树、区间最值

Problem A - Appender

题意简述: 给定一个字符串 S ,根据它的结尾字符进行不同的后缀拼接。解题思路: 这是一道非常基础的字符串模拟题。我们只需要检查字符串的最后一个字符是否为 'e'。如果是 'e',说明单词已经以 e 结尾,只需要加上 'r'。如果不是 'e',则加上完整的后缀 'er'。

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
// Problem: A - Appender
// Contest: AtCoder - JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
// URL: https://atcoder.jp/contests/abc476/tasks/abc476_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

#define fast_ ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);

#define ffi(a, b) for(int i = a; i <= b; i ++)
#define ffj(a, b) for(int j = a; j <= b; j ++)
#define ffk(a, b) for(int k = a; k <= b; k ++)

int qpow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod;} return res; }

#define pb push_back
#define ins insert
#define piii pair<pair<int, int>, int>
#define pii pair<int, int>
#define umap unordered_map
#define int long long

// #define MORE


const int N = 2e5 + 10, mod = 1e9 + 7;

int n, m, qq;
int a[N];

void solve()
{
string s; cin >> s;
if(s.back() == 'e') cout << s << "r" << endl;
else
cout << s << "er" << endl;
}


void Coding() { fast_; int t = 1;
#ifdef MORE
cin >> t;
#endif
while(t --) solve(); }

signed main() { Coding(); return 0; }

Problem B - Wild Card

题意简述: 给定长度为 N 的两个字符串 S1 和 S2 ,其中 S2 可能包含通配符 '*'。判断 S2 能否通过将 '*' 替换为任意字符来与 S1 完全匹配。

解题思路: 逐位比较两个字符串:

  • 如果 S1[i]==S2[i] ,当前字符匹配,继续检查。
  • 如果不相等,我们需要看 S2[i] 是否是通配符 '*'。
  • 如果是,它可以充当 S1[i] ,我们直接 continue。如果既不相等, S2[i] 也不是 '*',说明无法匹配,直接输出 No。 如果循环顺利结束,则说明完全匹配,输出 Yes。时间复杂度: O(N)
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
// Problem: B - Wild Card
// Contest: AtCoder - JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
// URL: https://atcoder.jp/contests/abc476/tasks/abc476_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

#define fast_ ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);

#define ffi(a, b) for(int i = a; i <= b; i ++)
#define ffj(a, b) for(int j = a; j <= b; j ++)
#define ffk(a, b) for(int k = a; k <= b; k ++)

int qpow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod;} return res; }

#define pb push_back
#define ins insert
#define piii pair<pair<int, int>, int>
#define pii pair<int, int>
#define umap unordered_map
#define int long long

// #define MORE


const int N = 2e5 + 10, mod = 1e9 + 7;

int n, m, qq;
int a[N];



void solve()
{
cin >> n;
string s1, s2; cin >> s1 >> s2;
for(int i = 0 ; i < n; i ++)
{
if(s1[i] != s2[i])
{
if(s2[i] == '*') continue;
else {
cout << "No\n";
return ;
}
}
}
cout << "Yes\n";
}

void Coding() { fast_; int t = 1;
#ifdef MORE
cin >> t;
#endif
while(t --) solve(); }

signed main() { Coding(); return 0; }

Problem C - Third Largest Number

题意简述: 给定一个长度为 N 的数组,要求在读取到第 i 个数字( i≥3 )时,输出当前前缀数组中的第三大数字。

解题思路: 我们需要一个能够动态维护一组数字并快速查询其排名的数据结构。在 C++ 中,std::multiset 是一个绝佳的选择。 为了方便找“第 K 大”,我们可以在定义时使用 greater 将其配置为降序排列:multiset<int, greater> s;。而对于 i≥3 的每次插入,我们只需将新元素丢进 multiset,然后利用迭代器向后移动 3 步(即循环 3 次)就能以近乎 O(1) 的时间拿到第三大的数字。插入的时间复杂度为 O(log⁡N) ,因此总体时间复杂度为 O(Nlog⁡N) ,足以通过本题。

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
// Problem: C - Third Largest Number
// Contest: AtCoder - JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
// URL: https://atcoder.jp/contests/abc476/tasks/abc476_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

#define fast_ ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);

#define ffi(a, b) for(int i = a; i <= b; i ++)
#define ffj(a, b) for(int j = a; j <= b; j ++)
#define ffk(a, b) for(int k = a; k <= b; k ++)

int qpow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod;} return res; }

#define pb push_back
#define ins insert
#define piii pair<pair<int, int>, int>
#define pii pair<int, int>
#define umap unordered_map
#define int long long

// #define MORE


const int N = 5e5 + 10, mod = 1e9 + 7;

int n, m, qq;
int a[N];
multiset<int, greater<int> > s;

void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
s.insert(a[1]);
s.insert(a[2]);

for(int i = 3; i <= n; i ++)
{
s.insert(a[i]);
int cnt = 0;
for(auto& c : s) {
cnt ++;
if(cnt == 3) {
cout << c << "\n";
break;
}
}
}
}

void Coding() { fast_; int t = 1;
#ifdef MORE
cin >> t;
#endif
while(t --) solve(); }

signed main() { Coding(); return 0; }

Problem D - Automat

解题思路: 这道题相对复杂,结合了贪心、前缀和以及二分查找。 从代码逻辑来看,主要涉及使用两种不同的预算( c1,c2 )去购买物品(分为 a 类和 b 类),并且存在某种打包或折扣机制(参数 K )。

核心步骤:

  • 排序与前缀和预处理: 为了最大化购买数量,我们贪心地优先购买价格便宜的物品,因此先对数组 a 和 b 进行升序 sort,并计算它们的前缀和。同时计算了数组 b 按 K 划分的消耗前缀和 cb。
  • 二分查找: 主逻辑中使用二分查找(while(l < r))来快速定位在给定的预算 xx 下最多能购买多少个 a 类物品。
  • 分情况枚举: 在能够购买一部分 a 物品的基础上,枚举剩余预算的分配策略,结合除法取模判断如何利用打包机制(代码中的 sum <= yy * k 分支),再利用嵌套的二分查找在 b 的前缀和 cb 上确定 b 类物品的最大购买量。本题的细节较多,边界条件的把控(如剩余物品的继续二分查找)非常考验代码基本功。
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// Problem: D - Automat
// Contest: AtCoder - JIJ Programming Contest 2026(AtCoder Beginner Contest 476)
// URL: https://atcoder.jp/contests/abc476/tasks/abc476_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

#define fast_ ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);

#define ffi(a, b) for(int i = a; i <= b; i ++)
#define ffj(a, b) for(int j = a; j <= b; j ++)
#define ffk(a, b) for(int k = a; k <= b; k ++)

int qpow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod;} return res; }

#define pb push_back
#define ins insert
#define piii pair<pair<int, int>, int>
#define pii pair<int, int>
#define umap unordered_map
#define int __int128

// #define MORE


const int N = 2e5 + 10, mod = 1e9 + 7;

long long n, m, k;
long long a[N], b[N], cb[N];

void solve()
{

cin >> n >> m >> k;
long long c1, c2;
cin >> c1 >> c2;
int xx = c1, yy = c2;

ffi(1, n) cin >> a[i];
ffi(1, m) cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);

ffi(1, n) a[i] = a[i - 1] + a[i];
ffi(1, m) cb[i] = (b[i] + k - 1) / k;
ffi(1, m) b[i] = b[i - 1] + b[i], cb[i] += cb[i - 1];

int l = 0, r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] > xx) r = mid - 1;
else l = mid;
}

if(a[l] <= xx) // 能买a部分甜品
{
int idx = l, rest = n - l;
xx -= a[l];

int ww = yy, uu = xx, cnt = l;
long long res = 0;

for(int i = 0; i <= rest; i ++)
{
yy = ww;
xx = uu;

cnt = l;
int cpp = -1;

int sum = a[idx + i] - a[idx] - xx;
if(sum <= yy * k && sum > 0)
{
int qq = sum / k;
if(qq * k == sum) yy -= qq;
else yy -= (qq + 1);
cnt += i;
xx = (qq + 1) * k - sum;
cpp = i;
}
else
{

}

long long p1 = i, p2 = cnt, p3 = res;
// cout << p1 << " " << p2 << " " << p3 << endl;


int l1 = 0, r1 = m;
while(l1 < r1)
{
int mid = l1 + r1 + 1 >> 1;
if(cb[mid] > yy) r1 = mid - 1;
else l1 = mid;
}

if(cb[l1] <= yy) // 能买部分drink
{
cnt += l1;
xx += yy * k - b[l1];
}
else xx += yy * k;


if(cpp == -1)
{
// for(int i = rest; i >= 0; i --)
// if(a[idx + i] - a[idx] <= xx)
// {
// cnt += i;
// break;
// }

int m1 = 0, m2 = rest;
while(m1 < m2)
{
int mid = m1 + m2 + 1 >> 1;
if(a[idx + mid] - a[idx] > xx) m2 = mid - 1;
else m1 = mid;
}
if(a[idx + m1] - a[idx] <= xx) cnt += m1;

}
else
{
int m1 = 0, m2 = rest - cpp;
while(m1 < m2)
{
int mid = m1 + m2 + 1 >> 1;
if(a[idx + mid + cpp] - a[idx + cpp] > xx) m2 = mid - 1;
else m1 = mid;
}
if(a[idx + m1 + cpp] - a[idx + cpp] <= xx) cnt += m1;
}

long long p4 = cnt;
// cout << p4 << endl;

long long iii = cnt;
res = max(iii, res);
}
cout << res << "\n";

}
else //
{

}

}



void Coding() { fast_; int t = 1;
#ifdef MORE
cin >> t;
#endif
while(t --) solve(); }

signed main() { Coding(); return 0; }

Problem E - Max-Min Swap Segment Tree

题意简述: 给定一个长度为 N 的数组 a 和 M 次操作。每次操作给出一个区间 [L,R] ,需要找到这个区间内的最大值和最小值,并将它们的位置互换。操作结束后输出最终的数组。

解题思路: 这题是典型的数据结构题,非常适合用线段树 (Segment Tree) 来解决。 由于我们需要交换最大值和最小值,线段树的每个节点不仅需要维护区间最大值 (vmax) 和最小值 (vmin),还必须维护它们在原数组中的对应下标 (idx1 和 idx2)。

实现细节:

  • 建树 (build) & 上传 (pushup):叶子节点记录自身的索引和值。父节点在 pushup 时不仅取子节点的最值,还将对应最值的索引一并继承上来。
  • 区间查询 (query1, query2):分别编写了查询区间最大值和最小值的函数。返回值是一个 pair<int, int>,包含最值以及它的下标。
  • 单点修改 (modify):当我们通过查询得到了区间 [L,R] 内的最大值 v1 和最小值 v2 后,只需调用两次单点修改:modify(1, v1.second, v2.first); (把原最大值位置设为最小值)modify(1, v2.second, v1.first); (把原最小值位置设为最大值)
  • 输出结果:最后再对每一个位置进行一次单点查询即可输出最终数组。操作的时间复杂度为 O(Mlog⁡N) ,建树为 O(N) ,总体时间复杂度完全在两秒的限制内。
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
118
119
120
121
122
123
124
125
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 10;

int n, m, p, a[N];
struct Node{
int l, r;
int vmax, vmin;
int idx1, idx2;
}tr[4 * N];

void pushup(int u) {
int l1 = tr[u << 1].vmax, l2 = tr[u << 1 | 1].vmax;

if(l1 >= l2)
tr[u].idx1 = tr[u << 1].idx1,
tr[u].vmax = l1;
else
tr[u].idx1 = tr[u << 1 | 1].idx1,
tr[u].vmax = l2;

l1 = tr[u << 1].vmin, l2 = tr[u << 1 | 1].vmin;

if(l1 <= l2)
tr[u].idx2 = tr[u << 1].idx2,
tr[u].vmin = l1;
else
tr[u].idx2 = tr[u << 1 | 1].idx2,
tr[u].vmin = l2;

// tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r) {
tr[u].vmax = tr[u].vmin = a[l];
tr[u].idx1 = tr[u].idx2 = l;
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}

pii query1(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r)
return {tr[u].vmax, tr[u].idx1};

int mid = tr[u].r + tr[u].l >> 1;
pii vv = {0, 0};
if(l <= mid) vv = query1(u << 1, l, r);
if(r > mid) {
auto cc = query1(u << 1 | 1, l, r);
if(cc.first > vv.first) vv = cc;
}
return vv;
}

pii query2(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r)
return {tr[u].vmin, tr[u].idx2};

int mid = tr[u].r + tr[u].l >> 1;
pii vv = {1e9, 1e9};
if(l <= mid) vv = query2(u << 1, l, r);
if(r > mid) {
auto cc = query2(u << 1 | 1, l, r);
if(cc.first < vv.first) vv = cc;
}
return vv;
}

void modify(int u, int x, int c)
{
if (tr[u].l == x && tr[u].r == x)
tr[u].vmax = tr[u].vmin = c;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= x) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
pushup(u);
}
}

signed main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
build(1, 1, n);
// exit(0);

// for(int i = 1; i <= n ;i ++)
// cout << query1(1, i, i).first << " ";
// cout << endl;

for(int i = 1; i <= m ;i ++)
{
int l, r; cin >> l >> r;
auto v1 = query1(1, l, r);
auto v2 = query2(1, l, r);

// cout << i << ": " << l << " " << r << endl;
// cout << v1.first << " " << v1.second << endl;
// cout << v2.first << " " << v2.second << endl;
// cout << endl;

modify(1, v1.second, v2.first);
modify(1, v2.second, v1.first);

}

for(int i = 1; i <= n ;i ++)
cout << query1(1, i, i).first << " ";
return 0;
}
Comments
赞赏
Share
← 返回