前言:
本文为AtCoder Beginner Contest 369 题ABCD详细题解，包括题目大意，详细的解题思路和两种语言描述，觉的有帮助或者写的不错可以点个赞
几天前的比赛拖的有点久了
比赛题目连接：Tasks - AtCoder Beginner Contest 369
目录
题A:
题目大意和解题思路:
题目意思就是说，给定两个整数 A 和 B，要找出有多少个整数 x
使得 A、B、x 这三个数可以排列成等差数列
现在(假设A<=B)，就是找出一个x, 使得A - x == B - A == x - B有三种情况：
当A == B的时候，x只有一种情况，就是A == B == x，此时公差d = 0
当A != B的时候，d = B - A, 那么x会有至少两种情况，一种是A - d,一种是B + d
此时需要考虑A和B中间数字个数cnt
cnt为偶数，则中间无法找出一个数字与A,B的差值相等,此时答案为2
cnt为奇数，中间会有一个数字x满足，此时d = x - A == B - x
代码(C++):
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int a, b;
std::cin >> a >> b;
int res = -1;
if (a == b) {
res = 1;
} else {
int cnt = abs(a - b - 1);
if (cnt % 2 == 0) {
res = 2;
} else {
res = 3;
}
}
std::cout << res << "\n";
}代码(Python):
def main():
a, b = map(int, input().split())
res = -1
if a == b:
res = 1
else:
cnt = abs(a - b - 1)
if cnt % 2 == 0:
res = 2
else:
res = 3
print(res)题B:
题目大意和解题思路:
他将通过依次按下N个键来演奏音乐。对于第i次按键，他将按下键Ai，如果Si = L则用左手，如果Si = R则用右手。
在开始演奏之前，他可以将双手放在他喜欢的任何键上，此时他的疲劳度为0。在演奏过程中，如果他将一只手从键x移动到键y，疲劳度会增加|y-x|（相反，除了移动手之外，疲劳度不会因任何其他原因增加）。要用一只手按某个键，那只手必须放在那个键上。
求演奏完后的最小疲脑度
有点没懂啥意思，求最小疲劳度？手开始放在最开始的键上就是最小的
不管怎么样，后续都是要移动的，所以开始的时候放在第一个要弹的键上即可(左右手都是)
写代码的话，求移动距离就行了
代码(C++):
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> left, right;
for (int i = 0; i < n; i++) {
char c;
int x;
std::cin >> x >> c;
if (c == 'L') {
left.push_back(x);
} else {
right.push_back(x);
}
}
int res = 0;
for (int i = 1; i < left.size(); i++) {
res += abs(left[i] - left[i - 1]);
}
for (int i = 1; i < right.size(); i++) {
res += abs(right[i] - right[i - 1]);
}
std::cout << res << "\n";
}代码(Python):
def main():
n = int(input())
left = []
right = []
for _ in range(n):
x, c = input().split()
(left if c == 'L' else right).append(int(x))
res = sum(abs(b - a) for a, b in zip(left, left[1:]))
res += sum(abs(b - a) for a, b in zip(right, right[1:]))
print(res)题C:
题目大意和解题思路:
题目意思就是说：给定一个正整数序列 A。找出所有可能的连续子序列（由开始位置 l 和结束位置 r 定义）。计算这些子序列中，有多少是等差数列。注意，单个数字也被视为等差数列。
直接暴力循环两遍，
简单的组合数学，从特殊到一般来看看，我们先不考虑单个数字的情况，假设一个连续的序列为：
2 4 6
那么这三个数字能组成多少个等差数列，答案是3，(2, 4), (4, 6), (2, 4, 6)
如果是四个呢：2 4 6 8
答案是6个等差数列，(2, 4),(4, 6)(6, 8) (2,4,6)(4, 6, 8)(2, 4, 6, 8)
两个数字的有三个，三个数字的有2个，四个数字的有三个
如果长度为n的一个为等差数列子序列
那么就是两个数字的有n - 1个，三个数字的有n - 2,，，，n个数字的有1个
那么总和就是用等差数列求和公式 (1 + n - 1) * (n - 1) / 2
也就是说一个长度为n的等差数列可以分成n * (n - 1) / 2个
代码实现的话，遍历数组，如果前后的差相等(也就是等差)，求出此时的长度len++
否则，那么前面一段就是长度为len的连续的等差数列，用上面的公式求出前面一段的数量
最后加上总长度n,因为单个数字也算，(初始化为n也可以)
数据为10^9,需要使用long long类型
代码(C++):
int main() {
//我在这里定义int为long long 就不需要考虑类型了
#define int long long
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> A(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i];
}
int res = n;
int len = 1, d = 0;
for (int i = 1; i < n; i++) {
int cur = A[i] - A[i - 1];
if (cur == d) {
len++;
} else {
res += (len * (len - 1) / 2);
len = 2;
d = cur;
}
}
//最后一段的len也要加上
res += (len * (len - 1) / 2);
std::cout << res << "\n";
}代码(python):
def main():
n = int(input())
A = list(map(int, input().split()))
res, d, length = n, 1, 0
for i in range(1, n):
cur = A[i] - A[i - 1]
if d == cur:
length += 1
else:
res += length * (length - 1) // 2
d = cur
length = 2
res += length * (length - 1) // 2
print(res)题D:
题目大意和解题思路:
对于每个怪物,他可以选择放过它或者击败它。
每个动作都会给他带来经验值:
- 如果他放过一个怪物,他将获得 0 经验值。
- 如果他击败一个强度为 X 的怪物,他将获得 X 经验值。
- 如果这是一个偶数编号的击败的怪物(第 2 个, 第 4 个, ...)，他将额外获得 X 经验值。
有点类似于打家劫舍？(bushi),DP刷的少
考虑当前怪物是否击败，当前怪物是否是奇数个或者偶数个击败的怪物，只取决于上一个的奇偶性
那么就是当前状态只取决于上一个状态
可以直接用两个变量进行DP，设x1, x2分别是上一个为奇数个，和上一个是偶数个前提下获得的经验
代码(C++):
int main() {
#define int long long
int n;
std::cin >> n;
std::vector<int> A(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i];
}
//x1表示上一个是奇数个,当前是偶数个
//x2表示上一个是偶数个,当前是奇数个
int x1 = 0, x2 = -1e18;
for (int i = 0; i < n; i++) {
int x = x1;
x1 = std::max(x1, x2 + 2 * A[i]);
x2 = std::max(x2, x + A[i]);
}
std::cout << std::max(x1, x2) << "\n";
}代码(Python):
def main():
n = int(input())
A = list(map(int, input().split()))
x1, x2 = 0, -1e18
for a in A:
x1, x2 = max(x1, x2 + a * 2), max(x2, x1 + a)
print(max(x1, x2))