Codeforces Round 969 (Div. 2) 题ABC详细题解，包含(C++,Python语言描述)
前言：
首先让我们恭喜tourist创造历史
他是第一，他又是第一，他总是第一，第一个codefores上4000分的，创造一个新的段位:Tourist，他的名字就是一个新的段位，他就是最高的山，最长的河
本文为Codeforces Round 969 (Div. 2)题ABC的详细题解，包含题目大意和解题思路，C++,Python两种语言编写，觉得有帮助或者写的不错可以点个赞
目录
题A:
题目大意和解题思路:
代码(C++):
代码(Python):
题B:
题目大意和解题思路:
代码(C++):
代码(Python):
题C:
题目大意和解题思路:
代码(C++):
代码(Python):
题A:
Problem - A - Codeforces
题目大意和解题思路:
题目意思就是说：在给定范围内的整数中，我们可以找到多少组三个数，这三个数两两之间的最大公约数都是1。每执行一次操作，就会从集合中移除三个数，然后找出最大的操作次数
取两个相邻的奇数，然后夹一个偶数即可，这样就可以保证操作次数最大
先统计奇数的数量，然后除以二即可
相邻的两个奇数，中间夹一个偶数，他们的最大公约数一定都是1
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int tt;std::cin >> tt;while (tt--) {int l, r;std::cin >> l >> r;int cnt = 0;for (int i = l; i <= r; i++) {if (i % 2 != 0) {cnt++;}}std::cout << cnt / 2 << "\n";}
}代码(Python):
def main():tt = int(input())res = []for _ in range(tt):l, r = map(int, input().split())cnt = 0for i in range(l, r + 1):if i % 2 != 0:cnt += 1res.append(cnt // 2)for r in res:print(r)题B:
Problem - B - Codeforces
题目大意和解题思路:
题目就是给一个数组，然后给两种操作，分别是 + l r 和 - l r
选择数组中满足小于等于l 且大于等于r 的元素加一(+)，或者减一(-)
最后输出数组中的最大值
我觉得B比A简单
关注数组中的最大值即可，如果最大值满足在[l, r]之间就对其进行加减操作
Q：为什么只用关注数组中的最大值？
A：可以这么考虑，假设有一个比最大值小的一个数x，无论l, r是多少，这个x最多只能等于最大值
代码(C++):
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int tt;std::cin >> tt;while (tt--) {int n, m;std::cin >> n >> m;int res = 0;for (int i = 0; i < n; i++) {int x;std::cin >> x;res = std::max(res, x);}while (m--) {char c;int l, r;std::cin >> c >> l >> r;if (l <= res && res <= r) {if (c == '-') {res--;} else {res++;}}std::cout << res << " ";}std::cout << "\n";}
}代码(Python):
def main():tt = int(input())res = []for _ in range(tt):n, m = map(int, input().split())x = max(list(map(int, input().split())))arr = []for _ in range(m):c, l, r = input().split()l, r = int(l), int(r)if l <= x <= r:if c == "-":x -= 1else:x += 1arr.append(x)res.append(arr)for r in res:print(*r)题C:
Problem - C - Codeforces
题目大意和解题思路:
给你一个数组，两个数字a和b，你可以对数组中任意一个元素操作任意次：加a或者加b
然后定义一个x = 数组最大值减最小值
现在进行任意操作，使得这个x最小，求出x的最小值
数学思维题，每次任意增加a和b，那么可以理解成每次增加的值，一定是gcd(a, b)的倍数h
要使得最大值和最小值的差值最小，每次增加h的若干倍数，那么只需要关注数组元素对h取余数的情况，余数相差最小的那两个数作为”最大值“和”最小值“
可以对数组每个数字取余数，然后排序，相邻两个数字之间的相差最小，那么这两个相邻数字就是要求的"最大值"和"最小值"，对其中一个数字加上h变成"最大值"即可
代码(C++):
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int tt;std::cin >> tt;while (tt--) {int n, a, b;std::cin >> n >> a >> b;std::vector<int> A(n);int h = gcd(a, b);for (int i = 0; i < n; i++) {std::cin >> A[i];A[i] %= h;}std::sort(A.begin(), A.end());long long res = A[n - 1] - A[0];for (int i = 0; i < n - 1; i++) {A[i] += h;res = std::min(res, (long long)(A[i] - A[i+1]));}std::cout << res << "\n";}
}代码(Python):
def gcd(a, b):while b != 0:a, b = b, a % breturn a
def main():tt = int(input())result = []for _ in range(tt):n, a, b = map(int, input().split())h = gcd(a, b)A = [int(x) % h for x in input().split()]A.sort()res = A[n - 1] - A[0]for i in range(0, len(A) - 1):A[i] += hres = min(res, A[i] - A[i + 1])result.append(res)for res in result:print(res)