AtCoder Beginner Contest 374 题A-D 详细题解(C++, Python）
前言:
本文为AtCoder Beginner Contest 374 题A - D的详细题解，包含C++,Python语言描述，D题恶心到我了，原来是误差范围内都对，我运行的跟答案后几位不太一样我就没敢提交
题目链接:
https://atcoder.jp/contests/abc374/tasks
题A:
A - Takahashi san 2 (atcoder.jp)
题目大意和解题思路:
题目大意就是输入一个字符串，判断字符串是否以"san"结尾
直接判断即可
首先是长度是否大于三，然后再判断最后三个字符是否分别为s, a, n
python也可以直接endwith,C++其实也可以使用rfind,但是不常用就不用了
代码(C++):
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::string s;
std::cin >> s;
std::string res = "";
int n = s.size();
if (n < 3) {
res = "No\n";
} else {
if (s[n - 3] == 's' && s[n - 2] == 'a' && s[n - 1] == 'n') {
res = "Yes\n";
} else {
res = "No\n";
}
}
std::cout << res;
}代码(Python):
s = input()
if s.endswith("san"):
print("Yes")
else:
print("No")题B:
B - Unvarnished Report (atcoder.jp)
题目大意和解题思路:
这题也是很基础的字符串题，题目大意是，输入两个字符串，如果字符串相同就输出0，否则就输出他们不同的位置
先判断是否相等，然后再循环，循环边界的min(s.size(), t.size())，不同的那个位置下标 + 1就是答案
但也可以这么写(参考jiangly的代码):
使用一个while循环，当i < s.size(), i < t.size() s[i] == s[j] 的时候进行循环，i++
然后i + 1就是答案
代码(C++):
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::string s, t;
std::cin >> s >> t;
if (s == t) {
std::cout << "0\n";
} else {
int i = 0;
while (i < s.size() && i < t.size() && t[i] == s[i]) {
i++;
}
std::cout << i + 1 << "\n";
}
}代码(Python):
s = input()
t = input()
if s == t:
print(0)
else:
i = 0
while i < len(s) and i < len(t) and s[i] == t[i]:
i += 1
print(i + 1)题C:
C - Separated Lunch (atcoder.jp)
题目大意和解题思路:
题目大意是把一个数组分成两个，然后确保两个数组的和尽可能相近，对于最相近的情况，输出较大的那一个数组和
这题N比较小，其实挺简单的
把每一种情况枚举出来即可，总共是有2 * n个分的情况，对于每一种情况，求出一个两个数组和的差，然后不断更新较小的差对应的答案
问题：如何枚举每一种情况？
答案：使用位运算
if (mask & (1 << i)) {
sum1 += A[i];
} else {
sum2 += A[i];
}mask是第几种情况，范围是[0, 2 ^ n)，对于每一种情况，对i左移进行与运算，即可选择出每一种情况来
如果不是很熟悉位运算的也可以使用递归写
代码(C++):
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> K(n);
for (int i = 0; i < n; i++) {
std::cin >> K[i];
}
int res = 0, d = INT_MAX;
for (int mask = 0; mask < (1 << n); mask++) {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum1 += K[i];
} else {
sum2 += K[i];
}
}
int diff = std::abs(sum1 - sum2);
if (diff < d) {
d = diff;
res = std::max(sum1, sum2);
}
}
std::cout << res << "\n";
}代码(Python):
n = int(input())
K = list(map(int, input().split()))
res, d = 0, 1e9
for mask in range(0, 1 << n):
sum1, sum2 = 0, 0
for i in range(n):
if mask & (1 << i):
sum1 += K[i]
else:
sum2 += K[i]
diff = abs(sum1 - sum2)
if diff < d:
d = diff
res = max(sum1, sum2)
print(res)题D:
D - Laser Marking (atcoder.jp)
题目大意和解题思路:
本题的意思就是激光画线段，刚开始激光端点在(0, 0)
然后题目给出激光移动的速度，每个线段的两个端点位置，让你求最短需要多久才能全部打印完
由于n的大小最大为6，所以还是很简单的，直接暴力回溯，把每一种情况枚举出来，算出每种情况对应的最小时间即可
具体操作我在代码里面直接写注释了，中间那个hypot函数参考了jiangly的代码，用于求欧几里得距离，也就是平方和然后再开方
代码(C++):
int n, s, t;
std::vector<std::vector<int>> A, B;
std::vector<bool> vis;
double res = INFINITY;
void dfs(int x, int y, double sum, int c) {
//当C == N的时候表示n个线已经打印完，算出此时的答案
if (c == n) {
res = std::min(res, sum);
return;
}
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
double d1 = std::hypot(A[i][0] - x, B[i][0] - y);
double d2 = std::hypot(A[i][1] - x, B[i][1] - y);
double d0 = std::hypot(A[i][0] - A[i][1], B[i][0] - B[i][1]);
//标记此点访问过
vis[i] = true;
//从一个端点开始画
dfs(A[i][1], B[i][1], sum + d1 / s + d0 / t, c + 1);
//从另一个端点开始画
dfs(A[i][0], B[i][0], sum + d2 / s + d0 / t, c + 1);
//还原
vis[i] = false;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
std::cin >> s >> t;
A.resize(n, std::vector<int>(2));
B.resize(n, std::vector<int>(2));
vis.resize(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i][0] >> B[i][0] >> A[i][1] >> B[i][1];
}
//开始是从(0, 0)开始
dfs(0, 0, 0.0, 0);
std::cout << std::fixed << std::setprecision(20) << res << "\n";
}代码(Python):
import math
def hypot(x1, y1, x2, y2):
return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
def dfs(x: int, y: int, sum_: float, c: int) -> None:
global res, n, s, t, A, B, vis
# 当 c == n 时表示 n 个线已经打印完，算出此时的答案
if c == n:
res = min(res, sum_)
return
for i in range(n):
if vis[i]:
continue
d1 = hypot(A[i][0], B[i][0], x, y)
d2 = hypot(A[i][1], B[i][1], x, y)
d0 = hypot(A[i][0], B[i][0], A[i][1], B[i][1])
# 标记此点访问过
vis[i] = True
# 从一个端点开始画
dfs(A[i][1], B[i][1], sum_ + d1 / s + d0 / t, c + 1)
# 从另一个端点开始画
dfs(A[i][0], B[i][0], sum_ + d2 / s + d0 / t, c + 1)
# 还原
vis[i] = False
n, s, t = map(int, input().split())
A = []
B = []
vis = [False] * n
for i in range(n):
a, b, c, d = map(int, input().split())
A.append((a, c))
B.append((b, d))
res = float('inf')
dfs(0, 0, 0.0, 0)
print(f"{res:.20f}")