当前位置：首页 > news >正文

AtCoder Beginner Contest竞赛题解 | ABC 421

news 2026/5/11 23:01:28

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

A - Misdelivery

【题目来源】

洛谷：[AT_abc421_a ABC421A] Misdelivery - 洛谷

【题目描述】

Mansion AtCoder has \(N\) rooms numbered from room \(1\) to room \(N\).
AtCoder公馆有 \(N\) 个房间，编号从 \(1\) 号房间到 \(N\) 号房间。

Each room \(i\) is inhabited by one person named \(S_i\).
每个房间 \(i\) 住着一位名为 \(S_i\) 的人。

You are to deliver a package addressed to Mr./Ms. \(Y\) in room \(X\). Determine whether the destination is correct.
您需要将收件人为 \(Y\) 先生/女士的包裹送至 \(X\) 号房间。请判断目的地是否正确。

【输入】

The input is given from Standard Input in the following format:

N
S_1
S_2
.
.
.
S_N
X Y

【输出】

Print Yes if the name of the person living in room X is Y, and No otherwise.

【输入样例】

3
sato
suzuki
takahashi
3 takahashi

【输出样例】

Yes

【算法标签】

《洛谷 AT_abc421_a Misdelivery》 #模拟#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 105;  // 定义最大字符串数量int n;               // 字符串数量
string a[N];         // 存储字符串的数组int main()
{// 输入字符串数量cin >> n;// 输入n个字符串for (int i = 1; i <= n; i++){cin >> a[i];}int x;        // 要查询的字符串索引string y;     // 要比较的目标字符串// 输入查询参数cin >> x >> y;// 比较指定位置的字符串if (a[x] == y){cout << "Yes" << endl;  // 相等输出Yes}else{cout << "No" << endl;   // 不等输出No}return 0;
}

【运行结果】

3
sato
suzuki
takahashi
3 takahashi
Yes

C - Alternated

【题目来源】

洛谷：[AT_abc421_c ABC421C] Alternated - 洛谷

【题目描述】

You are given a string \(S\) of length \(2N\). \(S\) contains exactly \(N\) occurrences of A and \(N\) occurrences of B.
给定一个长度为 \(2N\) 的字符串 \(S\)，其中恰好包含 \(N\) 个A和 \(N\) 个B。

Find the minimum number of operations (possibly zero) needed to make \(S\) have no adjacent identical characters, where an operation consists of swapping two adjacent characters in \(S\).
求使字符串 \(S\) 不存在相邻相同字符所需的最小操作次数（可以为零），其中每次操作包含交换 \(S\) 中两个相邻字符。

【输入】

The input is given from Standard Input in the following format:

N 
S

【输出】

Print the answer.

【输入样例】

3
AABBBA

【输出样例】

【算法标签】

《洛谷 AT_abc421_d Alternated》 #贪心#

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500005;int n, cur; 
string s, s2;
int cntA[N], dstA[N], minn = 1e18;signed main()
{// 输入n和字符串scin >> n >> s;int len = s.size();s = " " + s;  // 在字符串前加空格，使索引从1开始// 统计所有'A'字符的位置，存入cntA数组for (int i = 1; i <= len; i++){if (s[i] == 'A'){cntA[++cur] = i;}}// 第一种目标位置方案：1,3,5,...,2n-1for (int i = 1; i <= n; i++){dstA[i] = 2 * i - 1;}// 计算第一种方案的总移动距离int sum = 0;for (int i = 1; i <= n; i++){sum += abs(cntA[i] - dstA[i]);}minn = min(minn, sum);// 第二种目标位置方案：2,4,6,...,2nfor (int i = 1; i <= n; i++){dstA[i] = 2 * i;}// 计算第二种方案的总移动距离sum = 0;for (int i = 1; i <= n; i++){sum += abs(cntA[i] - dstA[i]);}minn = min(minn, sum);// 输出两种方案中的最小移动距离cout << minn << endl;return 0;
}

【运行结果】

3
AABBBA
2

D - RLE Moving

【题目来源】

洛谷：[AT_abc421_d ABC421D] RLE Moving - 洛谷

【题目描述】

There is an infinitely large grid. One cell of the grid is named cell \((0,0)\).
有一个无限大的网格。其中一个单元格被命名为单元格 \((0,0)\)。

The cell located \(r\) cells down and \(c\) cells right from cell \((0,0)\) is called cell \((r,c)\).
位于单元格 \((0,0)\) 向下 \(r\) 个单元格、向右 \(c\) 个单元格位置的单元格称为单元格 \((r,c)\)。

Here, "\(r\) cells down" means "\(|r|\) cells up" when \(r\) is negative, and "\(c\) cells right" means "\(|c|\) cells left" when \(c\) is negative.
此处，"向下 \(r\) 个单元格"在 \(r\) 为负数时表示"向上 \(|r|\) 个单元格"，"向右 \(c\) 个单元格"在 \(c\) 为负数时表示"向左 \(|c|\) 个单元格"。

Specifically, the cells around cell \((0,0)\) are as follows:
具体来说，单元格 \((0,0)\) 周围的单元格分布如下：

Initially, Takahashi is at cell \((R_t,C_t)\) and Aoki is at cell \((R_a,C_a)\). They will each make \(N\) moves according to strings \(S\) and \(T\) of length \(N\) consisting of U, D, L, R.
初始时，高桥位于单元格 \((R_t,C_t)\)，青木位于单元格 \((R_a,C_a)\)。两人将分别根据长度为 \(N\)、由\(U\)、\(D\)、\(L\)、\(R\)组成的字符串 \(S\) 和 \(T\) 各进行 \(N\) 次移动。

For each \(i\), Takahashi's and Aoki's \(i\)-th moves occur simultaneously: Takahashi moves one cell up if the \(i\)-th character of \(S\) is U, down if D, left if L, and right if R; Aoki moves similarly according to the \(i\)-th character of \(T\).
对于每个 \(i\)，高桥和青木的第 \(i\) 次移动同时进行：若 \(S\) 的第 \(i\) 个字符为 \(U\)，高桥向上移动一格；为 \(D\) 则向下；为 \(L\) 则向左；为 \(R\) 则向右。青木根据 \(T\) 的第 \(i\) 个字符进行类似移动。

Find the number of times Takahashi and Aoki are at the same cell immediately after a move during the \(N\) moves.
求在 \(N\) 次移动过程中，高桥和青木在移动后立即处于同一单元格的次数。

Since \(N\) is very large, \(S\) and \(T\) are given in the form \(((S'_1, A_1),\ldots,(S'_M,A_M))\) and \(((T'_1,B_1),\ldots,(T'_L,B_L))\), where \(S\) is the string obtained by concatenating "\(A_1\) copies of character \(S'_1\), \(\dots\), \(A_M\) copies of character \(S'_M\)" in this order, and \(T\) is given similarly.
由于 \(N\) 非常大，字符串 \(S\) 和 \(T\) 以 \(((S'_1, A_1),\ldots,(S'_M,A_M))\) 和 \(((T'_1,B_1),\ldots,(T'_L,B_L))\) 的形式给出，其中 \(S\) 是通过按顺序连接"\(A_1\)个字符\(S_1'\)、...、\(A_M\)个字符 \(S_M'\)"得到的字符串， \(T\) 的给出方式类似。

【输入】

The input is given from Standard Input in the following format:

R_t C_t R_a C_a
N M L
S_1' A_1
.
.
.
S_M' A_M
T_1' B_1
.
.
.
T_L' B_L

【输出】

Print the answer.

【输入样例】

【输出样例】

【算法标签】

《洛谷 AT_abc421_d RLE Moving》 #模拟# #分类讨论#

【代码详解】

#include <bits/stdc++.h>
using namespace std;#define int long long  // 定义int为long long类型，防止整数溢出
const int N = 100005;  // 定义数组最大长度int n, m, l, ans;      // n: 未使用，m: 第一个序列长度，l: 第二个序列长度，ans: 结果计数器
int Rt, Ct, Ra, Ca;    // Rt,Ct: 第一个点的初始位置，Ra,Ca: 第二个点的初始位置
char s[N], t[N];       // s: 第一个序列的方向，t: 第二个序列的方向
int a[N], b[N];        // a: 第一个序列的步长，b: 第二个序列的步长signed main()
{// 输入初始位置cin >> Rt >> Ct >> Ra >> Ca;// 输入两个序列的长度cin >> n >> m >> l;// 输入第一个序列（方向+步长）for (int i = 1; i <= m; i++){cin >> s[i] >> a[i];}// 输入第二个序列（方向+步长）for (int i = 1; i <= l; i++){cin >> t[i] >> b[i];}// 双指针遍历两个序列int i = 1, j = 1;while (i <= m && j <= l){// 取当前两个序列的最小步长int len = min(a[i], b[j]);a[i] -= len;b[j] -= len;// 计算第一个点的移动方向int d1x = 0, d1y = 0;if (s[i] == 'R') d1y = 1;else if (s[i] == 'L') d1y = -1;else if (s[i] == 'U') d1x = -1;else d1x = 1;  // 'D'// 计算第二个点的移动方向int d2x = 0, d2y = 0;if (t[j] == 'R') d2y = 1;else if (t[j] == 'L') d2y = -1;else if (t[j] == 'U') d2x = -1;else d2x = 1;  // 'D'// 判断是否相遇if (s[i] == t[j])  // 方向相同{if (Rt == Ra && Ct == Ca)  // 如果初始位置相同{ans += len;  // 整个移动过程中都在一起}}else  // 方向不同{int R = Rt - Ra;  // 行坐标差int C = Ct - Ca;  // 列坐标差int dx = d2x - d1x;  // 行方向差int dy = d2y - d1y;  // 列方向差int step = -1;if (R || C)  // 如果初始位置不同（即固定A点后，B点不在原点）{// 计算相遇需要的步数if (dx != 0) step = R / dx;if (dy != 0) step = C / dy;// 检查是否会在当前段内相遇if (step > 0 && step <= len && dx * step == R && dy * step == C){ans++;}}}// 更新两个点的位置Rt += d1x * len;Ct += d1y * len;Ra += d2x * len;Ca += d2y * len;// 如果当前段走完，移动指针if (a[i] == 0) i++;if (b[j] == 0) j++;}// 输出相遇次数cout << ans << endl;return 0;
}

【运行结果】

E - Yacht

【题目来源】

洛谷：[AT_abc421_e ABC421E] Yacht - 洛谷

【题目描述】

There are five six-sided dice. Each die has the numbers \(A_1,\ldots,A_6\) written on its faces, and each face appears with probability \(\frac{1}{6}\).
有五枚六面骰子。每枚骰子的六个面上分别写有数字 \(A_1,\ldots,A_6\)，每个面出现的概率均为 \(\frac{1}{6}\)。

You will play a single-player game using these dice with the following procedure:
您将使用这些骰子按照以下流程进行单人游戏：

Roll all five dice, observe the results, and keep any number (possibly zero) of dice.
掷出全部五枚骰子，观察结果，并保留任意数量（可能为零）的骰子。
Re-roll all dice that are not kept, observe the results, and additionally keep any number (possibly zero) of the re-rolled dice. The dice kept in the previous step remain kept.
重新投掷所有未保留的骰子，观察结果，并额外保留任意数量（可能为零）的重新投掷的骰子。上一步已保留的骰子保持保留状态。
Re-roll all dice that are not kept and observe the results.
重新投掷所有未保留的骰子并观察结果。
Choose any number \(X\). Let \(n\) be the number of dice among the five dice that show \(X\). The score of this game is \(nX\) points.
选择任意一个数字 \(X\)。令 \(n\) 为五枚骰子中显示 \(X\) 的骰子数量。本游戏的得分为 \(nX\) 分。

Find the expected value of the game score when you act to maximize the expected value of the game score.
求当您采取行动以最大化游戏得分的期望值时，该游戏得分的期望值。

【输入】

The input is given from Standard Input in the following format:

A_1 A_2 A_3 A_4 A_5 A_6

【输出】

Print the answer. Your answer will be considered correct if the relative or absolute error from the true value is at most \(10^{-5}\).

【输入样例】

1 2 3 4 5 6

【输出样例】

14.6588633742

【算法标签】

《洛谷 AT_abc42_e Yacht》 #动态规划DP# #搜索# #记忆化搜索# #期望#

【代码详解】

#include <bits/stdc++.h>
using namespace std;// 预计算6的幂次方数组（0-5次方）
const int pw[6] = {1, 6, 36, 216, 1296, 7776};// 定义DP状态数组：
// f[k][n][S] 表示在第k步，已选n个骰子，状态为S时的期望最大值
double f[4][6][7776];int A[6];  // 存储每个骰子的面值int main()
{// 输入6个骰子的面值for (int i = 0; i < 6; i++){cin >> A[i];}// 初始化第一步(k=1)的DP值for (int n = 0; n <= 5; n++)  // 已选骰子数量(0-5){for (int S = 0; S < pw[n]; S++)  // 遍历所有可能的状态{// 解码当前状态S，统计各面值出现次数int tmp = S, cnt[6] = {0};for (int j = 0; j < n; j++){cnt[tmp % 6]++;tmp /= 6;}// 遍历所有可能的未选骰子组合for (int P = 0; P < pw[5 - n]; P++){tmp = P;int c[6]; memcpy(c, cnt, sizeof(c));  // 复制当前计数// 解码未选骰子的状态for (int j = 0; j < 5 - n; j++){c[tmp % 6]++;tmp /= 6;}// 计算当前得分int score = 0;for (int i = 0; i < 6; i++){int tot = 0;for (int j = 0; j < 6; j++){if (A[j] == A[i]){tot += c[j];}}score = max(score, A[i] * tot);}f[1][n][S] += score;}// 计算期望值f[1][n][S] /= pw[5 - n];}}// 计算第二步和第三步的DP值(k=2,3)for (int k = 2; k <= 3; k++){for (int n = 0; n <= 5; n++){for (int S = 0; S < pw[n]; S++){for (int P = 0; P < pw[5 - n]; P++){double maxv = 0;// 遍历所有可能的保留骰子组合for (int K = 0; K < (1 << (5 - n)); K++){int m = __builtin_popcount(K);  // 计算保留骰子数量int tmp = P, T = S;// 构建新的状态Tfor (int i = 0; i < 5 - n; i++){if (K >> i & 1){T = T * 6 + (tmp % 6);}tmp /= 6;}maxv = max(maxv, f[k - 1][n + m][T]);}f[k][n][S] += maxv;}// 计算期望值f[k][n][S] /= pw[5 - n];}}}// 输出最终结果（保留10位小数）printf("%.10lf\n", f[3][0][0]);return 0;
}

【运行结果】