AtCoder Beginner Contest 318-摩杜云开发者社区

咕咕咕，总力战还没打，凹不过卷狗，躺了.jpg

A - Full Moon (abc318 A)

题目大意

给定\(n, m, p\)，问有多少个 \(i\)满足 \(0 < m+pi \leq n\)

解题思路

减去初始的\(m\)，剩下的就是看 \(p\)的倍数个数。

神奇的代码

#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, m, p;
    cin >> n >> m >> p;
    cout << (n - m) / p + (n >= m) << '\n';

    return 0;
}

B - Overlapping sheets (abc318 B)

题目大意

一个二维空间，有\(n\)个矩形覆盖。

问有多大的空间被覆盖了。重复覆盖算一次。

解题思路

空间大小只有\(100\)，矩形只有 \(100\)，对每个矩形直接 \(O(100^2)\)更新格子的覆盖情况，最后统计被覆盖的个数即可。

时间复杂度为 \(O(100^3)\)。

神奇的代码

#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;
    array<array<int, 101>, 101> tu{};
    while (n--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        for (int i = a; i < b; ++i)
            fill(tu[i].begin() + c, tu[i].begin() + d, 1);
    }
    int ans = 0;
    for (auto& i : tu)
        ans += count(i.begin(), i.end(), 1);
    cout << ans << '\n';

    return 0;
}

C - Blue Spring (abc318 C)

题目大意

\(n\)天旅行，第 \(i\)天旅行花费 \(f_i\)元。

你可以购买一日游券，可以免去任意一天的旅游费用。

但是一日游券是捆绑售卖的，你需要花 \(p\)元买 \(d\)张一日游券。这意味着你可以免去任意\(d\)天的旅游费用。你可以购买多次，最后一日游券可以剩余。

问旅游完 \(n\)天所需要的最小费用。

解题思路

假设我购买了\(x\)张一日游券，我肯定是免去旅游费用最高的那 \(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, d, p;
    cin >> n >> d >> p;
    vector<int> f(n);
    for (auto& i : f)
        cin >> i;
    sort(f.begin(), f.end(), greater<int>());
    LL sum = accumulate(f.begin(), f.end(), 0ll);
    LL ans = sum;
    for (int i = 0; i < n; i += d) {
        for (int j = i; j < min(n, i + d); ++j)
            sum -= f[j];
        sum += p;
        ans = min(ans, sum);
    }
    cout << ans << '\n';

    return 0;
}

D - General Weighted Max Matching (abc318 D)

题目大意

给定一张无向图，边有边权。要求选择一些边，最大化边权和，使得每条边的顶点不重复。

解题思路

点数只有\(16\)，考虑到每条边的顶点不能重复，那么当我们考虑某条边能不能选时，必须得知道目前已经选了哪些点，以决定这条边能不能选，因此设 \(dp[i]\)表示选择的点的情况是 \(i\)（二进制压缩的状态，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;
    cin >> n;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            int x;
            cin >> x;
            edge[i].push_back(x);
        }
    }
    vector<LL> dp((1 << n), 0);
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if ((~i >> j) & 1)
                continue;
            for (int k = j + 1; k < n; ++k) {
                if ((~i >> k) & 1)
                    continue;
                int w = edge[j][k - j - 1];
                dp[i] = max(dp[i], dp[i ^ (1 << j) ^ (1 << k)] + w);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';

    return 0;
}

E - Sandwiches (abc318 E)

题目大意

给定一个\(n\)个数的数组 \(a\)，问有多少个 \((i, j, k)\)，满足

\(i < j < k\)
\(a_i = a_k\)
\(a_i \neq a_k\)

解题思路

由于数有\(10^5\)，我们只能枚举其中一个。要么枚举 \(i\)要么枚举 \(j\)。分别考虑后发现枚举 \(j\)简单一点。

如果枚举下标\(i\)会发现比较难计算，对于当前的 \(a_i\)，那么对于之后的每个 \(a_k\)都要考虑它们之间的其他数的个数，感觉复杂度会比较大。

考虑枚举下标\(j\)，剩下的就是考虑 \(j\)左边和 \(j\)右边的相同数。这个\(j\)对答案的贡献就是 \(\sum_{x \neq a_j} l_{x} \times r_{x}\)，其中 \(l_x\)表示 \(j\)左边 \(x\)（是值，不是下标）的个数， \(r_x\)就是右边的 \(x\)的个数。

考虑当 \(j\)移动时，只有 \(a_j\)和 \(a_{j + 1}\)这两个数的个数发生变化。因此我们事先维护 \(\sum\)的值，\(\sum - l_{a_j} \times r_{a_j}\)就是此时的 \(j\)对答案的贡献。转移时通过加减那两个数的贡献，就得到 \(j\)移动到下一个数时的 \(\sum\)的值。然后累计就是答案了。

神奇的代码

#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<int> a(n);
    vector<int> l(n, 0), r(n, 0);
    for (auto& i : a) {
        cin >> i;
        --i;
        r[i]++;
    }
    LL ans = 0;
    LL tmp = 0;
    for (int i = 0; i < n; ++i) {
        tmp -= 1ll * l[a[i]] * r[a[i]];
        r[a[i]]--;
        ans += tmp;
        l[a[i]]++;
        tmp += 1ll * l[a[i]] * r[a[i]];
    }
    cout << ans << '\n';

    return 0;
}

F - Octopus (abc318 F)

题目大意

给定\(n\)个宝藏的位置，以及\(n\)只长度为 \(l_i\)的手。你要求合法的位置的个数。

一个位置\(x\)合法，意味着你可以用\(n\)只手拿到 \(n\)个宝藏。一只手只能拿一个宝藏，且拿的范围为 \([x - l_i, x + l_i]\)。

解题思路

考虑合法位置的情况，分三种，最左边，最右边，以及两个宝藏之间。

然后考虑最左边的种类，很显然，我们对手的长度进行从小到大排序，那就根据宝藏的坐标从小到大分配手。即对于第\(i\)个宝藏，分配的是长度为 \(l_i\)的手，那么能够及该宝藏的最左边的距离就是 \(x_i - l_i\)，对该距离取个最大值，就是最左边的合法位置了。

然后考虑这个合法位置不断往右边移动，在到达第一个宝藏的位置前都是合法位置。

然后合法位置到了第一个宝藏和第二个宝藏之间。考虑在这区间移动，我们的手分配宝藏的方案是不变的，直到第二个宝藏距离当前位置比第一个位置更近时，分配方案才发生变化，需要重新计算。

注意到需要重新计算的情况，是宝藏距离当前位置的排名发生了变化，因此手分配宝藏的方案需要改变，重新计算当前位置的合法性。而排名发生变化的位置被称为关键位置。

考虑这些关键位置在哪，既然是排名发生变化，那就是在某两个宝藏的中点，因此枚举左右两边宝藏，求个中点就能得到这些关键位置，注意到关键位置的数量只有\(O(n^2)\)个。

对于每个关键位置，重新计算下各个宝藏到该位置的距离，然后排个序分配手，在区间[当前关键位置，下一个关键位置-1]，其手的分配方案都不变，此时对于左边的宝藏，会有一个最小值 \(L = x_i + l_i\)，而对于右边的宝藏，会有个最大值 \(R = x_i - l_i\)，这之间的[R, L]就是合法位置的区间。

因此对所有这样的关键位置累计\(L - R + 1\)的值就是答案。总的时间复杂度是 \(O(n^3 \log n)\)。

神奇的代码

#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<LL> x(n), l(n);
    for (auto& i : x)
        cin >> i;
    for (auto& i : l)
        cin >> i;
    LL ans = 0;
    LL L = numeric_limits<LL>::min(), R = numeric_limits<LL>::max();
    for (int i = 0; i < n; ++i) {
        L = max(L, x[i] - l[i]);
        R = min(R, x[i] + l[n - i - 1]);
    }
    ans += max(0ll, x[0] - L);
    ans += max(0ll, R - x[n - 1] + 1);
    vector<int> id(n);
    vector<int> rk(n);
    iota(id.begin(), id.end(), 0);
    for (int i = 0; i < n - 1; ++i) {
        vector<LL> div{x[i]};
        for (int j = 0; j <= i; ++j) {
            for (int k = i + 1; k < n; ++k) {
                LL mid = (x[j] + x[k] + 1) / 2;
                if (mid > x[i] && mid < x[i + 1])
                    div.push_back(mid);
            }
        }
        sort(div.begin(), div.end());
        div.push_back(x[i + 1]);
        for (int k = 0; k < div.size() - 1; ++k) {
            LL mid = div[k];
            vector<LL> pos(n);
            for (int j = 0; j < n; ++j) {
                pos[j] = abs(x[j] - mid);
            }
            sort(id.begin(), id.end(), [&](int a, int b) {
                if (pos[a] != pos[b])
                    return pos[a] < pos[b];
                else
                    return a > b;
            });
            for (int j = 0; j < n; ++j)
                rk[id[j]] = j;
            L = div[k + 1] - 1, R = div[k];
            for (int j = 0; j <= i; ++j) {
                L = min(L, x[j] + l[rk[j]]);
            }
            for (int j = i + 1; j < n; ++j)
                R = max(R, x[j] - l[rk[j]]);
            ans += max(0ll, L - R + 1);
        }
    }
    cout << ans << '\n';

    return 0;
}

其实上面想复杂了（其实写也写复杂了，其实可以直接\(O(n^2)\)，枚举宝藏求中点，然后遍历所有关键点，上述这么写是因为当时考虑的每两个宝藏之间的情况，所以就一段一段的），不过是一个很朴素的从特殊位置开始的思路。

还是考虑关键位置，这个关键位置可以是两个宝藏的中点，它们的距离排名发生了变化；也可以是某个宝藏使用某只手的极限位置（即\(x_i - l_j\)和\(x_i + l_j\)，以这些极限距离作为分割点\(div_i\)，分别考虑每个分割点是否合法（同上面一样距离排序然后分配手），如果可以则代表 \([div_i, div_{i+1} - 1]\)都可以。可以参考jiangly的代码，但是正确性不太能理解，因为是以最优分配方式判断合法性，能保证这个区间都能取到最优方案吗（？

G - Typical Path Problem (abc318 G)

题目大意

给定一张简单无向图，问是否存在一个简单路径，从点\(a\)出发经过点 \(b\)到达点 \(c\)。

解题思路

题目可以转化成是否存在一棵生成树，其根为\(b\)，点 \(a\)和点 \(c\)的 \(lca\)是根，然后就一直在研究生成树，就不会了

神奇的代码

Ex - Count Strong Test Cases (abc318 Ex)

题目大意

<++>

解题思路

<++>

神奇的代码