前言:
本文为Codeforces Round 971 (Div. 4) ABCD题的题解，包含C++,Python语言描述，觉得有帮助或者写的不错可以点个赞
比赛打了没一半突然unrated了就不是很想继续写了,早起写个题解
(之前的div3也没复盘，哎真菜)
目录
题A:
题目大意和解题思路:
给定两个整数 a 和 b (a ≤ b)。在所有可能的整数值 c (a ≤ c ≤ b) 中,找到 (c-a) + (b-c) 的最小值。
弱智题
代码(C++):
int main() {
#define int long long
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int a, b;
std::cin >> a >> b;
std::cout << b - a << "\n";
}
}代码(Python):
def main():
tt = int(input())
result = []
for _ in range(tt):
a, b = map(int, input().split())
result.append(b - a)
for res in result:
print(res)题B:
题目大意和解题思路:
你的谱面布局由 n 行和 4 列组成。因为底部的音符更接近,所以你会先处理最底部的行,最后处理最上面的行。每一行都会包含一个音符,用 '#' 表示。
对于每个音符 1, 2, ..., n,按照处理顺序,输出该音符出现的列。
从最下面开始，查找#的位置即可，注意输出的是位置不是下标
代码(C++):
int main() {
#define int long long
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int n;
std::cin >> n;
std::vector<std::string> A(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i];
}
for (int i = n - 1; i >= 0; i--) {
std::string s = A[i];
for (int j = 0; j < 4; j++) {
if (s[j] == '#') {
std::cout << j + 1 << " ";
break;
}
}
}
std::cout << "\n";
}
}代码(Python):
def main():
tt = int(input())
result = []
for _ in range(tt):
n = int(input())
A = [""] * n
for i in range(n):
A[i] = input()
res = []
for i in range(n - 1, -1, -1):
s = A[i]
for j in range(4):
if s[j] == "#":
res.append(j + 1)
break
result.append(res)
for res in result:
print(*res)题C:
题目大意和解题思路:
Freya 正在二维坐标平面上旅行。她现在位于点 (0,0) 并想到达点 (x,y)。在一次移动中,她选择一个整数 d,满足 0 ≤ d ≤ k,然后向她正在面对的方向跳 d 个格子。
最初,她面向正 x 方向。在每次移动后,她会在面向正 x 方向和正 y 方向之间交替(即,她的第二次移动会面向正 y 方向,第三次移动会面向正 x 方向,依此类推)。
要到达点 (x,y),她至少需要执行多少次移动?
有趣的小学数学题，卡了我一段时间
首先要确定的是，刚开始是向x方向移动，然后k是最大距离，移动距离可以为0，但是要计数
虽然是每次交替，但是可以这么想:，先把短的一边走完，再走长的一边，然后短的那一边移动距离0即可，那么最终答案就为长的一边的移动次数乘以2
求出x方向的最小移动次数d_x，y方向的最小移动次数d_y
求出最大的那一个乘以2即为答案，注意若是d_x * 2最大，那么需要-1，因为是先从x方向进行移动的
代码(C++):
int main() {
#define int long long
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int x, y, k;
std::cin >> x >> y >> k;
int d_x = (x + k - 1) / k;
int d_y = (y + k - 1) / k;
int res = std::max(d_x * 2 - 1, d_y * 2);
std::cout << res << "\n";
}
}代码(Python):
def main():
tt = int(input())
result = []
for _ in range(tt):
x, y, k = map(int, input().split())
d_x = (x + k - 1) // k
d_y = (y + k - 1) // k
res = max(d_x * 2 - 1, d_y * 2)
result.append(res)
for res in result:
print(res)题D:
题目大意和解题思路:
题目意思就是说，给你一些整数点，其中纵坐标y的值为0和1，然后让你求从这些点中选三个点组成直角三角形，一共有多少种选法
当 y 只取0和1的时候，可以理解成一个平行线，上面取三点，组成直角三角形
那么只有两种情况，一种是两点连成的直线垂直于平行线(也就是纵坐标相等的两个点)，加上两条平行线上面任意一点即可组成直角三角形
另外一种就是中间一个点，左边两个点..组成等腰直角三角形，如下图所示:长度必须满足下面情况
代码实现的话，统计纵坐标相等两点的情况，每种情况都会使得答案加上n - 2（点的个数-2）
第二种情况就查看是否对于每一个横坐标x,是否在对面平行线上x - 1和x + 1位置有点即可
我这里用哈希表暴力解
代码(C++):
int main() {
#define int long long
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int tt;
std::cin >> tt;
while (tt--) {
int n;
std::cin >> n;
std::unordered_map<int, int> cnt0, cnt1;
for (int i = 0; i < n; i++) {
int x, y;
std::cin >> x >> y;
if (y == 0) {
cnt0[x]++;
} else {
cnt1[x]++;
}
}
int res = 0;
for (auto& p : cnt0) {
int x = p.first;
if (cnt1.count(x)) {
res += (cnt1.size() + cnt0.size() - 2);
}
}
for (auto& p : cnt0) {
int x = p.first;
if (cnt1.count(x - 1) && cnt1.count(x + 1)) {
res++;
}
}
for (auto& p : cnt1) {
int x = p.first;
if (cnt0.count(x - 1) && cnt0.count(x + 1)) {
res++;
}
}
std::cout << res << "\n";
}
}代码(Python):
def main():
tt = int(input())
result = []
for _ in range(tt):
n = int(input())
cnt0 = defaultdict(int)
cnt1 = defaultdict(int)
for _ in range(n):
x, y = map(int, input().split())
if y == 0:
cnt0[x] += 1
else:
cnt1[x] += 1
res = sum((len(cnt1) + len(cnt0) - 2) for x in cnt0 if x in cnt1)
res += sum(1 for x in cnt0 if (x - 1 in cnt1 and x + 1 in cnt1))
res += sum(1 for x in cnt1 if (x - 1 in cnt0 and x + 1 in cnt0))
result.append(res)
for res in result:
print(res)