AtCoder Beginner Contest 370 ABCD题详细题解(C++,Python)
前言:
本文为AtCoder Beginner Contest 370 ABCD题的详细题解，包含C++,Python语言描述，觉得有帮助或者写的不错可以点个赞
个人感觉D比C简单，C那里的字典序有点不理解, E应该是前缀和加dp，但是是dp不明白，等我明白了会更新的(好像拖了好多东西了)
目录
题A:
题目大意和解题思路:
代码(C++):
代码(Python):
题B:
题目大意和解题思路:
代码(C++):
代码(Python):
题C:
题目大意和解题思路:
代码(C++):
代码(Python):
题D:
题目大意和解题思路:
代码(C++):
代码(Python):
题A:
A - Raise Both Hands (atcoder.jp)
题目大意和解题思路:
如果只举起一只手,如果他想吃章鱼烧就输出Yes,如果他不想吃就输出No。如果他举起两只手或者一只手都不举,就输出Invalid
简单的if else判断
可以用三元运算符优化
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int a, b;std::cin >> a >> b;std::string res = (a == 1 && b == 0 ? "Yes" : a == 0 && b == 1 ? "No" : "Invalid");std::cout << res << "\n";
}代码(Python):
def main():a, b = map(int, input().split())res = "Yes" if a == 1 and b == 0 else "No" if a == 0 and b == 1 else "Invalid"print(res)题B:
B - Binary Alchemy (atcoder.jp)
题目大意和解题思路:
有N种元素，编号为1, 2, ..., N。
这些元素可以相互组合。当元素i和j组合时，如果i≥j，它们会变成元素A[i,j]；如果i<j，它们会变成元素A[j,i]。
从元素1开始，按顺序将它与元素1, 2, ..., N组合。找出最终得到的元素。
题目意思其实很简单，就是最开始是1跟1比较，然后比较的数字大小决定了下一个坐标
比如示例一：
4 3 2 4 3 1 2 2 1 2 4
最开始1跟1比较，得到A11,也就是 3
然后3跟2比较，得到A32,也就是1
然后1跟3比较，得到A31,也就是3
最后3跟4比较，得到A43,也就是2
根据上面可以得到，大的坐标在前面，小的坐标在后面
然后可以模拟，输入的放入n + 1长度的二维数组，下标从1开始，然后答案定义为1，详细见代码：
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int n;std::cin >> n;std::vector<std::vector<int>> A(n + 1, std::vector<int> (n + 1));for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {std::cin >> A[i][j];}}//开始为1int res = 1;//依次跟1 到 n 进行比较 大的那一个为A的第一个下标for (int i = 1; i <= n; i++) {res = A[std::max(res, i)][std::min(res, i)];}std::cout << res << "\n";
}代码(Python):
def main():n = int(input())A = [[0 for _ in range(n + 1)] for _ in range(n + 1)]for i in range(1, n + 1):row = list(map(int, input().split()))for j in range(1, i + 1):A[i][j] = row[j - 1]res = 1for i in range(1, n + 1):res = A[max(res, i)][min(res, i)]print(res)题C:
C - Word Ladder (atcoder.jp)
题目大意和解题思路:
让 X 为一个空数组，重复以下操作直到 S 等于 T：
- 改变 S 中的一个字符，并将改变后的 S 添加到 X 的末尾。
找出通过这种方式得到的元素数量最少的字符串数组 X。如果有多个这样的最小元素数量的数组，找出其中字典序最小的一个。
什么是字符串数组的字典序？
长度为 N 的字符串 S=S₁S₂...Sₙ 在字典序上小于长度为 N 的字符串 T=T₁T₂...Tₙ，如果存在一个整数 1≤i≤N，满足以下两个条件：
- S₁S₂...Sᵢ₋₁ = T₁T₂...Tᵢ₋₁
- Sᵢ 在字母表中比 Tᵢ 更早出现。
具有 M 个元素的字符串数组 X=(X₁,X₂,...,Xₘ) 在字典序上小于具有 M 个元素的字符串数组 Y=(Y₁,Y₂,...,Yₘ)，如果存在一个整数 1≤j≤M，满足以下两个条件：
- (X₁,X₂,...,Xⱼ₋₁) = (Y₁,Y₂,...,Yⱼ₋₁)
- Xⱼ 在字典序上小于 Yⱼ。
题目的意思就是把s变成t，一次只能变换一个字母，然后每次变换后把变换的字符串放入x中
并且使得x的字符串尽可能小
就是把缩小的变换都放在前面，增大的变换都放在后面，当前也不知道为啥卡这么久，脑子发昏了
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::string s, t;std::cin >> s;std::cin >> t;int n = s.size();std::vector<std::string> A;for (int i = 0; i < n; i++) {if (s[i] > t[i]) {s[i] = t[i];A.push_back(s);}}for (int i = n - 1; i >= 0; i--) {if (s[i] < t[i]) {s[i] = t[i];A.push_back(s);}}std::cout << A.size() << "\n";for (auto a : A) {std::cout << a << "\n";}
}代码(Python):
def main():s = list(input().strip())t = list(input().strip())n = len(s)A = []for i in range(n):if s[i] > t[i]:s[i] = t[i]A.append(''.join(s))for i in range(n - 1, -1, -1):if s[i] < t[i]:s[i] = t[i]A.append(''.join(s))print(len(A))for a in A:print(a)题D:
D - Cross Explosion (atcoder.jp)
题目大意和解题思路:
题目意思就是说，有一个 H 行 W 列的网格图，在每个单元格里面都有一个墙，
然后放炸弹，如果这个单元格有墙，那就炸
如果没有，那就同时摧毁从该位置向上、下、左、右看到的第一面墙
根据题目的意思很容易得到暴力模拟代码:
超时代码:
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int H, W, Q;std::cin >> H >> W >> Q;std::vector<std::vector<bool>> A(H, std::vector<bool>(W, true));for (int q = 0; q < Q; q++) {int r, c;std::cin >> r >> c;r--; c--;if (A[r][c]) {A[r][c] = false;continue;}for (int i = r - 1; i >= 0; i--) {if (A[i][c]) {A[i][c] = false;break;}}for (int i = r + 1; i < H; i++) {if (A[i][c]) {A[i][c] = false;break;}}for (int j = c + 1; j < W; j++) {if (A[r][j]) {A[r][j] = false;break;}}for (int j = c - 1; j >= 0; j--) {if (A[r][j]) {A[r][j] = false;break;}}}int res = 0;for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {if (A[i][j]) {res++;}}}std::cout << res << "\n";
}上面代码复杂度为O(H * W + Q * (H + W))
而题目给的是10^5,肯定会超时的
可以用set进行优化，使用四个集合存储每一行和每一列中墙壁的位置
由于是找从该位置向上、下、左、右看到的第一面墙，那么可以想到二分查找
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int H, W, Q;std::cin >> H >> W >> Q;// 使用四个集合存储每一行和每一列中墙壁的位置std::vector<std::set<int>> rows(H), cols(W);for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {rows[i].insert(j);cols[j].insert(i);}}// 定义remove_wall，方便操作auto remove_wall = [&](int r, int c) {rows[r].erase(c);cols[c].erase(r);};for (int q = 0; q < Q; q++) {int r, c;std::cin >> r >> c;r--; c--;if (rows[r].count(c)) {remove_wall(r, c);continue;}auto it = rows[r].lower_bound(c);if (it != rows[r].begin()) {int j = *(--it);remove_wall(r, j);}it = rows[r].upper_bound(c);if (it != rows[r].end()) {int j = *it;remove_wall(r, j);}it = cols[c].lower_bound(r);if (it != cols[c].begin()) {int i = *(--it);remove_wall(i, c);}it = cols[c].upper_bound(r);if (it != cols[c].end()) {int i = *it;remove_wall(i, c);}}int res = 0;for (int i = 0; i < H; i++) {res += rows[i].size();}std::cout << res << "\n";return 0;
}