链接：https://atcoder.jp/contests/abc434

A – Balloon Trip

算法：

    数学。

思路：

    无。

关键代码：

void miyan()
{
    int w, b;
    cin >> w >> b;

    w *= 1000;

    cout << w / b + 1 << endl;
}

B – Bird Watching

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int m, n;
    cin >> n >> m;

    map<int, vector<int>> hash;
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        hash[x].push_back(y);
    }

    for (auto [_, v] : hash)
    {
        double sum = 0;
        for (auto x : v)
            sum += x;

        printf("%.10lf\n", sum / v.size());
    }
}

C – Flapping Takahashi

算法：

    模拟。

思路：

    维护可行区间。

关键代码：

void miyan()
{
    int n, h;
    cin >> n >> h;

    int last = 0;
    int L = h, R = h;
    bool ok = 1;
    while (n--)
    {
        int t, l, u;
        cin >> t >> l >> u;

        if (!ok)
            continue;

        int cur = t - last;
        last = t;

        L = max(1, L - cur);
        R += cur;

        L = max(L, l);
        R = min(R, u);

        if (L > R)
            ok = 0;
    }

    if (ok)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

D – Clouds

算法：

    二分差分，二维前缀和。

思路：

    移去某一朵云后只有只被这朵云覆盖的格子才会变为未覆盖。

    对于给定的 \(n\) 朵云，二维差分维护覆盖范围。

    再统计出只被一朵云覆盖的点，然后进行二维前缀和维护，这样就可以 \(O(1)\) 求出只被当前云覆盖的点。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    vector b(2002, vector<int>(2002, 0));
    vector<array<int, 4>> a(n);
    for (int i = 0; i < n; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        a[i] = {x1, y1, x2, y2};

        ++b[x1][y1];
        --b[x2 + 1][y1];
        --b[x1][y2 + 1];
        ++b[x2 + 1][y2 + 1];
    }

    for (int i = 1; i <= 2000; ++i)
        for (int j = 1; j <= 2000; ++j)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    int sum = 0;
    vector cnt(2002, vector<int>(2002, 0));
    for (int i = 1; i <= 2000; ++i)
    {
        for (int j = 1; j <= 2000; ++j)
        {
            if (b[i][j])
                ++sum;
            if (b[i][j] == 1)
                cnt[i][j] = 1;
        }
    }

    for (int i = 1; i <= 2000; ++i)
        for (int j = 1; j <= 2000; ++j)
            cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];

    for (int i = 0; i < n; ++i)
    {
        auto [x1, y1, x2, y2] = a[i];

        int cur = cnt[x2][y2] - cnt[x1 - 1][y2] - cnt[x2][y1 - 1] + cnt[x1 - 1][y1 - 1];

        cout << 2000 * 2000 - sum + cur << endl;
    }
}

E – Distribute Bunnies

算法：

    图论，并查集。

思路：

    数轴上的点可以看做是节点。

    一只兔子看做一条边，一个为 \(<x, r>\) 的兔子连接 \(x – r\) 和 \(x + r\) 两点。

    此时问题就转化为：在一张图中每条边必须选择一个节点，最多选多少节点。

    不难发现在一个连通块中，最多选择点的个数 \(= min(v, e)\)，既连通块点数和边数的最小值。

    维护一个带权并查集，点的值域很大需要离散化一下。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    vector<pii> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].first >> a[i].second;

    unordered_map<int, int> hash;
    int idx = 1;
    for (int i = 0; i < n; ++i)
    {
        auto [x, r] = a[i];

        if (!hash.count(x))
            hash[x] = idx++;
        if (!hash.count(x - r))
            hash[x - r] = idx++;
        if (!hash.count(x + r))
            hash[x + r] = idx++;
    }

    vector<int> p(n * 4 + 10);
    vector<int> poi(n * 4 + 10);
    vector<int> edg(n * 4 + 10, 0);
    for (int i = 1; i < n * 4 + 10; ++i)
    {
        p[i] = i;
        poi[i] = 1;
    }

    auto find = [&](auto &&self, int x) -> int
    {
        if (x != p[x])
            p[x] = self(self, p[x]);

        return p[x];
    };

    for (int i = 0; i < n; ++i)
    {
        auto [x, r] = a[i];

        int xl = hash[x - r], xr = hash[x + r];

        xl = find(find, xl), xr = find(find, xr);

        if (xl != xr)
        {
            p[xl] = xr;
            poi[xr] += poi[xl];
            edg[xr] += edg[xl];
        }

        ++edg[xr];
    }

    ll ans = 0;
    for (int i = 1; i < n * 4 + 10; ++i)
        if (p[i] == i)
            ans += min(poi[i], edg[i]);

    cout << ans << endl;
}

F – Concat (2nd)

    还没补。