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\)替换成其他数，使得形成一个排列）
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 330beginner atcoder contest 330 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315