A. 有天你飞起来去摘那云彩

Description

天上有 \(n\) 朵云彩，他们从左到右排成一排，每朵云彩都有一个洁白值，分别是 \(p_1, p_2, \cdots p_n\)，并且每朵云彩的洁白值都不同。

现在，你想要飞起来去摘下一些云彩，为此你需要计算一个奇特的任务。

具体的，你需要从每个长度为 \(m\) 的区间中，选出 \(k\) 朵云彩，使得它们的洁白值之和尽可能小。

Format

Input

第一行，三个整数，\(n, m, k\)。

第二行，\(n\) 个整数，\(p_1, p_2, \cdots p_n\) 表示云彩的洁白值。

保证云彩的洁白值互不相同。

Output

输出一行，包含 \(n - m + 1\) 个整数，其中第 \(i\) 个整数表示从 \(p_i, p_{i+1}, \cdots p_{i+m-1}\) 中选出恰好 \(k\) 个云彩能得到的最小洁白值总和。

Samples

输入1

1 2	6 4 3 1 3 4 2 5 6

输出1

6 9 11

输入2

1 2	10 6 3 1 2 10 9 7 8 4 3 6 5

输出2

1	10 13 14 13 12

Limitation

\(1 \leq k \leq m \leq n \leq 10^6\)

\(1 \leq p_i \leq n\)，对于 \(i \neq j\) 有 \(p_i \neq p_j\)

思路与题解

其实就是滑动窗口的 Top-K

采用一个大根堆和一个小根堆来维护当前窗口内的元素

这里的堆由于要找到元素并删除，采用 multiset 实现这一功能

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int n,m,k;
    cin >> n >> m >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (m > n) return 0;

    k = min(k, m);

    multiset<int> minq, maxq;
    long long ans = 0;

    auto add = [&](int x) {
        if (k == 0) {
            maxq.insert(x);
            return;
        }
        if (minq.size() < k) {
            minq.insert(x);
            ans += x;
        } else {
            auto top = prev(minq.end());
            if (x < *top) {
                minq.insert(x);
                ans += x;
                int v = *top;
                minq.erase(top);
                maxq.insert(v);
                ans -= v;
            } else {
                maxq.insert(x);
            }
        }
    };

    auto remove = [&](int x) {
        auto it = minq.find(x);
        if (it != minq.end()) {
            minq.erase(it);
            ans -= x;
            if (minq.size() < k && !maxq.empty()) {
                auto it2 = maxq.begin();
                int v = *it2;
                maxq.erase(it2);
                minq.insert(v);
                ans += v;
            }
        } else {
            auto it2 = maxq.find(x);
            if (it2 != maxq.end()) {
                maxq.erase(it2);
            }
        }
    };

    for (int i = 0; i < m; ++i) {
        add(a[i]);
    }
    cout << ans << " ";

    for (int i = m; i < n; ++i) {
        add(a[i]);
        remove(a[i - m]);
        cout << ans << " ";
    }
    
    return 0;
}

B. 最小的 n 个和

Description

给定 \(A\)、\(B\) 两个数列，各包含 \(n\) 个数，分别从 \(A\) 和 \(B\) 中任意取一个数相加得到和，这样会有 \(n^2\) 种结果(包括重复的)，求 \(n^2\) 个结果中前 \(n\) 个最小的和。

Format

Input

第一行为 \(n\)，第二行为数列 \(A\)，第三行为数列 \(B\)。

Output

输出一行，包含前 \(n\) 个最小的和，按照升序输出，两数之间用一个空格隔开。

Samples

输入数据 1

1
2
3

5
1 3 4 2 0
7 3 5 2 11

输出数据 1

2 3 3 4 4

输入数据 2

1
2
3

20
33 84 93 14 89 61 55 54 63 24 81 36 22 35 78 63 13 2 72 3
39 15 85 2 60 53 84 11 94 68 74 47 44 36 42 77 66 38 6 46

输出数据 2

1	3 3 4 14 16 16 16 17 23 23 24 25 25 26 27 28 29 29 30 31

输入数据 3

1
2
3

20
91 78 44 65 66 40 32 69 38 87 66 79 14 78 69 74 18 22 6 62
77 61 63 69 64 57 58 56 53 52 51 50 49 48 47 46 45 44 43 42

输出数据 3

1	14 16 18 24 28 32 33 35 35 36 37 38 39 40 41 42 43 44 45 46

Limitation

\(1 \leq n \leq 100000, 0 \leq A_i, B_i \leq 10^9\)

思路与题解

一开始以为不能排序，排序交了一遍之后才发现可以排序

排序之后按照 b 分为 n 链，依次加到一个优先队列中，这种链可以考虑为每次有一个指针从 b[0] 开始向后移动，每次比较这 n 个指针所指的和，取最小的那个，然后将该指针向后移动一位，再次加入优先队列

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    using T = tuple<ll, int, int>; // {sum, i, j}
    priority_queue<T, vector<T>, greater<T>> pq;

    for (int i = 0; i < n; ++i) pq.emplace(a[i] + b[0], i, 0);


    int count = 0;
    while (count < n && !pq.empty()) {
        auto [sum, i, j] = pq.top();
        pq.pop();

        cout << sum << " ";
        count++;

        if (j + 1 < n) {
            pq.emplace(a[i] + b[j + 1], i, j + 1);
        }
    }

    return 0;
}

C. 后序遍历

Description

给定一棵 \(n\) 个节点的二叉树的前序遍历（根、左、右）和中序（左、根、右）遍历，求其后序遍历（左、右、根）。

Format

Input

第一行一个数 \(n\)，表示树的节点个数。

接下来一行 \(n\) 个整数，表示前序遍历的节点编号。

接下来一行 \(n\) 个整数，表示中序遍历的节点编号。

Output

一行 \(n\) 个整数，表示后序遍历的节点编号。

Samples

输入样例

1
2
3

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

输出样例

1	7 4 2 8 9 5 6 3 1

Limitation

\(1 \leq n \leq 1000\)

样例树结构：

思路与题解

很经典的题目了，学遍历必做的题

主要思路是找根，前序遍历的根是第一个元素，在中序遍历中找到该根的位置，左边是左子树，右边是右子树，然后递归的求解即可

#include <iostream>
#include <vector>

using namespace std;

int n;
vector <int> pre, mid, post;

void dfs(int preL, int preR, int midL, int midR) {
    int root = pre[preL];
    int k = midL;
    while (k <= midR && mid[k] != root) k++;
    int leftNum = k - midL;
    if (leftNum > 0) {
        dfs(preL + 1, preL + leftNum, midL, k - 1);
    }
    if (leftNum < preR - preL) {
        dfs(preL + leftNum + 1, preR, k + 1, midR);
    }
    post.push_back(root);
}



int main() {
    cin >> n;
    pre.resize(n);
    mid.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> pre[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> mid[i];
    }
    dfs(0, n - 1, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << post[i] << " ";
    }

    return 0;
}

D. 树值之和

Description

如果有来生，我要做一棵树，站成永恒，没有悲欢的姿势，一半在尘土里安详，一半在风里飞扬；一半洒落雨凉，一半沐浴阳光，非常沉默，非常骄傲。从不依靠，从不寻找。

Y 觉得树很好，他希望军训的同学也能像树一样。

为此，他将 \(n\) 名同学排成树的形状，每个同学站在树的一个节点上，1 号同学站在根的位置。

这 \(n\) 名同学的美丽值为 \(a_1, a_2, \cdots, a_n\)。而 Y 又定义了一个名为”树值”的玩意，他认为，每个同学的树值为该同学对应节点子树中所有同学的美丽值之和加上子树中同学的数量。注意，节点 \(v\) 的子树包括节点 \(v\) 自己。

Y 想知道，所有同学的树值之和是多少。

Format

Input

第一个一个整数 \(n\) 表示同学数量。

第二行 \(n - 1\) 个整数分别表示第 \(2, 3, \cdots, n\) 号同学的”父亲”。

第三行 \(n\) 个整数表示 \(a_1, a_2, \cdots, a_n\)。

Output

一行一个整数表示所有同学的树值之和。

Samples

输入样例

1
2
3

10
1 1 3 4 2 4 3 3 9
9 4 7 9 7 4 6 10 6 6

输出样例

Limitation

\(1 \leq n \leq 10^6, \quad 1 \leq a_i \leq 10^5\)

节点编号从 1 开始。

思路与题解

简单来说就是计算每个节点的深度乘上每个节点的值加上每个节点的深度

那问题就转化为求节点的深度了，但是如果每个都求一遍会超时，所以可以记录下每一次求深度的结果

使用栈就可以轻松做到这一点

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    if (n <= 0) return 0;

    vector<int> pa(n);
    pa[0] = -1;
    for (int i = 1; i < n; ++i) {
        int x;
        cin >> x;
        pa[i] = x - 1;
    }

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

    long long ans = 0;
    vector<int> depth(n, 0);
    for (int i = 0; i < n; ++i) {
        if (depth[i] != 0) {
            ans += 1LL * (a[i]+1) * depth[i];
        }
        int cur = i;
        stack<int> stk;
        while (cur != -1 && depth[cur] == 0) {
            stk.push(cur);
            cur = pa[cur];
        }
        int base_depth = (cur == -1) ? 0 : depth[cur];
        while (!stk.empty()) {
            base_depth += 1;
            int node = stk.top();
            stk.pop();
            depth[node] = base_depth;
        }
        ans += 1LL * (a[i]+1) * depth[i];
    }
    cout << ans;
    return 0;
}

E. 儿子的儿子的儿子……

Description

Y 虽然让同学们站成一棵树的样子，但是同学们都不安分。

每个同学都想知道自己的儿子的儿子的儿子……有多少个。

即求，对于每个节点 \(v\)，在其子树中距离自己恰好为 \(k\) 的节点有多少个。

Format

Input

第一行两个数 \(n\) 和 \(k\)。

第二行 \(n - 1\) 个整数分别表示第 \(2, 3, \cdots, n\) 号同学的”父亲”。

Output

输出 \(n\) 个数空格隔开表示每个同学的儿子的儿子的儿子……的数量。

Samples

输入样例

1 2	5 1 1 1 2 1

输出样例

3 1 0 0 0

Limitation

\(1 \leq n, k \leq 5 \times 10^6\)

节点编号从 1 开始，且 1 为根。

思路与题解

一开始以为一个 dp 就能解决了，也就是 dp[i][k] 代表节点 \(i\) 距离为 \(k\) 的个数，那么有递推

\[dp[pa[i]][k] += dp[i][k-1]\]

超内存了，那只能用滚动数组压缩一下，但是超时了，但感觉这题没有其他做法，只能在类似快速幂的思路下进行优化

每个节点向上走 \(k\) 步，可以把 \(k\) 写成二进制的形式，然后每次跳 \(2^j\) 步

每次维护一个 up 数组，表示跳 \(2^j\) 步之后的节点是谁，如果 \(k\) 的该位为 1，则将当前节点跳到 up 数组所指的节点

现在就是 \(O(n \log k)\) 时间，\(O(n)\) 空间了

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long k;
    cin >> n >> k;
    if (n <= 0) return 0;

    vector<int> pa(n);
    pa[0] = -1;
    for (int i = 1; i < n; ++i) {
        int x;
        cin >> x;
        pa[i] = x - 1;
    }

    k = min(k ,n-1LL);

    vector<int> up = pa;
    vector<int> cur(n);
    iota(cur.begin(), cur.end(), 0);

    long long rem = k;
    while (rem > 0) {
        if (rem & 1LL) {
            for (int i = 0; i < n; ++i) {
                if (cur[i] != -1) cur[i] = up[cur[i]];
            }
        }

        vector<int> nextup(n, -1);
        for (int i = 0; i < n; ++i) {
            int mid = up[i];
            nextup[i] = (mid == -1) ? -1 : up[mid];
        }
        up = nextup;
        rem >>= 1LL;
    }

    vector<int> dp(n, 0);
    for (int i = 0; i < n; ++i) if (cur[i] != -1) dp[cur[i]] += 1;

    for (int i = 0; i < n; ++i) {
        cout << dp[i] << " ";
    }
    return 0;
}

SA. 二叉树上的询问

传统题 1000ms 256MB

题目描述

给出一棵具有 \(n\) 个结点的树。

我们规定，1 是这棵树的树根。

并且，我们规定，对于所有的 \(2 \leq i \leq n\)，编号为 \(i\) 的结点的父结点是 \(\left\lfloor \frac{i}{2} \right\rfloor\)。

显然，这是一棵二叉树，对于节点 \(i\)，其左子结点是 \(2i\)，其右子结点是 \(2i + 1\)（如果它有对应节点的话）。

现在，有 \(m\) 个询问。每个询问，问编号为 \(x\) 的结点在这棵二叉树的前序遍历中排名第几。你需要对每组询问输出对应的答案。

前序遍历: 对每棵子树，先访问其根结点，再访问其左子树，最后访问其右子树。

例如，当 \(n = 5\) 的时候，前序遍历为 \(\{1, 2, 4, 5, 3\}\)

输入格式

第一行，输入两个整数 \(n\)，\(m\) \((1 \leq n \leq 10^{18}, 1 \leq m \leq 10^5)\)，分别表示这棵树的结点总数，以及询问个数。

接下来 \(m\) 行，第 \(i\) 行输入一个整数 \(x_i\) \((1 \leq x_i \leq n)\)，表示询问结点 \(x_i\) 在这棵树前序遍历中的排名。

输出格式

对每个询问，输出一行，一个整数，表示对应询问的答案。

样例

输入

输出

时空限制

1000ms 256MB

思路与题解

#include <bits/stdc++.h>
#include <climits>

using namespace std;
using ll = long long;

ll subtree(ll n, ll u) {
    if (u > n) return 0;
    ll cnt = 0;
    ll l = u, r = u;
    while (l <= n) {
        cnt += min(n, r) - l + 1;
        if (l > (LLONG_MAX >> 1)) break;
        l <<= 1;
        if (r > (LLONG_MAX >> 1)) r = LLONG_MAX;
        else r = (r << 1) + 1;
    }
    return cnt;
}

ll ans(ll n, ll x) {
    if (x == 1) return 1;
    if (x & 1) return ans(n, x/2) + subtree(n, x-1) + 1;
    return ans(n, x/2) + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    int m;
    cin >> n >> m;
    while (m--) {
        ll x;
        cin >> x;
        cout << ans(n, x) << "\n";
    }
    return 0;
}

SB. 跑步！

题目背景

因为题目太难，同学们集体要工不在考试，于是你转到操场跑步去了。

题目描述

俯视操场，把操场看成一个平面，建立平面直角坐标系。

同学们分成了两组。
第一组的同学刚开始站在 x 轴上，位置在 \((p_i, 0)\)，他们的跑动速度都是 \((0, v_1)\)（即：向 y 轴方向以 \(v_1\) 速度跑动）。每个人有一个视野范围 \(w_1\)，也就是说，当他位于坐标 \((x, y)\) 时，能够看见点 \((x, y)\) 到点 \((x + w_1, y)\) 这条线段上的人（包含端点）。
第二组的同学刚开始站在 y 轴上，位置在 \((0, p_i)\)，他们的跑动速度都是 \((v_2, 0)\)（即：向 x 轴方向以 \(v_2\) 速度跑动）。每个人有一个视野范围 \(w_2\)，也就是说，当他位于坐标 \((x, y)\) 时，能够看见点 \((x, y)\) 到点 \((x, y + w_2)\) 这条线段上的人（包含端点）。
同学们都有一个自己的出现时间 \(t_i\)，可以理解为，在 \(t_i\) 时间内，这个同学会出现在自己的位置上，然后按照自己的速度开始奔跑。
每位同学在自己奔跑的时候，会记录自己视野范围内出现的人。现在你需要求出每位同学在自己奔跑的过程中，能记录到多少个不同的人（不包括自己）。（假设时间无限，一直跑下去）

输入格式

一行，三个整数，\(n, v_1, v_2\)。

接下来 \(n\) 行，每行四个整数 \(a_i, t_i, p_i, w_i\)，分别表示这个同学是第 \(a_i\) 组的同学，他的出现时间是 \(t_i\)，位置参数是 \(p_i\)，视野范围是 \(w_i\)。

输出格式

\(n\) 行，第 \(i\) 行表示第 \(i\) 个人在跑步过程中一共能看到多少个不同的人。

样例 #1

样例输入 #1

1
2
3

2 1 1
1 1 1 1
2 2 2 1

样例输出 #1

1
2

1
1

样例 #2

样例输入 #2

样例输出 #2

提示

【数据范围】：

对30%的数据满足，\(n \leq 1000\)

对50%的数据满足，\(v_1 = v_2 = 1\)

对100%的数据满足，\(1 \leq n, v_1, v_2, t_i, p_i, w_i \leq 10^5\)，\(a_i \in \{1, 2\}\)。保证同组的同学中，任意两个同学的 \(t_i, p_i\) 不相同。

思路与题解

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Person {
    int a;
    ll t, p, w;
    int idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll v1, v2;
    cin >> n >> v1 >> v2;

    vector<Person> all(n), g1, g2;
    g1.reserve(n); g2.reserve(n);

    for (int i = 0; i < n; ++i) {
        cin >> all[i].a >> all[i].t >> all[i].p >> all[i].w;
        all[i].idx = i;
        if (all[i].a == 1) g1.push_back(all[i]);
        else g2.push_back(all[i]);
    }

    vector<ll> ans(n, 0);

    auto same_group = [&](vector<Person>& g) {
        if (g.empty()) return;
        sort(g.begin(), g.end(), [](const Person& x, const Person& y){
            if (x.t != y.t) return x.t < y.t;
            return x.p < y.p;
        });
        int m = (int)g.size();
        int i = 0;
        while (i < m) {
            int j = i;
            while (j < m && g[j].t == g[i].t) ++j; // [i,j)
            vector<ll> pos; pos.reserve(j - i);
            for (int k = i; k < j; ++k) pos.push_back(g[k].p);
            for (int k = i; k < j; ++k) {
                ll limit = g[k].p + g[k].w;
                auto it = upper_bound(pos.begin(), pos.end(), limit);
                ll cnt = (it - pos.begin()) - (k - i) - 1;
                if (cnt > 0) ans[g[k].idx] += cnt;
            }
            i = j;
        }
    };

    same_group(g1);
    same_group(g2);

    ll K = v1 * v2;

    vector<ll> keysB;
    keysB.reserve(g2.size());
    for (auto &x : g2) keysB.push_back(K * x.t - v2 * x.p);
    sort(keysB.begin(), keysB.end());

    for (auto &x : g1) {
        ll L = K * x.t - v1 * (x.p + x.w);
        ll R = K * x.t - v1 * x.p;
        auto itL = lower_bound(keysB.begin(), keysB.end(), L);
        auto itR = upper_bound(keysB.begin(), keysB.end(), R);
        ans[x.idx] += (itR - itL);
    }


    vector<ll> keysA;
    keysA.reserve(g1.size());
    for (auto &x : g1) keysA.push_back(K * x.t - v1 * x.p);
    sort(keysA.begin(), keysA.end());

    for (auto &x : g2) {
        ll L = K * x.t - (x.p + x.w) * v2;
        ll R = K * x.t - x.p * v2;
        auto itL = lower_bound(keysA.begin(), keysA.end(), L);
        auto itR = upper_bound(keysA.begin(), keysA.end(), R);
        ans[x.idx] += (itR - itL);
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

SC. 五折券

传统题 1000ms 256MB

Description

ZZR 打算买 \(n\) 个商品，其中第 \(i\) 个商品的价格为 \(a_i\) 元，现在 ZZR 有 \(m\) 张五折券。

若他买第 \(i\) 个商品使用了 \(Y\) 张打折券，则他购买这个商品只需要花费 \(\left\lfloor \frac{a_i}{2^Y} \right\rfloor\) 元。

ZZR 想请你帮他计算一下，他购买这些商品至少要花费多少元？

Format

Input

第一行包含两个整数 \(n, m\) 表示商品数量和五折券数量。

第二行 \(n\) 个正整数，表示每个商品的价格 \(a_1, a_2, \cdots, a_n\)。

Output

一个整数，表示 ZZR 购买这些商品最少需要花费多少元。

Samples

输入样例 1

1 2	3 3 2 13 8

输出样例 1

输入样例 2

1 2	4 4 1 9 3 5

输出样例 2

输入样例 3

1 2	1 100000 1000000000

输出样例 3

Limitation

\(1 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times 10^5\)，\(1 \leq a_i \leq 10^9\)。

对于第一个样例，ZZR 购买第一个商品不使用打折券，花费 2 元，购买第二个商品使用两张打折券，花费 3 元，购买第三个商品使用一张打折券，花费 4 元，一共花费 9 元。

思路与题解

#include <iostream>
#include <queue>

using namespace std;

int main(){
	int n,m;
	cin >> n >> m; 
    vector<double> a(n);
    priority_queue<double> pq;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        pq.push(a[i]);
    }
    while(m--){
        double x = pq.top();
        pq.pop();
        x = x/2;
        pq.push(x);
    }

    long long sum = 0;
    while(!pq.empty()){
        int top = pq.top();
        pq.pop();
        sum += top;
    }
    cout << sum;
    

    return 0;
}

(´-ω-｀)

数据结构作业题解07

A. 有天你飞起来去摘那云彩

Description

Format

Input

Output

Samples

Limitation

思路与题解

B. 最小的 n 个和

Description

Format

Input

Output

Samples

输入数据 1

输出数据 1

输入数据 2

输出数据 2

输入数据 3

输出数据 3

Limitation

思路与题解

C. 后序遍历

Description

Format

Input

Output

Samples

Limitation

思路与题解

D. 树值之和

Description

Format

Input

Output

Samples

输入样例

输出样例

Limitation

思路与题解

E. 儿子的儿子的儿子……

Description

Format

Input

Output

Samples

输入样例

输出样例

Limitation

思路与题解

SA. 二叉树上的询问

题目描述

输入格式

输出格式

样例

输入

输出

时空限制

思路与题解

SB. 跑步！

题目背景

题目描述

输入格式

输出格式

样例 #1

样例 #2

提示

思路与题解

SC. 五折券

Description

Format

Input

Output

Samples

Limitation

思路与题解