Codeforces Round 981 (Div. 3) A - E 详细题解(C++)
本文为Codeforces Round 981 (Div. 3) A - E 详细题解，觉得有帮助或者写的不错可以点个赞
题A:
题目大意和解答思路:
代码(C++):
题B:
题目大意和解答思路:
代码(C++):
题C:
题目大意和解答思路:
代码(C++):
题D:
题目大意和解答思路:
代码(C++):
题E:
题目大意和解答思路:
代码(C++):
题A:
Problem - A - Codeforces
题目大意和解答思路:
有一个点初始在0的位置，第i次(从1开始)操作可以将点移动2 * i - 1的距离。
玩家S先手，负方向移动，K后手，正方向移动
然后给你一个数字n，表示当点移动出 [-n, n]的时候，最后一个是谁
n的大小为100，可以直接根据题目意思进行模拟
代码如下
void solve() {
int n;
std::cin >> n;
int x = 0;
int i = 1;
while (true) {
x -= (2 * i - 1);
if (abs(x) > n) {
std::cout << "Sakurako\n";
return;
}
i++;
x += (2 * i - 1);
if (abs(x) > n) {
std::cout << "Kosuke\n";
return;
}
i++;
}
}但是可以很容易的发现，先手的S总是向负方向移动，后手的K总是向正方向移动，每次移动的距离为2 * i - 1，从1开始的奇数，所以可以把每次移动点的位置写下来：
-1， 2， -3， 4....
可以发现负方向都是奇数，正方向都是偶数，由于奇数是先手的，那么当n为奇数的时候，负方向会先超过[-n, n],以此可以写出O(1)的代码
代码(C++):
void solve() {
int n;
std::cin >> n;
std::cout << (n % 2 == 0 ? "Sakurako\n" : "Kosuke\n");
}题B:
Problem - B - Codeforces
题目大意和解答思路:
这题给你一个长度为n的矩阵，由正数和负数组成
现在你可以进行下面的操作：
选择一个子矩阵，把这个子矩阵的主对角线，就是从左上到右下角的那一条对角线的所有元素加1
现在询问你，最少需要多少次操作才能使得矩阵中没有负数
这个题目读懂后还是比较简单的，每次都是对角线的元素增加1，那么可以把所有的”对角线“中的最小值找出来，然后就是答案就是所有的最小值相加
具体过程，我们可以发现，这种满足”对角线“性质的，i - j是相同的，那么可以使用一个map进行存储
代码(C++):
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> A(n, std::vector<int> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> A[i][j];
}
}
std::map<int, int> mp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mp[i - j] = std::min(mp[i - j], A[i][j]);
}
}
i64 res = 0;
for (auto [_, val] : mp) {
res -= val;
}
std::cout << res << "\n";
}题C:
Problem - C - Codeforces
题目大意和解答思路:
题目意思就是说，给你一个数组，你可以交换对称位置的元素，比如第一个跟最后一个交换
可以交换任意次
然后使得数组里面相邻的数字个数最小
这个可以用dp的，但是不用这么麻烦
可以从题目的角度出发，想想每次交换会变什么
交换这个数字前，统计这个位置和交换后位置的”相邻数字个数“总和
交换数组后，再统计一次
对比这两个数字来确定此次交换是否进行即可
最后统计相邻数字个数即可，直接看代码实现
代码(C++):
void solve() {
int n;
std::cin >> n;
std::vector<int> A(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i];
}
for (int i = 1; i < n / 2; i++) {
int c0 = (A[i] == A[i - 1]) + (A[n - i - 1] == A[n - i]);
std::swap(A[i], A[n - i - 1]);
int c1 = (A[i] == A[i - 1]) + (A[n - i - 1] == A[n - i]);
if (c0 < c1) {
std::swap(A[i], A[n - i - 1]);
}
}
int res = 0;
for (int i = 0; i < n - 1; i++) {
res += (A[i] == A[i + 1]);
}
std::cout << res << "\n";
}题D:
Problem - D - Codeforces
题目大意和解答思路:
D题按理说是比C题简单很多的，因为比较常规，但是我用了unordered_map,被hack了。。
这个题目定义了一个最美丽的片段：
一段[l, r] 的区间和为0就是最美丽片段
然后让你求出数组中，最多能有多少个不重叠的最美丽片段
贪心+前缀和+两数之和套路(枚举右，维护左)
可以先求出一个前缀和数组prefix_sum，然后[l, r]之间的和就是prefix_sum[r] - prefix_sum[r]
遍历前缀和数组，再用一个哈希表维护找寻差为0的
要使得不重叠片段最多，那么往后遍历，每找到一个片段就算一个
可以再优化一下空间，不需要前缀和数组，直接用一个变量加当前数组的和即可
找到一个区间即可清空哈希表，因为这一段是不重合的区间
还有要注意的就是需要mp[0] = 1,因为单独的0也算
代码(C++):
void solve() {
int n;
std::cin >> n;
std::vector<int> A(n);
for (int i = 0; i < n; i++) {
std::cin >> A[i];
}
std::map<i64, int> mp;
int res = 0;
i64 sum = 0;
mp[0] = 1; //注意这一步
for (int i = 0; i < n; i++) {
sum += A[i];
if (mp.count(sum)) {
res++;
mp.clear();
mp[0] = 1;
sum = 0;
continue;
}
mp[sum]++;
}
std::cout << res << "\n";
}题E:
Problem - E - Codeforces
题目大意和解答思路:
给你一个数组，你可以交换任意两个元素，使得数组中所有元素满足下面的一个条件即可：
p_i = i
p_(pi) = i
让你找出最小交换次数
既然是可以进行交换实现要求的，那么数组元素肯定满足由1 ~ n这n个元素组成
那么可以建立一个全部元素满足条件2的数组P
就是P[A[i]] = i
可以对每一个i进行维护, 如果此时的i既不满足条件1也不满足条件2
那么就A[A[i]] 和 A[P[i]] 进行交换使得此时的i满足条件
i 要么直接到达正确位置，要么满足 ppi = i 的条件
这种方法每次交换都至少让一个元素满足，所以是最小的
代码(C++):
void solve() {
int n;
std::cin >> n;
std::vector<int> A(n + 1), P(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> A[i];
P[A[i]] = i;
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (A[i] != i && A[A[i]] != i) {
int p = A[A[i]], p2 = i;
std::swap(A[A[i]], A[P[i]]);
std::swap(P[p], P[p2]);
res++;
}
}
std::cout << res << "\n";
}