Codeforces Round 996 (Div. 2)

A. Two Frogs

题目大意

长为n的线段上，A和B分别控制一颗棋子（给定初始位置ab），每次必须左或者右移动一步，二者不能重合，不能移动时输，问A先手能否必胜

解题思路

由于二者每次必须要移动，因此距离的奇偶性始终不变，只需要看二者距离奇偶性即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;std::cin >> t;while (t--) {int n, a, b;std::cin >> n >> a >> b;if (std::abs(a - b) % 2) {std::cout << "NO\n";} else {std::cout << "YES\n";}}
}

B. Crafting

题目大意

给你ab两个数组，你可以让i位置+1，然后所有其他位置都会-1，途中不能出现负数，问能否让所有 $a_i\ge b_i$

解题思路

先看有多少个地方不满足，如果超过一个，则显然不可能实现，因为会导致出现负数，对于只有一个的情况直接按照题意模拟看能否实现即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;std::cin >> t;while (t--) {int n;std::cin >> n;std::vector<int> a(n), b(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}for (int i = 0; i < n; i++) {std::cin >> b[i];}int cnt = 0, p;for (int i = 0; i < n; i++) {a[i] -= b[i];if (a[i] < 0) {cnt++;p = i;}}if (cnt == 0) {std::cout << "YES\n";} else if (cnt >= 2) {std::cout << "NO\n";} else {int f = 1;for (int i = 0; i < n; i++) {if (i != p) {a[i] += a[p];if (a[i] < 0) {f = 0;}}}if (f) {std::cout << "YES\n";} else {std::cout << "NO\n";}}}
}

C. The Trail

题目大意

给你一个n*m的数字矩阵，现在有一条（1，1）到（n，m）的路径被置零，让你填充这条路径，满足矩阵所有行列求和相等

解题思路

nx=mx，显然和为0的时候是一个答案，此后按照路径逐个填充即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int t;std::cin >> t;while (t--) {int n, m;std::cin >> n >> m;std::string s;std::cin >> s;std::vector<std::vector<i64>> g(n, std::vector<i64>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cin >> g[i][j];}}i64 x = 0, y = 0, sum = 0;for (int i = 0; i < n + m - 2; i++) {sum = 0;if (s[i] == 'D') {for (int j = 0; j < m; j++) {sum += g[x][j];}g[x][y] = -sum;x++;} else {for (int j = 0; j < n; j++) {sum += g[j][y];}g[x][y] = -sum;y++;}}sum = 0;for (int i = 0; i < n; i++) {sum += g[i][m - 1];}g[x][y] = -sum;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cout << g[i][j] << " \n"[j == m - 1];}}}
}

D. Scarecrow

题目大意

数轴n = 0处有一只乌鸦，此外还有n个稻草人在数轴上，他们每秒可以左右移动一个单位，如果x处的乌鸦非右侧y处有稻草人满足x-y<=k时，乌鸦会被传送到y+k处，问乌鸦要到大于l处的最短时间的两倍是多少

解题思路

乌鸦的移动方式只有两种，一种是左侧有稻草人隔k每次把乌鸦向右推1个单位，另一种稻草人到了乌鸦左侧k范围内把乌鸦向右弹k个单位
两倍时间等于两倍距离，所以可以把距离都翻倍再开始算，首先肯定是让最左侧的稻草人过来把乌鸦弹过去，因此初始化位置now=k，时间time=a0
对于在当前乌鸦位置左侧的稻草人，让稻草人从右边往左走到尽可能靠近乌鸦的位置看能不能把乌鸦弹出去（乌鸦的位置就是弹的最远的位置，所以要和now取min）；如果不行则只能让左侧的稻草人推着乌鸦走，并且右侧的稻草人移动过来，这个等待的时间是二者距离的一半，之后再弹k个单位如此往复直到右侧没有稻草人，最后再把目标位置和当前位置的差值加上即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t;std::cin >> t;while (t--) {i64 n, k, l;std::cin >> n >> k >> l;k *= 2, l *= 2;std::vector<i64> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];a[i] *= 2;}i64 now = k, time = a[0];for (int i = 1; i < n; i++) {if (a[i] <= now) {a[i] = std::min(a[i] + time, now);if (now - a[i] <= k) {now = a[i] + k;}continue;}if (a[i] - now > time) {i64 dist = a[i] - now - time;time += dist / 2;now += dist / 2;}now += k;}std::cout << time + std::min(0ll, l - now)<< "\n";}
}