A – Counting Passes (abc330 A)题目大意

给定\(n\)个学生的分数,以及及格分 \(x\),问多少人及格了。

解题思路

依次判断即可。

神奇的代码
#include 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 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 <= 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 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   oo   o oo oo

由此我们枚举转折点的o,由这个o组成的图形的数量就是\((row[i] – 1) \times (col[j] – 1)\) ,其中\(row[i],col[j]\)表示这个 o所在行和列的o的数量。累计所有的这些o即是答案。

注意答案可能会超int

神奇的代码
#include 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 s(n);    for (auto& i : s) {        cin >> i;    }    vector 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 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 cnt;    vector ini(n + 1);    iota(ini.begin(), ini.end(), 0);    set mex(ini.begin(), ini.end());    vector 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 > 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 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 x(n), y(n);    for (int i = 0; i > x[i] >> y[i];    ranges::sort(x);    ranges::sort(y);    vector invx = x, invy = y;    ranges::reverse(invx);    ranges::reverse(invy);    int l = -1, r = 1e9 + 1;    auto ok = [&](int len, vector& 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 > 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\)替换成其他数,使得形成一个排列)

解题思路

神奇的代码