算法题解

Atcoder abc477 | 题解

2026-10-02 #二分#模拟#Atcoder#图论#djikstra

比赛:UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
比赛时间:2026-09-26 20:00 ~ 21:40( 20:00 ~ 21:40)
比赛时长:100 分钟

A、Traffic Light

题意描述: 交通灯按照 B → Y → R → B 的顺序循环变色。给定交通灯当前的颜色,输出它接下来会变成的颜色。

解题思路: 按照题目给出的变化顺序直接判断即可:当前颜色为 B 时输出 Y,为 Y 时输出 R,否则输出 B。

复杂度分析: 时间复杂度为 O(1) ,空间复杂度为 O(1) 。

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
// Problem: A - Traffic Light
// Contest: AtCoder - UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
// URL: https://atcoder.jp/contests/abc477/tasks/abc477_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

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

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

void solve()
{
string s; cin >> s;
if(s == "B") cout << "Y";
else if(s == "Y") cout << "R";
else cout << "B";
}

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

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

B、Standing Outliers

题意描述

数轴上有 N 个人,第 i 个人位于坐标 Xi 。如果第 i 个人与其他所有人的距离都不小于 D ,则称这个人是“独立站立”的。

输出满足条件的人数,并按编号从小到大输出这些人的编号。

解题思路

由于 N≤100 ,可以直接枚举每一对人 (i,j) ,计算二者之间的距离 |Xi−Xj| 。

先假设所有人都满足条件。如果发现一对人的距离小于 D ,那么这两个人都不可能满足要求,将二者标记为不满足。枚举结束后,依次统计并输出仍然满足条件的人的编号即可。

复杂度分析

需要枚举所有人的组合,时间复杂度为 O(N2) ,标记数组的空间复杂度为 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
// Problem: B - Standing Outliers
// Contest: AtCoder - UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
// URL: https://atcoder.jp/contests/abc477/tasks/abc477_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], b[N];

void solve()
{
cin >> n >> m;
ffi(1, n) cin >> a[i], b[i] = 1;
int res = 0; vector<int> v;
ffi(1, n)
{
ffj(i + 1, n) {
if(abs(a[i] - a[j]) < m)
b[i] = b[j] = 0;
}
if(b[i] == 1) res++, v.pb(i);
}
cout << res << endl;
for(auto cc: v) cout << cc << " ";
}

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

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

C、Range Search Query

题意描述

给定两个字符串 S 和 T ,以及 Q 次询问。每次询问给出区间 [L,R] ,判断 S 的子串 S[L…R] 中是否包含 T 。若包含则输出 Yes,否则输出 No。

解题思路

字符串 S 的长度最多为 4×105 ,询问次数最多为 2×105 。如果每次询问都重新截取区间并查找 T ,最坏情况下会超时,因此需要先进行预处理。

首先利用 find 找出 T 在 S 中每一次出现的起始位置,并将这些位置按升序保存到数组 v 中。为了避免遗漏相互重叠的匹配,每找到一次匹配后,只将下一次查找的起点向后移动一位。

对于一次询问 [L,R] ,使用 lower_bound 在 v 中找到第一个不小于 L 的匹配起点 p 。只要该位置存在,并且

p+|T|−1≤R,

就说明这一次完整匹配全部位于询问区间内,答案为 Yes;否则答案为 No。

复杂度分析

设 |S|=n 。预处理保存所有匹配位置,之后每次询问进行一次二分查找,询问部分的时间复杂度为 O(Qlog⁡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
// Problem: C - Range Search Query
// Contest: AtCoder - UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
// URL: https://atcoder.jp/contests/abc477/tasks/abc477_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 = 2e5 + 10, mod = 1e9 + 7;

int n, m, qq;
int a[N];
vector<int> v;

bool doxx(int l, int r, string s, string t)
{

int len = r - l + 1;
bool st = false;

if(len < t.size()) return false;

auto tt = lower_bound(v.begin(), v.end(), l) - v.begin();

if(tt != v.size() && v[tt] >= l)
{
// cout << v[tt] << " " << v[tt] + t.size() - 1 << " " << r << endl;
if(v[tt] + t.size() - 1 <= r) {
st = true;
}
}
return st;
}

void solve()
{
cin >> n;
string s, t;
cin >> s >> t;

int idx = 0;
for(int i = 0; i < s.size(); i ++)
{
int tt = s.find(t, idx);
if(tt != -1)
{
v.pb(tt + 1);
// cout << tt << " ";
idx = tt + 1;

}
else break;
}
sort(v.begin(), v.end());

// for(auto c: v) cout << c << " ";
// cout << endl;

while(n --)
{
int l, r; cin >> l >> r;
if(doxx(l, r, s, t))
cout << "Yes\n";
else
cout << "No\n";
}
}

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

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

D - Masking Tape

题意描述

有 N 个方格,初始时所有方格的颜色均为 a,且上面都没有放置胶带。接下来进行 Q 次操作:

  • 1 x:翻转第 x 个方格的胶带状态。若原来没有胶带,则放上胶带;否则揭下胶带。
  • 2 c:将所有没有被胶带覆盖的方格染成颜色 c 。

求所有操作结束后每个方格的颜色。

解题思路

如果每次执行染色操作时都遍历所有方格,时间复杂度会达到 O(NQ) 。因此,代码以每次 2 c 操作为分界,只处理相邻两次染色之间胶带状态发生过变化的位置。

将每次 2 c 看作一个分界点。在两次染色之间没有其他染色操作,所以一个方格无论翻转多少次,真正需要关注的只有:

  1. 上一次染色时它是否被胶带覆盖;
  2. 本次染色时它是否被胶带覆盖。

代码中各变量的含义如下:

  • tt:上一次染色操作使用的颜色,初始为 a;
  • pre1[x][0]:上一次染色时方格 x 的胶带状态;
  • pre1[x].back():方格 x 当前的胶带状态;
  • mp01:最后一次状态变化为“未覆盖变为覆盖”的位置;
  • mp10:最后一次状态变化为“覆盖变为未覆盖”的位置;
  • color[x]:方格 x 被胶带保护时需要单独保存的颜色;
  • bk:最后一次染色之后的所有翻转操作。

对于操作 1 x,根据 pre1[x].back() 判断方格当前是否被覆盖,然后翻转它的状态。同时,将它放入 mp01 或 mp10,并从另一张表中删除,从而保留这个位置最后一次状态变化的方向。

遇到新的染色操作 2 c 时,结算两张表中记录的位置:

  • 若 pre1[x][0]=0 且 pre1[x].back()=1,说明方格在上一次染色时没有胶带,而在本次染色时已经被覆盖。在被盖住之前,它的颜色已经被上一次染色操作改成 tt,所以需要令 color[x]=tt;
  • 若 pre1[x][0]=1 且 pre1[x].back()=0,说明方格在上一次染色时被覆盖,而在本次染色时没有胶带。它将直接参与本次染色,因此只需更新记录的胶带状态;
  • 若一个位置在区间起点和终点的状态相同,那么中途的翻转不会影响结果,因为这段时间内没有发生染色。

完成结算后,将新的颜色保存到 tt,并清空 bk,开始记录下一次染色之后的翻转操作。

所有询问结束后,最后一次染色之后可能还发生过若干次胶带翻转,但这些翻转不会改变颜色。将 bk 中的操作倒序撤销,就能恢复每个位置在最后一次染色时的胶带状态:

  • 当时没有胶带,最终颜色就是 tt;
  • 当时有胶带,最终颜色就是此前保存在 color[x] 中的颜色。

参考代码

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
// Problem: D - Masking Tape
// Contest: AtCoder - UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
// URL: https://atcoder.jp/contests/abc477/tasks/abc477_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 long long

// #define MORE


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

int n, m, qq;
int a[N];
map<int, int> mp01, mp10, pre;
map<int, char> color;
vector<pii> bk;

void solve()
{
cin >> n >> m;
vector<vector<int>> pre1(n + 1, vector<int>());

ffi(1, n) color[i] = 'a', pre1[i].pb(0);

char tt = 'a';
while(m --)
{
int t; cin >> t;
if(t == 1)
{
int x; cin >> x;
if(pre1[x].back() == 0)
{
mp01[x] = 1, pre[x] = 1, mp10.erase(x);
bk.pb({x, 1});
pre1[x].pb(1);
}
else mp10[x] = 1, pre[x] = 0, mp01.erase(x), bk.pb({x, 0}), pre1[x].pb(0);
}
else
{
char c; cin >> c;
vector<int> v;

for(auto [pp, _]: mp01)
if(pre1[pp].back() == 1 && pre1[pp][0] == 0)
color[pp] = tt, v.pb(pp);
for(auto pp: v) mp01.erase(pp), pre1[pp][0] = 1;

v.clear();

for(auto [pp, _]: mp10)
if(pre1[pp].back() == 0 && pre1[pp][0] == 1)
v.pb(pp);
for(auto pp: v) mp10.erase(pp), pre1[pp][0] = 0;


tt = c ;
bk.clear();
}
}

if(bk.size())
{
for(int i = bk.size() - 1; i >= 0; i --)
{
auto [aa, bb] = bk[i];
if(bb==1) pre[aa] = 0;
else pre[aa] = 1;
}
}

ffi(1, n) {
if(pre[i] == 0) cout << tt;
else cout << color[i];
}
}

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

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

E - Wheel Distance

题意描述

给定一张包含 N+1 个顶点的无向带权图:

  • 顶点 1 到 N 首尾相连构成一个环,其中顶点 i 与顶点 (imodN)+1 之间的边权为 Ai ;
  • 顶点 N+1 是中心点,它与顶点 i 之间的边权为 Bi 。

接下来有 Q 次询问。每次给出两个顶点 S 和 T ,求从 S 到 T 的最短路长度。

解题思路

整张图可以看作一个“轮子”:顶点 1∼N 构成外圈,顶点 N+1 是轮子的中心。

首先按照题目给出的边建立无向图,并以中心点 N+1 为起点执行一次 Dijkstra。令 d[i] 表示顶点 i 到中心点的最短距离。这样,当询问中有一个端点为中心点时,可以直接输出另一个端点对应的 d 值。

如果询问的两个端点 l,r 都位于外圈,那么最短路径可以分成两种情况。

1. 不经过中心点

此时路径只能沿外圈行走。环上两点之间存在顺时针和逆时针两条路径,取二者中较短的一条即可。

对数组 A 求前缀和。假设 l<r ,则其中一个方向的距离为

dis=a[r−1]−a[l−1],

另一个方向的距离为

sum−dis,

其中 sum 表示整个外圈所有边权之和。因此,不经过中心点的最短距离为

min(dis,sum−dis).

2. 经过中心点

由于 d[i] 已经表示顶点 i 到中心点的最短距离,所以从 l 先走到中心点,再从中心点走到 r 的最短距离为

d[l]+d[r].

将上述两类路径的长度取最小值,就是本次询问的答案。

复杂度分析

图中有 N+1 个顶点和 2N 条无向边。执行一次 Dijkstra 的时间复杂度为 O(Nlog⁡N) ,每次询问只需 O(1) 的时间,因此总时间复杂度为 O(Nlog⁡N+Q) ,空间复杂度为 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
126
127
128
129
130
131
132
133
134
135
// Problem: E - Wheel Distance
// Contest: AtCoder - UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)
// URL: https://atcoder.jp/contests/abc477/tasks/abc477_e
// 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], bb[N];
int e[N * 4], ne[N * 4], w[N * 4], h[N * 4], idx;
int d[N];
bool st[N];

void add(int a,int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dijkstra()
{
priority_queue<pii, vector<pii>, greater<pii>> q;
memset(d, 0x3f, sizeof d);
d[n + 1] = 0;
q.push({d[n + 1], n + 1});

while(q.size())
{
auto [dist, ver] = q.top(); q.pop();

if(st[ver]) continue;
st[ver] = 1;

for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] > dist + w[i]) {
d[j] = min(d[j], dist + w[i]);
q.push({d[j], j});
}
}
}
}

void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);

int res = 0, ttt = 0;

ffi(1, n) {
int x; cin >> x;
a[i] = x;
add(i, i % n + 1, x);
add(i % n + 1, i, x);
res += x;
}

ffi(1, n) {
int x; cin >> x;
bb[i] = x;
add(n + 1, i, x);
add(i, n + 1, x);
}

dijkstra();

// cout << res << endl;
// ffi(1, n) cout << d[i] << " ";
// cout << endl;

ffi(1, n) a[i] += a[i - 1];

while(m --)
{
int l, r; cin >> l >> r;
if(l > r) swap(l, r);

if(r == n + 1) {
cout << d[l] << "\n";
continue;
}

int cc = a[r - 1] - a[l - 1];
cc = min(cc, res - cc);
cc = min({cc, d[l] + d[r]});

cout << cc << "\n";
}


}



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

signed main() { Coding(); return 0; }
Comments
赞赏
Share
← 返回