AtCoder Beginner Contest 330
A - Counting Passes (abc330 A)
题目大意
给定\(n\)个学生的分数，以及及格分 \(x\)，问多少人及格了。
解题思路
依次判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, l;
cin >> n >> l;
int ans = 0;
while (n--) {
int x;
cin >> x;
ans += (x >= l);
}
cout << ans << '\n';
return 0;
}
B - Minimize Abs 1 (abc330 B)
题目大意
回答\(n\)个问题，每个问题给定 \(a,l,r\)，问函数 \(f(x) = |x - a|\)在 \([l,r]\)的最小值。
解题思路
全定义域下，最小值显然在\(x=a\)取得。绝对值函数图像是\(V\)型。
现在限定在 \([l,r]\)，则分 \(a \leq l, a \geq r, l < a < r\)三种情况分别讨论极值即可。即分别在\(x=l, x=r, x=a\)取得最小值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, l, r;
cin >> n >> l >> r;
while (n--) {
int a;
cin >> a;
if (a <= l)
cout << l << ' ';
else if (a >= r)
cout << r << ' ';
else
cout << a << ' ';
}
return 0;
}
C - Minimize Abs 2 (abc330 C)
题目大意
给定\(d\)，问函数 \(f(x,y) = |x^2 + y^2 - d|\)的最小值。
解题思路
枚举\(x\)的取值，范围是\([1,2e6]\)，然后得 \(y^2 = abs(d - x * x)\)，分别取 \(y_1 = \lfloor \sqrt{y^2} \rfloor, y_2 = \lceil \sqrt{y^2} \rceil\)，由于会有一正一负的情况(\(x^2 + y_1^2 \leq d, x^2 + y_2^2 \geq d\))，取\(\min(f(x, y_1), f(x, y_2))\)，对所有 \(x\)取最小值即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL d;
cin >> d;
int up = 2e6;
LL ans = 1e18;
for (int i = 0; i <= up; ++i) {
LL x = 1ll * i * i;
LL y = abs(d - x);
LL y1 = floor(sqrt(y)), y2 = ceil(sqrt(y));
ans = min({ans, abs(x + y1 * y1 - d), abs(x + y2 * y2 - d)});
}
cout << ans << '\n';
return 0;
}
D - Counting Ls (abc330 D)
题目大意
给定一个包含ox的二维矩阵。问所有的满足下述条件的三元组下标数量。
- 这三个三元组对应的符号都是
o。 - 恰有两个三元组同一行。
- 恰有两个三元组同一列。
解题思路
三元组组成的图形都是形如
oo oo o o
o o oo oo
由此我们枚举转折点的o，由这个o组成的图形的数量就是\((row[i] - 1) \times (col[j] - 1)\) ，其中\(row[i],col[j]\)表示这个 o所在行和列的o的数量。累计所有的这些o即是答案。
注意答案可能会超int。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<string> s(n);
for (auto& i : s) {
cin >> i;
}
vector<int> col(n), row(n);
for (int i = 0; i < n; ++i) {
row[i] = ranges::count(s[i], 'o');
for (int j = 0; j < n; ++j)
col[i] += (s[j][i] == 'o');
}
LL ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'o') {
ans += 1ll * (row[i] - 1) * (col[j] - 1);
}
}
cout << ans << '\n';
return 0;
}
E - Mex and Update (abc330 E)
题目大意
给定一个数组\(a\)，进行如下操作。
每次操作 令\(a_i = x\)。然后输出 \(mex(a)\)。
\(mex(a)\)表示数组\(a\)未出现的最小非负整数。
解题思路
考虑如何求出一个数组的\(mex\)，我们可以记 \(visit[i]\)表示数字 \(i\)的出现次数，那每次求 \(mex\)可以从小到大遍历该数组，找到第一个出现次数为\(0\)的下标即是答案。
但这复杂度可能会高达 \(O(n)\)，考虑更快速的方法，我们可以用 \(set\)储存 \(visit\)数组中值为 \(0\)(未出现的数）下标，这样 \(set\)的最小值就是答案。
当\(a_i=x\)时，相当于把原来的 \(a_i\)删掉，即 \(visit[a_i]--\)，然后把 \(x\)加进来，即 \(visit[x]++\)，如果 \(visit[a_i]\)变为 \(0\)，则说明 \(a_i\)没有出现，将其插入到 \(set\)中。同时 \(visit[x]\)变为 \(1\)，说明 \(x\)出现了，从 \(set\)中删去。
这样就可以动态维护 \(mex\)值，其复杂度都是 \(O(log)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
map<int, int> cnt;
vector<int> ini(n + 1);
iota(ini.begin(), ini.end(), 0);
set<int> mex(ini.begin(), ini.end());
vector<int> a(n);
auto insert = [&](int i) {
int x = a[i];
cnt[x]++;
if (cnt[x] == 1)
mex.erase(x);
};
auto remove = [&](int i) {
int x = a[i];
cnt[x]--;
if (cnt[x] == 0)
mex.insert(x);
};
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
a[i] = x;
insert(i);
}
while (q--) {
int pos, x;
cin >> pos >> x;
--pos;
remove(pos);
a[pos] = x;
insert(pos);
cout << *mex.begin() << '\n';
}
return 0;
}
F - Minimize Bounding Square (abc330 F)
题目大意
二维平面，点，可进行最多\(k\)次操作，每次操作将一个点上下左右移动一格。点可以重叠。
问进行操作后，能将所有点覆盖的正方形的边长的最小值。
解题思路
两个维度相互独立，我们可以分别考虑每个维度。
考虑一维情况下，如果我们固定覆盖的线段长度，会发现比较好做。
注意到如果边长越大，我们需要的移动次数越少，可行的可能性就越高，相反，边长越小，需要移动的次数越多，可行的可能性就越低。这里有一个单调性，因此我们可以二分最终的边长。
边长固定了，考虑到最优情况下，覆盖的线段必定有一端点上的点是从来没移动过的，因此我们可以枚举这个作为边界的点。然后计算需要移动的次数。
坐标从小到大考虑，可以用双指针维护移动次数（一个前缀坐标和与一个后缀坐标和）。注意需要分别枚举作为左端点的点和作为右端点的点。
两个维度分别取所需移动次数的最小值，其和不超过\(k\)则边长可行。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
LL k;
cin >> n >> k;
vector<LL> x(n), y(n);
for (int i = 0; i < n; ++i)
cin >> x[i] >> y[i];
ranges::sort(x);
ranges::sort(y);
vector<LL> invx = x, invy = y;
ranges::reverse(invx);
ranges::reverse(invy);
int l = -1, r = 1e9 + 1;
auto ok = [&](int len, vector<LL>& p, int sign = 1) {
LL sufsum = accumulate(p.begin(), p.end(), 0ll);
LL presum = 0;
LL minn = 1e18;
int r = 0;
for (int i = 0; i < n; ++i) {
while (r < n && abs(p[r] - p[i]) <= len) {
sufsum -= p[r];
++r;
}
LL cnt = abs(p[i] * i - presum) +
abs(sufsum - (p[i] + sign * len) * (n - r));
minn = min(cnt, minn);
presum += p[i];
}
return minn;
};
auto check = [&](int len) {
return min(ok(len, invx, -1), ok(len, x)) +
min(ok(len, invy, -1), ok(len, y)) <=
k;
};
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
cout << r << '\n';
return 0;
}
G - Inversion Squared (abc330 G)
题目大意
给定一个数组\(a\)，仅包含 \(-1\)或者 \([1,n]\)，其中 \([1,n]\)中的数最多只出现一次。
计算满足以下条件的排列的逆序对的平方和。
- \(a_i \neq -1 => p_i = a_i\)。（即将 \(-1\)替换成其他数，使得形成一个排列）
解题思路
<++>
神奇的代码