AtCoder Beginner Contest 366

A - Election 2 (abc366 A)

题目大意

\(n\)张票,目前投了 \(t\)给高桥, \(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, t, a;
    cin >> n >> t >> a;
    if (t > a)
        swap(t, a);
    int left = n - t - a;
    if (t + left > a)
        cout << "No" << '\n';
    else
        cout << "Yes" << '\n';

    return 0;
}



B - Vertical Writing (abc366 B)

题目大意

给定\(n\)个字符串,把这 \(n\)个字符串顺时针旋转 \(90\)度,输出。

由于字符串长度不一,可能会出现 st的情况,前面的 都要替换成*

解题思路

手动旋转\(90\)度,然后对于每一行,从右往左,一旦碰到字符,后续再碰到 时,替换成 *即可。

神奇的代码
#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;
    int m = 0;
    vector<string> s(n);
    for (auto& i : s) {
        cin >> i;
        m = max(m, (int)i.size());
    }
    vector<string> t(m);
    reverse(s.begin(), s.end());
    for (int i = 0; i < m; ++i) {
        for (auto& j : s) {
            if (i < j.size()) {
                t[i] += j[i];
            } else {
                t[i] += ' ';
            }
        }
    }
    for (auto& i : t) {
        bool start = false;
        for (int j = i.size() - 1; j >= 0; --j) {
            if (i[j] != ' ') {
                start = true;
            }
            if (start && i[j] == ' ') {
                i[j] = '*';
            }
        }
    }
    for (auto& i : t)
        cout << i << '\n';

    return 0;
}



C - Balls and Bag Query (abc366 C)

题目大意

\(q\)个操作,分三种。

  • 1 x 放入背包一个球,数字\(x\)
  • 2 x 从背包拿出一个球,数字\(x\)
  • 3 问背包不同数字球的个数

解题思路

map维护一下各个数字球的个数,当\(map[x] = 0\)时移除该元素,询问就是 \(map.size()\)

神奇的代码
#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 q;
    cin >> q;
    map<int, int> cnt;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            cnt[x]++;
        } else if (op == 2) {
            int x;
            cin >> x;
            cnt[x]--;
            if (cnt[x] == 0)
                cnt.erase(x);
        } else {
            cout << cnt.size() << '\n';
        }
    }

    return 0;
}



D - Cuboid Sum Query (abc366 D)

题目大意

三维数组,回答\(q\)个询问,每个询问问一个三维区间和。

解题思路

维护一个三元前缀和,即可\(O(1)\)通过容斥原理得到一个三元区间的和。

至于如何容斥出来的,感受下二维的情况,三维就是\(2^3\)个项的相加减,公式即在代码里,其实就是\(\sum_{i=0}^{1} \sum_{j=0}^{1} \sum_{k=0}^{1} (-1)^{i+j+k} sum[x-len_x \times i][y-len_y \times j][z- len_z \times k]\)。这里\(x\)就是 \(rx\)\(x - \len_x\)就是 \(lx - 1\),其余字母同理。

神奇的代码
#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<vector<vector<int>>> a(
        n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
        }
    }
    vector<vector<vector<int>>> sum(
        n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                sum[i][j][k] = a[i][j][k] + sum[i - 1][j][k] +
                               sum[i][j - 1][k] + sum[i][j][k - 1] -
                               sum[i - 1][j - 1][k] - sum[i - 1][j][k - 1] -
                               sum[i][j - 1][k - 1] + sum[i - 1][j - 1][k - 1];
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int lx, rx, ly, ry, lz, rz;
        cin >> lx >> rx >> ly >> ry >> lz >> rz;
        int ans = sum[rx][ry][rz] - sum[lx - 1][ry][rz] - sum[rx][ly - 1][rz] -
                  sum[rx][ry][lz - 1] + sum[lx - 1][ly - 1][rz] +
                  sum[lx - 1][ry][lz - 1] + sum[rx][ly - 1][lz - 1] -
                  sum[lx - 1][ly - 1][lz - 1];
        cout << ans << '\n';
    }

    return 0;
}



E - Manhattan Multifocal Ellipse (abc366 E)

题目大意

二维平面。给定\(n\)个点\((x_i, y_i)\)

给定\(D\),问有多少个坐标 \((x,y)\),满足\(\sum_{i=1}^{n}(|x - x_i| + |y - y_i|) \leq D\)

解题思路

从求和式子可以看出\(x,y\)是相互独立的,\(\sum_{i=1}^{n}(|x - x_i| + |y - y_i|) = \sum_{i=1}^{n}|x - x_i| + \sum_{i=1}^{n}|y - y_i|) \leq D\),我们可以分别考虑 \(x,y\)轴的情况。

注意到点坐标范围只有 \([-10^6, 10^6]\) ,我们可以直接枚举\(x\)\(y\)的值,由于\(D \leq 10^6\),可以粗略算出来\(x,y\)的范围不会超过\([-2e6,2e6]\)

因此,我们直接枚举每个\(x\)\(-2e6\)\(2e6\),计算得到 \(\sum_{i=1}^{n}|x-x_i|\)的值 。而计算这个值可以\(O(1)\)\(O(\log n)\)算出来,即把绝对值去掉,即\(\sum_{x_i < x} (x - x_i) + \sum_{x_i \geq x}(x_i - x)\)。我们对\(x_i\)排序,然后可以二分\(x\)或者枚举\(x\)时动态维护这个边界点,同时维护前缀和presum后缀和sufsum,以及边界点前面的点数\(it\),那么 \(\sum_{x_i < x} (x - x_i) + \sum_{x_i \geq x}(x_i - x) = it * x - presum + sufsum - (n - it) * x\)

这样就算出了每个\(x\)\(\sum_{i = 1}^{n}|x - x_i|\),同理计算出每个 \(y\)\(\sum_{i=1}^{n}|y-y_i|\)

剩下的问题就是从\(x\)里选一个 \(\sum_x\),从 \(y\)里选一个 \(\sum_y\) ,有\(\sum_x + \sum_y \leq D\),有多少对。

这就是个经典问题,先对两个 \(\sum\)排序,然后依次枚举 \(\sum_x\),那么 \(\sum_y \leq D - sum_1\)的都是满足的,可以二分这个边界点,或者双指针维护一下得到满足条件的\(\sum_y\)的数量,累计即为答案。

神奇的代码
#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, d;
    cin >> n >> d;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
    auto solve = [&](vector<int>& a) {
        sort(a.begin(), a.end());
        vector<LL> dis;
        int up = 2e6;
        int it = 0;
        LL presum = 0, sufsum = accumulate(a.begin(), a.end(), 0ll);
        for (int i = -up; i <= up; ++i) {
            LL sum = 0;
            while (it < n && a[it] < i) {
                presum += a[it];
                sufsum -= a[it];
                ++it;
            }
            sum = 1ll * it * i - presum + sufsum - 1ll * (n - it) * i;
            if (sum < 0) {
                debug(i, presum, sufsum, sum);
            }
            dis.push_back(sum);
        }
        sort(dis.begin(), dis.end());
        return dis;
    };
    auto dis1 = solve(x);
    auto dis2 = solve(y);
    LL ans = 0;
    int it = dis2.size() - 1;
    for (auto i : dis1) {
        while (it >= 0 && dis2[it] + i > d)
            --it;
        ans += it + 1;
    }
    cout << ans << '\n';

    return 0;
}



F - Maximum Composition (abc366 F)

题目大意

给定\(n\)个一次函数 \(f_i(x) = a_ix + b_i\)

选择 \(k(\leq 10)\)个不同的一次函数,使得 \(f_{p_1}(f_{p_2}(...f_{p_k}(1)))\)最大。

解题思路

注意到\(a_i > 0, b_i > 0\),如果允许 重复选函数的话,因为\(x\)越大, \(f(x)\)越大,因此每次肯定选,使得\(f_i(x)\)值最大的函数\(f_i\) 。但这里不允许重复。

不允许重复,会产生什么问题呢?比如一个函数\(f_1(x) = 10x + 1\) ,另一个函数\(f_2(x) = x+9\),如果按照上述方法,结果就是\(f_2(f_1(1))=f_2(11) = 20\),然而反过来则是 \(f_1(f_2(1)) = f_1(10)=101\)。即函数 \(f_1\)虽然在第一步使用,可以得到最大的 \(f\),但后使用,可以变得更大。因此,如果最后我会选\(f_1\)\(f_2\)\(f_2\)会优先使用,\(f_1\)会后使用。

这里就出现了函数之间,选择的偏序(顺序)问题。这个偏序怎么定义呢?函数\(f_i,f_j\) ,如果\(f_i(f_j(x)) > f_j(f_i(x))\),则有 \(a_i(a_jx + b_j) + b_i\geq a_j(a_ix + b_i) + b_j\),我们把 \(i,j\)分离在一左一右,得到 \(\frac{a_i - 1}{b_i} \geq \frac{a_j - 1}{b_j}\)

这意味着说,如果\(\frac{a_i - 1}{b_i} \geq \frac{a_j - 1}{b_j}\),则\(f_i(f_j(x)) > f_j(f_i(x))\),即我先用\(f_j\),再用 \(f_i\)

有了这个函数使用的偏序有什么用呢?题目要使值最大,不仅要考虑选哪 \(k\)个函数,还要考虑这 \(k\)个函数复合的顺序。而现在我们已经有了一个最优复合顺序了,那剩下的问题就是选哪 \(k\)个函数。这其实就是一个选或不选的背包问题了。

先对 \(f_i\)按照 \(\frac{a_i - 1}{b_i}\)从小到大排序,然后设\(dp[i][j]\)表示考虑前 \(i\)个函数,已经使用了 \(j\)个函数的最大函数值。转移则考虑当前函数选或不选,从\(dp[i - 1][j-1]\)\(dp[i-1][j]\)转移即可。初始条件 \(dp[0][0] = 1\)

神奇的代码
#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, k;
    cin >> n >> k;
    vector<array<int, 2>> f(n);
    for (auto& [a, b] : f)
        cin >> a >> b;
    sort(f.begin(), f.end(),
         [](const array<int, 2>& a, const array<int, 2>& b) {
             auto& [a1, b1] = a;
             auto& [a2, b2] = b;
             return (a2 - 1) * b1 > (a1 - 1) * b2;
         });
    vector<LL> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        auto& [a, b] = f[i];
        vector<LL> dp2 = dp;
        for (int j = 1; j <= k; ++j) {
            dp2[j] = max(dp2[j], a * dp[j - 1] + b);
        }
        dp.swap(dp2);
    }
    cout << dp[k] << '\n';

    return 0;
}



G - XOR Neighbors (abc366 G)

题目大意

给定一张图,给每个点一个点权,使得每个点的邻居的点权异或和为\(0\)。给出方案,或告知不能。

解题思路

<++>

神奇的代码



热门相关:我真不是学神   梁医生又在偷偷套路我   与你相恋的小时光   神话版三国   妖魔哪里走