A. Two Frogs
题意
n片荷花，给定两只青蛙的起始位置，轮流跳跃，从Alice开始。
要求：
- 青蛙可以向左或者向右跳一格，只能在n片荷花范围内
- 若一片荷花上有青蛙，不能跳到这片荷花上
Alice先跳，问都采用最优策略，Alice能否获胜。
分析
最优策略当然两者相向跳跃，挤压对方的生存空间。假如每个回合两只青蛙都能移动，则两者之间的距离的奇偶性不变。
若初始两者之间的距离为偶数，则Alice赢，否则输
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
void solve() {
int n, a, b;
cin >> n >> a >> b;
if (abs(a - b) % 2 == 1)cout << "No\n";
else cout << "Yes\n";
}
int main() {
int _;
cin >> _;
while (_--)solve();
}B. Crafting
题意
给定$n$个材料的已有个数$a_i$，和需要的个数$b_i$，可以将除$i$外的所有材料减一换取材料$i$加一，换句话说，选择材料 $i$ 后，更新数组 $a$ 如下： $a_i := a_i + 1 $，以及所有 j 中的 $j\neq i $和 $1\le j\le n $的 $a _ j := a _ j - 1$ 。$a_i$不能为负数。求是否经过一系列操作满足需要的材料个数。
分析
假设存在两个材料i，j都不满足需要的个数，若让i满足，则j要减少；让j满足，i要减少。故不可能同时满足两个。
故最多只能有一个材料不能满足要求。
除此之外其他的材料多出来的个数的最小值必须大于满足材料i的个数。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N];
void solve() {
int f=0;
int req=0;
int t=0x3f3f3f3f;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
for (int i = 0; i < n; ++i) {
if(b[i]<=a[i]){
t = min(t, a[i] - b[i]);
}else{
if(f==0){
f=1;
req = b[i] - a[i];
}else{
cout << "NO\n";
return;
}
}
}
if (req <= t) {
cout << "YES\n";
} else cout << "NO\n";
}
int main() {
int _;
cin >> _;
while (_--)solve();
}
C. The Trail
题意
给定一个矩阵，每个元素代表山的高度。删除其中从左上角到右下角的一条路径，这条路径只能向右或者向下移动。
已知这个矩阵的每行的和与每列的和都相等，求一个可能的方案填满此路径。
分析
假设n*m的矩阵，每行和每列的元素和都为x，则需要满足x*n==x*m
可知，若x==0，则可满足上式。
由于路径只能向下或者向右，考虑左上角的元素，若向右，则可由第一列算出元素值，反之可由第一行算出。
算出后填入，同样的手法处理下一个位置。
代码
这里使用的数据b，c提前存储了行和列的和，其实不需要，数据不大，再加一个循环算也可以。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 5;
char d[N];
int a[N][N];
int b[N], c[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n + m - 2; ++i) {
cin >> d[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
b[i] += a[i][j];
c[j] += a[i][j];
}
}
// if (n != m) {
int i = 0, j = 0;
for (int w = 0; w < n + m - 2; ++w) {
if (d[w] == 'D') {
a[i][j] = -b[i];
b[i] += a[i][j];
c[j] += a[i][j];
i++;
} else {
a[i][j] = -c[j];
b[i] += a[i][j];
c[j] += a[i][j];
j++;
}
}
a[i][j] = -b[i];
b[i] += a[i][j];
c[j] += a[i][j];
for (int i = 0; i < n; ++i) {
assert(b[i] == 0);
}
for (int i = 0; i < m; ++i) {
assert(c[j] == 0);
}
for (int k = 0; k < n; ++k) {
for (int l = 0; l < m; ++l) {
cout << a[k][l] << ' ';
}
cout << '\n';
}
}
signed main() {
int _;
cin >> _;
while (_--)solve();
}
D. Scarecrow
一只乌鸦位于数轴上的位置 0。数轴上还有 n 个稻草人，分别位于整数坐标 $a_1, a_2, \ldots, a_n$ 处。这些稻草人被施了魔法，可以以每秒 1 单位的速度左右移动。
乌鸦害怕稻草人，因此希望与位于或在其左侧的最近稻草人保持至少 k 的距离。为此，乌鸦使用其瞬间传送能力如下：
- 设 $x$ 为乌鸦的当前位置，$y $为满足 $y \le x$ 的稻草人的最大位置。如果 $x - y < k$，即稻草人距离太近，乌鸦将立即传送到位置 $y + k$。
这种传送是瞬间且持续进行的。乌鸦会不断检查位于或在其左侧的稻草人，并在稻草人距离过近时(可能在非整数时间点发生)进行传送。需要注意的是，除了这种传送能力外，乌鸦不会自行移动。
你的任务是确定乌鸦传送到位置大于或等于 $\ell$ 所需的最短时间，假设稻草人以最优方式移动以允许乌鸦达到目标。为了方便起见，你需要输出乌鸦到达目标位置 $\ell$ 所需最短时间的两倍。可以证明，这个值始终是整数。
需要注意的是，稻草人可以随时开始、停止或改变方向(可能在非整数时间点)。
分析
刚开始肯定是最左边的稻草人去找乌鸦，当稻草人移动到位置0时，乌鸦会立刻瞬移到位置k，此时左边的稻草人立刻向右移动，等价于推着乌鸦向右移动，故我们可以忽略乌鸦左边的稻草人，看作乌鸦一直向右移动即可。
乌鸦开始运动后，记运动的时间为t秒，最优的当然是瞬移后位移到下一个稻草人的身上，设瞬移后的位置为x，下一个稻草人的初始位置为y，考虑以下四种情况
- $y>x$，且$y-t\le x$，即刚开始在目标位置右边，t秒后可以经过目标位置
- $y<x$，且$y+t\ge x$，即刚开始在目标位置左边，t秒后可以经过目标位置
- $y>x$，且$y-t>x$，即刚开始在目标位置右边，t秒后不能到达目标位置
- $y<x$，且$y+t<x$，即刚开始在目标位置左边，t秒后不能到达目标位置
情况一，二，四都可以在此轮不增加时间，因为乌鸦会立刻瞬移到下一个位置。情况三要增加乌鸦和稻草人的相遇时间
代码
这里为了不产生小数，将刻度调整为0.5，即总体放大两倍
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int a[N];
void solve() {
int n, k, l;
cin >> n >> k >> l;
k *= 2;
l *= 2;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] *= 2;
}
int t = a[0];
int cur = k;
for (int i = 1; i < n; ++i) {
if (a[i] >= cur) {
if (a[i] - t <= cur) {
cur += k;
} else {
int w = a[i] - t - cur;
assert(w % 2 == 0);
t += w / 2;
cur = cur + w / 2 + k;
}
} else {
if (a[i] + t >= cur) {
cur += k;
} else {
cur = a[i] + t + k;
}
}
if (cur >= l) {
cout << t << endl;
return;
}
}
cout << t + l - cur << endl;
}
signed main() {
int _;
cin >> _;
while (_--)solve();
}
此处评论已关闭