2025-06-28-sol

Lyccrius · 2025-06-28 10:07:24 · 题解

A 植树节

30pts

a_i, b_i, n \le 10^3

直接使用数组模拟每棵树苗的浇水次数，每次浇水在浇水区间内循环修改。

时间复杂度 \mathcal O(n^2)。

40pts

a_i = b_i

每次浇水区间长度为一，同样直接数组模拟即可，代码与上面相同。

50pts

a_i = 1, b_i = 10^3

每次浇水区间左右端点完全相同，故 1 \sim 10^3 的树苗浇水次数完全相同，只记录一次即可。

100pts

注意到区间修改单点查询，且先修改后查询，使用差分维护序列即可。

时间复杂度 \mathcal O(n)。

#include <iostream>
#include <algorithm>

const int maxN = 1e5;
const int maxA = 1e6;

int n;
int l = maxA, r = 1;
int a[maxN + 10], b[maxN + 10];
int c[maxA + 10], s[maxA + 10];
int ans;

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i] >> b[i];
        l = std::min(l, a[i]);
        r = std::max(r, b[i]);
        c[a[i]] += 1;
        c[b[i] + 1] -= 1;
    }
    for (int i = l; i <= r; i++) {
        s[i] = s[i - 1] + c[i];
        ans = std::max(ans, s[i]); 
    }
    std::cout << ans << std::endl;
    return 0; 
}

B 宴会

30pts

n \le 100, 0 \le x_i, t_i \le 1000

注意到数据范围非常小，直接上暴力。

在 0 \sim 1000 上枚举每一个 x_0，每次统计所有人到大宴会的时间的最大值座位宴会开始时间，取宴会开始时间最小的 x_0 作为答案。

时间复杂度 \mathcal O(nx)。

100pts

保证所有测试数据的 n 加起来不超过 2 \times 10^5。

数据范围提示时间复杂度为 \mathcal O(n)。

为了更加直观清晰，首先将答案进行一个数学上的形式化表示，即找到一个 x_0，使得 \max(\lvert x_i - x_0 \rvert + t_i) 最小。

• 当 x_i \lt x_0 时，\lvert x_i - x_0 \rvert + t_i = - x_i + x_0 + t_i = x_0 - (x_i - t_i) = \lvert x_0 - (x_i - t_i) \rvert，即 x_0 到 x_i - t_i 的距离；
• 当 x_i \gt x_0 时，\lvert x_i - x_0 \rvert + t_i = x_i - x_0 + t_i = (x_i + t_i) - x_0 = \lvert x_0 - (x_i + t_i) \rvert，即 x_0 到 x_i + t_i 的距离。

到这里 x_i 本身已经对答案不产生影响了，只考虑 x_i - t_i 及 x_i + t_i 即可。

由于我们只需要考虑 x_0 到这些 x_i - t_i 及 x_i + t_i 的最大值，那么我们只需要考虑最小的 x_i - t_i 及最大的 x_i + t_i 即可。

要让 x_0 到最小的 x_i - t_i 及 最大的 x_i + t_i 的距离的最大值最小，显然应当最小的 x_i - t_i 及最大的 x_i + t_i 的中点作为 x_0。

答案即 \frac{\min \{ x_i - t_i \} + \max \{ x_i + t_i \} }{2}，时间复杂度 \mathcal O(n)。

#include <iostream>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <cmath>

const int maxN = 1e5;
const int maxX = 1e8;

int T;
int n;
int x[maxN + 10];
int t[maxN + 10];
int l, r;

void init() {
    l = maxX;
    r = 0;
    return;
}

void mian() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> x[i];
    for (int i = 1; i <= n; i++) std::cin >> t[i];
    for (int i = 1; i <= n; i++) l = std::min(l, x[i] - t[i]);
    for (int i = 1; i <= n; i++) r = std::max(r, x[i] + t[i]);
    if ((l + r) % 2) {
        std::cout << std::fixed << std::setprecision(1) << (1.0 * l + r) / 2 << std::endl; 
    } else {
        std::cout << (l + r) / 2 << std::endl;
    }
    return;
}

int main() {
    std::cin >> T;
    while (T--) init(), mian();
    return 0;
}

其他做法

二分法

三分法

调整法

C 部署

#include <iostream>

const int maxN = 1e6;
const int maxM = 1e6;
const int maxQ = 1e6;
const int maxA = 1e9;
const int maxX = maxN;
const int maxY = 10;

int n, m, q;
int a[maxN + 10];
int p, x, y;

namespace graph {
    struct Vertex {
        int val;
        int tag1;
        int tag2;
        int head;
    } vertex[maxN + 10];

    struct Edge {
        int head;
        int next;
    } edge[2 * maxN + 10];

    int ecnt;

    void addEdge(int tail, int head) {
        ecnt++;
        edge[ecnt].head = head;
        edge[ecnt].next = vertex[tail].head;
        vertex[tail].head = ecnt;
        return;
    }

    void pushDown1(int u, int from) {
        for (int e = vertex[u].head; e; e = edge[e].next) {
            int v = edge[e].head;
            if (v == from) continue;
            vertex[v].val += vertex[u].tag1; 
            vertex[v].tag1 += vertex[u].tag1;
        }
        vertex[u].tag1 = 0;
        return;
    }

    void pushDown2(int u, int from) {
        for (int e = vertex[u].head; e; e = edge[e].next) {
            int v = edge[e].head;
            vertex[v].val += vertex[u].tag2;
        }
        return;
    }

    void DFS(int u, int from) {
        pushDown1(u, from);
        pushDown2(u, from);
        for (int e = vertex[u].head; e; e = edge[e].next) {
            int v = edge[e].head;
            if (v == from) continue;
            DFS(v, u);
        }
        return;
    }
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i], graph::vertex[i].val = a[i];
    for (int i = 1; i <= n - 1; i++) std::cin >> x >> y, graph::addEdge(x, y), graph::addEdge(y, x);
    std::cin >> m;
    for (int i = 1; i <= m; i++) {
        std::cin >> p >> x >> y;
        if (p == 1) graph::vertex[x].tag1 += y, graph::vertex[x].val += y;
        if (p == 2) graph::vertex[x].tag2 += y, graph::vertex[x].val += y;
    }
    graph::DFS(1, 0);
    std::cin >> q;
    for (int i = 1; i <= q; i++) {
        std::cin >> x;
        std::cout << graph::vertex[x].val << std::endl;
    }
    return 0;
}