题目

A.Balloon Trip

题目描述

给定整数 $W$ 和 $B$ ，解决以下问题。

Takahashi的权重为 $W {\rm [kg]}$ 。（注意单位为 ${\rm kg}$ ）

一个带有 $n$ 气球的物体，当且仅当该物体的质量严格小于 $nB$ ${\rm [g]}$ 时，才会飞向天空。

让高桥飞上天空最少需要多少个气球？

思路

语法题

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int x, y;
    cin >> x >> y;
    cout << 1000 * x / y + 1;
    return 0;
}

B.Bird Watching

题目描述

$N$ 有 $M$ 类的鸟在天空中飞翔。

鸟类类型编号为 $1,2,\dots,M$ 。

$N$ 鸟的编号为 $1,2,\dots,N$ ， $i$ 鸟的类型为 $A_i$ ，尺寸为 $B_i$ 。

对于每一个 $k=1,2,\dots,M$ ，求出类型为 $k$ 的飞鸟的平均大小。

可以保证，对于每一个 $k=1,2,\dots,M$ ，至少有一只类型为 $k$ 的鸟在飞行。

思路

语法题

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> cnt1(m + 1, 0);
    vector<int> cnt2(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        cnt1[x] += y;
        cnt2[x]++;
    }
    for (int i = 1; i <= m; i++) {
        cout << fixed << setprecision(7) << (double)cnt1[i] / (double)cnt2[i] << '\n';
    }
    return 0;
}

C.Flapping Takahashi

题目描述

高桥决定乘坐热气球在天空中飞行。高桥在 $0$ 时间处于 $H$ 高度 (单位为秒), 并将从现在开始飞行 $10^9$ 秒。

高桥可以每秒改变飞行高度 $1$ 。然而，他不能使飞行高度 $0$ 或更低。

换句话说，如果 $F(t)$ 表示高桥在 $t$ 时的高度，那么 $F(t)$ 满足以下所有条件：

$F(0) = H$
$-1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1$ 用于 $0 \leq t \lt u \leq 10^9$ 。
$F(t) \gt 0$ 用于 $0 \leq t \leq 10^9$ 。

关于海拔有 $N$ 目标。 $i$ 第四个目标是使海拔在 $t_i$ 时至少为 $l_i$ , 最多为 $u_i$ 。
高桥能否以一种实现所有目标的方式飞行？

给你提供了 $T$ 测试用例；请解决其中的每一个。

思路

直接维护每次到达每个目标的时候飞行的最大和最小高度，要是这两个东西满足最小高度大于最大高度就炸了，否则就更新两者的值。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = {x, {y, z}};
    }
    int ls = 0, minn = m, maxx = m;
    for (int i = 0; i < n; i++) {
        int x = a[i].first, y = a[i].second.first, z = a[i].second.second;
        minn -= x - ls;
        maxx += x - ls;
        minn = max({minn, 1LL, y});
        maxx = min(maxx, z);
        if (minn > maxx) {
            cout << "No" << '\n';
            return;
        }
        ls = x;
    }
    cout << "Yes" << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D.Clouds

题目描述

天空由 $2000 \times 2000$ 网格表示。
当抬头看天空时，从顶部数第四行 $r$ 和从左侧数第四列 $c$ 的单元格被称为 $(r,c)$ 。

目前，这片天空中飘浮着云 $1,2,\dots,N$ 。
单元格 $(r,c)$ 被云 $i$ 覆盖，当且仅当它满足 $U_i \le r \le D_i$ 和 $L_i \le c \le R_i$ 。

对于 $k=1,2,\dots,N$ , 请回答以下问题：

只从 $N$ 云中移除云 $k$ 。此时，天空中飘浮着 $N-1$ 云。有多少个单元格没有被任何云覆盖？

思路

不要像我一样犯唐刚读完题没看数据范围就去写扫描线然后这问题其实就没了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int pre1[2222][2222], pre2[2222][2222];
signed main()
{
    int n;
    cin >> n;
    vector<vector<int>> v;
    for (int i = 0; i < n; i++) {
        int u, d, l, r;
        cin >> u >> d >> l >> r;
        v.push_back({l, r, u, d});
        pre1[u][l]++;
        pre1[u][r + 1]--;
        pre1[d + 1][l]--;
        pre1[d + 1][r + 1]++;
    }
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j <= 2000; j++) {
            pre1[i][j] += pre1[i][j - 1];
        }
    }
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j <= 2000; j++) {
            pre1[i][j] += pre1[i - 1][j];
        }
    }
    int cnt = 0;
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j <= 2000; j++) {
            if (pre1[i][j] == 0) {
                cnt++;
            }
        }
    }
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j <= 2000; j++) {
            pre2[i][j] = pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1] + ((pre1[i][j] == 1) ? 1 : 0);
        }
    }
    for (int i = 0; i < n; i++) {
        int l = v[i][0], r = v[i][1], u = v[i][2], d = v[i][3];
        cout << cnt + pre2[d][r] - pre2[u - 1][r] - pre2[d][l - 1] + pre2[u - 1][l - 1] << '\n';
    }
    return 0;
}

E.Distribute Bunnies

题目描述

在数轴上有编号为 $1$ 到 $N$ 的 $N$ 只兔子。兔子 $i$ 在坐标 $X_i$ 。多个兔子可能在同一坐标。

每只兔子有一个参数叫跳跃能力，兔子 $i$ 的跳跃功率 $R_i$ 。

现在，所有的兔子都只跳一次。当坐标 $x$ 具有跳跃能力 $r$ 的兔子跳跃时，它移动到坐标 $x+r$ 或坐标 $x-r$ 。

如果你可以自由选择每只兔子跳跃到的坐标，找到所有兔子跳跃后兔子所在的最大可能的不同坐标。

思路

不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心不要贪心

我们可以把每一个兔子左右分别能跳到的位置离散化，并把他们在并查集中合并。所以对于每个并查集里的连通分量，能对答案产生的贡献就是边数和点数之间的最小值。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct DSU
{
    vector<int> fa, cnt1, cnt2;
    DSU(int n) {
        fa.resize(n + 1);
        cnt1.resize(n + 1, 1);
        cnt2.resize(n + 1, 0);
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
        }
    }
    int find(int x) {
        if (fa[x] == x) {
            return x;
        }
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            fa[x] = y;
            cnt1[y] += cnt1[x];
            cnt2[y] += cnt2[x] + 1;
        } else {
            cnt2[x]++;
        }
    }
};
signed main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x - y, x + y};
        v.push_back(a[i].first);
        v.push_back(a[i].second);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    DSU dsu(v.size());
    for (int i = 0; i < n; i++) {
        int tp1 = lower_bound(v.begin(), v.end(), a[i].first) - v.begin();
        int tp2 = lower_bound(v.begin(), v.end(), a[i].second) - v.begin();
        dsu.merge(tp1, tp2);
    }
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (dsu.find(i) == i) {
            ans += min(dsu.cnt1[i], dsu.cnt2[i]);
        }
    }
    cout << ans;
    return 0;
}

复盘

NOIPlus诗人