牛客挑战赛72

发表于 更新于 分类于 阅读次数： 本文字数： 535 阅读时长 ≈ 2 分钟
Practice makes perfect.

A. Crying 与爬山

思路：

  • 找到序列中 \(a_{i-1} \gt a_i \lt a_{i+1}\) 的个数即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

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

    int ans = 0;
    for (int i = 1; i + 1 < n; i++) {
        if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
            ans++;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

B. Crying 与选秀

思路：

  • 模拟
  • 当集合大小小于6时，就一直填入，当大于6时，只需要每次和集合中最小的那个数比较一下即可，这个过程可以用set维护

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int ans = 0;
    std::set<std::pair<double, int>> st;
    std::vector<double> a(n);
    std::vector<int> res;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        if (st.size() < 6) {
            st.insert({a[i], i});
            res.push_back(0);
            ans++;
        } else {
            auto x = *st.begin();
            if (a[i] > x.first) {
                res.push_back(x.second + 1);
                st.erase(st.begin());
                st.insert({a[i], i});
                ans++;
            } else {
                res.push_back(0);
            }
        }
    }

    std::cout << ans << "\n";
    for (auto x : res) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    return 0;
}

C. Crying 与哈密顿路

思路：

D. Crying 与 404

思路：

  • 用主席树维护区间 [l, r] 的第 k 小的数
  • 每一个数的节点，我们存三个参数，这个区间的左右端点 [l, r]，以及这个区间的数的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
constexpr int N = 5E5 + 10;
struct node {
    int l, r;
    int sum;
}tr[N * 40];

int root[N], cnt;
void modify(int &x, int y, int l, int r, int pos) {
    x = ++cnt;
    tr[x] = tr[y];
    tr[x].sum++;
    if (l == r) {
        return ;
    }

    int mid = l + r >> 1;
    if (pos <= mid) {
        modify(tr[x].l, tr[y].l, l, mid, pos);
    } else {
        modify(tr[x].r, tr[y].r, mid + 1, r, pos);
    }
}

int query(int x, int y, int l, int r, i64 k) {
    if (l == r) {
        return l + k - 1;
    }
    int mid = l + r >> 1;
    int sum = (mid - l + 1) - (tr[tr[y].l].sum - tr[tr[x].l].sum);
    if (k <= sum) return query(tr[x].l, tr[y].l, l, mid, k);
    else return query(tr[x].r, tr[y].r, mid + 1, r, k - sum);
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;

        modify(root[i], root[i - 1], 0, n, x);
    }
    while (m--) {
        int l, r;
        std::cin >> l >> r;

        i64 k;
        std::cin >> k;

        if (k >= n) {
            std::cout << k + (r - l) << "\n";
        } else {
            std::cout << query(root[l - 1], root[r], 0, n, k) << "\n";
        }
    }

    return 0;
}