CF Round 920 (Div. 3) 笔记
前言
关于这个新系列，是我们的老师推荐给我们的。他说，多打 Codeforces 的比赛能增长我们的实战知识，提升我们的实力。我当然是非常相信的，因为老师说能提升 \(200\) 多分，从 \(\text{CSP-J }100\) 多分的蒟蒻变成 \(300\) 多分的大佬。那么，我会持续出 Codeforces 打虚拟赛的心得并坚持出这个系列，看看我会有怎样的收获和变化。（希望早日拿到蓝勾！）
本场比赛难度为 \(\text{Div.3}\)，据说稳定做出四道题是 \(\text{CSP-J }1=\) 水平。
战绩
\(\text{AC}\) 了前四题，第五题做出来一半，最后还是没有想出来平局的情况。
\(\text{Div.3}\) 做出来四题，好像还行？不过第四题在洛谷提前做过。
题目分析
\(\text{A}\) 题 \(\color{#FE4C61}\texttt{CF1921A Square}\)
题面概括
给定正方形四个点的坐标，正方形的边平行于 \(x\) 或 \(y\) 轴，求正方形面积。
赛时思路
既然是一个正方形，那么只要求出一条边的边长 \(a\)，就可以求得面积 \(a^2\)。那么我们只要找到两条 \(x\) 轴或 \(y\) 轴相等的点，再计算他们另一个维度的差，就可以了。\(x\) 轴或 \(y\) 轴相等意味着这两个点构成了一条边，而不是对角线。
\(\text{Code:}\)
#include <bits/stdc++.h>
using namespace std;
struct node {
int x, y;
}a[5];
int T;
int main() {
cin >> T;
while (T --) {
for (int i = 1; i <= 4; i++)
cin >> a[i].x >> a[i].y;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j < i; j++) {
if (a[j].x == a[i].x) {
cout << abs(a[j].y - a[i].y) * abs(a[j].y - a[i].y) << "\n";
goto nxt;
}
if (a[j].y == a[i].y) {
cout << abs(a[j].x - a[i].x) * abs(a[j].x - a[i].x) << "\n";
goto nxt;
}
}
}
nxt:;
}
return 0;
}
个人总结
考查的是平面几何计算。较为简单，比赛时最好的方法是把图画出来，能更直观地思考。
\(\text{B}\) 题 \(\color{#FE4C61}\texttt{CF1921B Arranging Cats}\)
题面概括
有两个字符串 \(f,b,f_i,b_i\in\{0,1\}\)。需要用最少的操作次数将 \(b\) 变为 \(f\)。有三种操作：
-
将 \(0\) 变为 \(1\)。
-
将 \(1\) 变为 \(0\)。
-
将两个不同字符交换位置。
赛时思路
先考虑比较简单的两种修改操作。我们可以想到，一位一位对比，只要不一样，就使用一次修改操作。
接着再考虑交换操作。发现交换操作是将两个位置的字符反转，即 \(1\) 变为 \(0\)，\(0\) 变为 \(1\)。这不就相当于做了两次修改操作吗？也就是说，一次交换操作可以替换两次修改操作。但是替换的是一个 \(0\) 变 \(1\)，一个 \(1\) 变 \(0\)，而不能是两个同一种操作，因为交换操作是将两个不同的数交换。
假设将 \(0\) 变为 \(1\) 的操作数为 \(\text{moveTo1}\)，将 \(1\) 变为 \(0\) 的操作数为 \(\text{moveTo0}\)，则两者重合的部分，即较小值为可以用交换操作解决的部分。两者之差为多出来的需要单独处理的部分，那么答案就是 \(\max\{\text{moveTo0,moveTo1}\}\)。
\(\text{Code:}\)
#include <bits/stdc++.h>
using namespace std;
int T;
int main() {
cin >> T;
while (T --) {
int n;
string b, f;
cin >> n >> b >> f;
int moveTo0 = 0, moveTo1 = 0;
for (int i = 0; i < n; i++) {
if (b[i] != f[i] && b[i] == '0') moveTo1++;
if (b[i] != f[i] && b[i] == '1') moveTo0++;
}
cout << max(moveTo0, moveTo1) << "\n";
}
return 0;
}
个人总结
比较简单的题，对于多种操作，可以先从简单的操作入手。
\(\text{C}\) 题 \(\color{#F39C11}\texttt{CF1921C Sending Messages}\)
题面概括
手机有 \(f\) 的电量，有 \(n\) 个消息要回复，第 \(i\) 个信息在 \(m_i\) 秒。可以选择一直开着机，每秒耗费 \(a\) 电量。也可以先关机，等到要回复的时候再开机。关机操作耗费 \(b\) 电量。问是否能回复所有的信息。
赛时思路
有两种操作，容易想到取消耗较小的一个。第 \(i\) 个信息遇上一个信息间隔的时间为 \(m_i-m_{i-1}\)，则开机的消耗为 \(a\cdot(m_i-m_{i-1})\)。关机的消耗为 \(b\)。我们只需在开机和关机两种情况中取最小值即可，一旦 \(f\) 小于等于 \(0\)，就没电了，输出 \(\texttt{NO}\)。直到最后如果手机还有电，输出 \(\texttt{YES}\)。
\(\text{Code:}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int T;
ll m[N];
int main() {
cin >> T;
while (T --) {
ll n, f, a, b;
cin >> n >> f >> a >> b;
for (int i = 1; i <= n; i++)
cin >> m[i];
bool flag = 1;
for (int i = 1; i <= n; i++) {
ll t = m[i] - m[i - 1];
if (t * a <= b) {
f -= t * a;
if (f <= 0) {
cout << "NO\n";
flag = 0;
break;
}
}
else {
f -= b;
if (f <= 0) {
cout << "NO\n";
flag = 0;
break;
}
}
}
if (flag) cout << "YES\n";
}
return 0;
}
\(\text{D}\) 题 \(\color{#F39C11}\texttt{CF1921D Very Different Array}\)
这道题打比赛之前居然做过。
题面概括
在 \(b\) 中选出 \(n\) 个数以任意顺序组成序列 \(c\)，使得 \(D=\sum _{i=1}^n \left\vert a_i-c_i \right\vert\) 最大。输出 \(D\) 即可。
赛时思路
容易想到用最值相减，即 \(a\) 的最大值减去 \(b\) 的最小值，或 \(b\) 的最大值减去 \(a\) 的最小值。容易发现这些数值在序列中是一一对应的，即 \(a_i\) 对应 \(b_{m-i+1}\)，同时也对应 \(b_{n-i+1}\)。取较大值即可。
\(\text{Code:}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll T, n, m, a[N], b[N];
int main() {
cin >> T;
while (T --) {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
ll ans = 0;
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
for (int i = 1; i <= n; i++)
ans += max(abs(a[i] - b[n - i + 1]), abs(a[i] - b[m - i + 1]));
cout << ans << "\n";
}
return 0;
}
小结
这次比赛整体不错，感觉打 CF 比赛确实会有进步。继续坚持吧！