CF1857 Div.3 A~F 题解

本文主要是介绍CF1857 Div.3 A~F 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章较长，点个赞支持作者吧！！！

CF1857A

luogu题目链接
codeforces题目链接

分析

由于 $奇数 + 奇数 = 偶数, 偶数 + 偶数 = 偶数$ ，所以我们只需判断 $a$ 数组的总和是否为偶数即可。

代码

代码过于简单不放了……

CF1857B

luogu题目链接
codeforces题目链接

分析

既然要求值最大，那么越高位肯定越要进位，如果当前位要进位必须是当前位 $\ge 5$ ，或者是当前位及后面连续一段都是 $4$ ，且段的末尾的后一个位 $\ge 5$ ，模拟即可。

代码

有点长，放出来占篇幅……

CF1857C

luogu题目链接
codeforces题目链接

分析

考虑将数组 $b$ 升序排序，因为最小值跟其他数取 $\min$ 必然是最小值，所以 $b_1$ 一定是最小值，在把最小值去掉，重复以上操作即可，最大值是任何数都行，最好取到 $10^9$ 。

设 $m=\frac{n\times (n-1)}{2}$ 由于最小值出现了 $n - 1$ 次，次小值出现了 $n - 2$ 次，所以可以按照代码里那样输出答案，具体看代码。

代码

# include <bits/stdc++.h> using namespace std;
using PII = pair <int, int>;const int N = 5e5 + 5;
int T, n, b[N];signed main () {for (cin >> T; T; T --) {cin >> n;int len = n;n = n * (n - 1) / 2;for (int i = 1; i <= n; i ++) {cin >> b[i];}sort (b + 1, b + n + 1);for (int i = 1, j = 1; i <= n; i += len - j, j ++) {cout << b[i] << " ";}cout << "1000000000\n";}return 0;
}

CF1857D

luogu题目链接
codeforces题目链接

分析

一个很常见的套路：先将相同的放在一起，先对式子移项： $a_u-a_v\ge b_u-b_v\to a_u-b_u\ge a_v-b_v$ ，发现只有 $a_i-b_i$ 最大的 $i$ 才能向所有点连边所以统计最大值，输出即可。

代码

# include <bits/stdc++.h> 
# define int long longusing namespace std;
using PII = pair <int, int>;
const int N = 1e5 + 5, inf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;int T, n, a[N], b[N];signed main () {for (cin >> T; T; T --) {scanf ("%lld", &n);for (int i = 1; i <= n; i ++) {scanf ("%lld", &a[i]);} for (int i = 1; i <= n; i ++) {scanf ("%lld", &b[i]);} int maxn = -linf, cnt = 0;for (int i = 1; i <= n; i ++) {maxn = max (maxn, a[i] - b[i]);}for (int i = 1; i <= n; i ++) {if (a[i] - b[i] == maxn) {cnt ++;}} printf ("%lld\n", cnt);for (int i = 1; i <= n; i ++) {if (a[i] - b[i] == maxn) {printf ("%lld ", i);}} printf ("\n");}return 0;
}

CF1857E

luogu题目链接
codeforces题目链接

分析

发现点被覆盖的次数的和其实就是每个 $p_i$ 连出的线段的长度和。

先对 $p$ 数组升序排序，发现如果从点 $p_i$ 换到点 $p_{i+1}$ ，就是 $p_{i+1}$ 左边的所有点都增加了 $p_{i+1}$ 到 $p_i$ 这一段，所有 $p_{i+1}$ 右边的（包括 $p_{i+1}$ ）都减少了 $p_{i+1}$ 到 $p_i$ 这一段，统计前缀和和后缀和计算即可。

代码

# include <bits/stdc++.h> 
# define int long long
# define x first
# define y secondusing namespace std;
using PII = pair <int, int>;
const int N = 5e5 + 5, inf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;PII a[N];
int T, n, ans[N], fsum[N], bsum[N];signed main () {for (cin >> T; T; T --) {scanf ("%lld", &n);for (int i = 1; i <= n; a[i].y = i, i ++) {cin >> a[i].x;}sort (a + 1, a + n + 1);fill (bsum + 1, bsum + n + 2, 0);for (int i = 1, j = n; i <= n; i ++, j --) {fsum[i] = fsum[i - 1] + a[i].x;bsum[j] = bsum[j + 1] + a[j].x;}for (int i = 1; i <= n; i ++) {int t = a[i].x * (i - 1) - fsum[i - 1] - 1 + bsum[i + 1] - a[i].x * (n - i) + n + 1;ans[a[i].y] = t;}for (int i = 1; i <= n; i ++) {cout << ans[i] << " ";}cout << '\n';}return 0;
}

CF1857F

luogu题目链接
codeforces题目链接

分析

首先可以由第一个条件知道 $x-a_i=a_j$ ，那么第二个条件就变成了 $a_i(x-a_i)=y$ ，把括号 OK 掉即为 ${a_i}^2+a_ix=y$ ，也就是 ${a_i}^2+xa_i-y=0$ ，发现是一个一元二次方程，写出公式：

$ans:\frac{x\pm \sqrt{x^2-4y}}{2}$

计算即可，用 map 统计每个数出现的次数，假设求出来的两个答案为 $a, b$ ，则 $mp_a \times mp_b$ 即为答案，若求出来的答案相等则 $mp_a \times (mp_a-1)/2$ 为答案。

注意特判如果 $\Delta=x^2-4y$ 为 $0$ 则此时无解，或求出来的答案不满足条件也无解，此时答案都为 $0$

代码

# include <bits/stdc++.h> 
# define int long longusing namespace std;
// using ll = long long;
using PII = pair <int, int>;const int N = 2e5 + 5;
int T, n, q, x, y, a[N];
map <int, int> mp;int getans () {int d = x * x - 4 * y;int a = (x - sqrt (d)) / 2, b = (x + sqrt (d)) / 2;if (d < 0 || a + b != x || a * b != y) {return 0;} if (a == b) {return mp[a] * (mp[a] - 1) / 2;}return mp[a] * mp[b];
}signed main () {for (cin >> T; T; T --) {mp.clear();cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];mp[a[i]] ++;}for (cin >> q; q; q --) {cin >> x >> y;cout << getans () << ' ';}cout << '\n';}return 0;
}