我想在阿里巴巴做卫生纸的网站,对高校网站建设的期待,关于网站开发中网站上传,京东app下载安装前言: 本文为AtCoder Beginner Contest 370 ABCD题的详细题解#xff0c;包含C,Python语言描述#xff0c;觉得有帮助或者写的不错可以点个赞 个人感觉D比C简单#xff0c;C那里的字典序有点不理解, E应该是前缀和加dp#xff0c;但是是dp不明白#xff0c;等我明白了会更…前言: 本文为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 Invalidprint(res)
题B:
B - Binary Alchemy (atcoder.jp)
题目大意和解题思路:
有N种元素编号为1, 2, ..., N。
这些元素可以相互组合。当元素i和j组合时如果i≥j它们会变成元素A[i,j]如果ij它们会变成元素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::vectorstd::vectorint A(n 1, std::vectorint (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 的字符串 SS₁S₂...Sₙ 在字典序上小于长度为 N 的字符串 TT₁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::vectorstd::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::vectorstd::vectorbool A(H, std::vectorbool(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::vectorstd::setint 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;
}
