AtCoder Regular Contest 137 题解（A~C）

A-Coprime Pair

思路

我们知道两个质数之间并不会相隔太远，于是我们直接用暴力就可以通过这题。

先从大到小枚举答案，并且枚举所有可能的起点，当枚举到的两个值满足条件输出并结束程序即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL x, y, ans;
LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }
int main() {scanf("%lld%lld", &x, &y);for (LL i = y - x; i; i--) {for (LL j = x; j + i <= y; j++) {if (gcd(j, j + i) == 1) {printf("%d", i);return 0;}}}return 0;
}

B-Count 1’s

思路

假设我们所能得到的分数的最大值为 $ansmax$ ，最小值为 $ansmin$ ，则答案一定为 $max-min+1$ ，因为每次多改变一个节点，所能取到的分数只会改变一，在整数情况下看他是连续的。

再稍微转换一下，就会发现，其实也就是求变换之后所能对原分数产生的改变的最大值和最小值的差。

于是我们将问题变为了如何求改变的最大值和最小值。

我们先将原数组按一下方式处理：

• 如果 $a_i$ 为 $1$ ，则将 $b_i$ 设为 $-1$
• 如果 $a_i$ 为 $0$ ，则将 $b_i$ 设为 $1$

此时的 $b$ 数组记录的就是如果改变这个节点，会对当前分数产生的影响。

我们再将 $b$ 数组取一个前缀和，此时 $b$ 数组表示的就是从第一个节点到这个节点全部改变对分数产生的影响。

我们记录一个从起点开始改变，所能得到分数的最大值为 $maxn$ ，最小值为 $minn$ 。

我们从一开始枚举，对于每个节点，我们都将 $ansmax$ 和 $ansmin$ 更新一下，然后更新一下 $maxn$ 和 $minn$ 就可以了。

更新方式看代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, a[300005], b[300005], maxn, minn, ansmax, ansmin;
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]), b[i] = b[i - 1] + (a[i] == 0 ? 1 : -1);for (int i = 1; i <= n; i++) {ansmax = max(ansmax, b[i] - minn);//b[i]-minn就是以当前节点为结尾所能产生的最大值ansmin = min(ansmin, b[i] - maxn);//b[i]-maxn就是以当前节点为结尾所能产生的最小值maxn = max(maxn, b[i]);minn = min(minn, b[i]);}printf("%d", ansmax - ansmin + 1);return 0;
}

C-Distinct Numbers

思路

我们先看最大两个点。

然后我们分情况讨论。

首先假设两个点之间的距离超过 $1$ ，此时如果我们将最大值移到次大值加一的位置后，我们必赢，则就移过去。

如果我们必输呢？

因为我们移到次大值加一后，对方必须移到前面一个空位处，我们假设对方移到一个点 $a$ 后我们必输，则我们第一次移动就不移到次大值加一，直接移到点 $a$ ，此时的局面和我们移到次大值加一的位置然后对方再移到点 $a$ 是一样的，因为这个局面先手的人必败，所以我们移到点 $a$ 后对方必败。

通过上面两种情况，我们知道如果最大值和次大值之间的差大于一，则无论如何先手必胜。

我们再看看最大值和次大值之间的差等于一的时候。

因为如果我们移到一个位置使得移完后这个节点到最大值之间有空格，此时就会回到我们先前讨论的情况，这是对方是必胜的。

于是我们和对方的每次移动都得要移到前面离最大值最近的空格。

于是我们可以根据空格数来判断谁赢。

如果空格数是偶数，则最后一下是对方移动，那我们必输。

如果空格数是奇数，则最后一下是我们移动，那我们必赢。

于是我们就可以做这道题了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, a[3000005];
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);if (a[n] - a[n - 1] > 1)printf("Alice");else {if ((a[n] - n) % 2)//a[n]-n就相当于空格数printf("Bob");elseprintf("Alice");}return 0;
}