中国矿山建设网站,网站运营工作计划,西安做seo的公司,大朗网站建设公司A-Coprime Pair
思路
我们知道两个质数之间并不会相隔太远#xff0c;于是我们直接用暴力就可以通过这题。
先从大到小枚举答案#xff0c;并且枚举所有可能的起点#xff0c;当枚举到的两个值满足条件输出并结束程序即可。
代码
#include bits/stdc.h
using n…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
思路
假设我们所能得到的分数的最大值为 ansmaxansmaxansmax 最小值为 ansminansminansmin 则答案一定为 max−min1max - min 1max−min1 因为每次多改变一个节点所能取到的分数只会改变一在整数情况下看他是连续的。
再稍微转换一下就会发现其实也就是求变换之后所能对原分数产生的改变的最大值和最小值的差。
于是我们将问题变为了如何求改变的最大值和最小值。
我们先将原数组按一下方式处理
如果 aia_iai 为 111 则将 bib_ibi 设为 −1-1−1如果 aia_iai 为 000 则将 bib_ibi 设为 111
此时的 bbb 数组记录的就是如果改变这个节点会对当前分数产生的影响。
我们再将 bbb 数组取一个前缀和此时 bbb 数组表示的就是从第一个节点到这个节点全部改变对分数产生的影响。
我们记录一个从起点开始改变所能得到分数的最大值为 maxnmaxnmaxn 最小值为 minnminnminn 。
我们从一开始枚举对于每个节点我们都将 ansmaxansmaxansmax 和 ansminansminansmin 更新一下然后更新一下 maxnmaxnmaxn 和 minnminnminn 就可以了。
更新方式看代码。
代码
#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
思路
我们先看最大两个点。
然后我们分情况讨论。
首先假设两个点之间的距离超过 111 此时如果我们将最大值移到次大值加一的位置后我们必赢则就移过去。
如果我们必输呢
因为我们移到次大值加一后对方必须移到前面一个空位处我们假设对方移到一个点 aaa 后我们必输则我们第一次移动就不移到次大值加一直接移到点 aaa 此时的局面和我们移到次大值加一的位置然后对方再移到点 aaa 是一样的因为这个局面先手的人必败所以我们移到点 aaa 后对方必败。
通过上面两种情况我们知道如果最大值和次大值之间的差大于一则无论如何先手必胜。
我们再看看最大值和次大值之间的差等于一的时候。
因为如果我们移到一个位置使得移完后这个节点到最大值之间有空格此时就会回到我们先前讨论的情况这是对方是必胜的。
于是我们和对方的每次移动都得要移到前面离最大值最近的空格。
于是我们可以根据空格数来判断谁赢。
如果空格数是偶数则最后一下是对方移动那我们必输。
如果空格数是奇数则最后一下是我们移动那我们必赢。
于是我们就可以做这道题了。
代码
#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;
}
