第三次排位赛题解

小马的诱惑

签到题 直接输出就行

人机猎杀者

本题考察最短路问题

由题可知，我们没有负权，并且是一个单源最短路，应该采用 dijkstra 算法。参考数据范围，直接暴力会 TLE ，所以使用堆优化实现，参考实现代码如下

C++ 实现

#ifdef _MSC_VER    // 如果编译器是 msvc

import std.compat; // 导入标准库模块

#else
#include <bits/stdc++.h> // 否则导入万能头
template <typename... Args> // 并且自己实现C++23的打印函数
void print(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
}
template <typename... Args>
void println(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
    std::cout.put('\n');
}
void print(const std::string_view s) { std::cout << s; }
void println(const std::string_view s) { std::cout << s << '\n'; }
#endif
// 拓展打印函数的功能
void println() { std::cout << '\n'; }

using namespace std;
// 写几个别名缩写，不写缩写也行
template <typename W, typename V> // 邻接表的边类型
using Edge = pair<W, V>;
template <typename EdgeType> // 邻接表本身
using Graph = vector<vector<EdgeType>>;
template <typename T> // 小根堆（优先队列优化 dijkstra)
using Heap = priority_queue<T, vector<T>, greater<>>;

void solve() {
    int64_t V, E, s;
    cin >> V >> E >> s;
    // 存图
    using edge_t = Edge<int64_t, int64_t>;
    Graph<edge_t> graph(V + 1); // 这个图的编号从 1 开始，所以节点数 + 1
    for (int64_t u, v, w; E--;) {
        cin >> u >> v >> w; // 邻接表，u -> v : [w]
        graph[u].emplace_back(w, v);
    }
    // dijkstra 初始化，注意顶点从 1 开始编号，长度要 + 1
    Heap<edge_t> heap;
    vector<int64_t> distances(V + 1, numeric_limits<int64_t>::max());
    distances[s] = 0;
    heap.emplace(distances[s], s);
    // dijkstra 堆优化实现
    while (not heap.empty()) {
        auto [_, u] = heap.top();
        heap.pop();
        // 遍历 u 为起点的所有边
        for (auto &&[w, v] : graph[u]) {
            if (distances[u] + w < distances[v]) {
                distances[v] = distances[u] + w;
                heap.emplace(distances[v], v);
            }
        }
    }
    // 打印结果
    for (auto &&distance : distances | views::drop(1)) {
        if (distance == numeric_limits<int64_t>::max())
            print("inf");
        else
            print("{}", distance);
        if (V--) // 不是最后一个顶点就可以打空格
            print(" ");
    }
    println();
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int64_t t{1};
    cin >> t;
    while (t--)
        solve();
    return 0;
}

懂点GCD的栈

本题考查栈的基本操作

按题意模拟即可

之前的被强数据hack掉了

考虑使用区间压缩表示法来优化。我们现在把栈中的元素表示为(值，数量)，然后模拟即可。

#include <bits/stdc++.h>
#pragma region printlns
namespace std {
#ifndef _MSC_VER
    template <typename... Args>
    void print(const std::string_view fmt, const Args &...args) {
        std::cout << std::vformat(fmt, std::make_format_args(args...));
    }
    template <typename... Args>
    void println(const std::string_view fmt, const Args &...args) {
        std::cout << std::vformat(fmt, std::make_format_args(args...)) << '\n';
    }
    void print(const std::string_view s) { std::cout << s; }
    void println(const std::string_view s) { std::cout << s << '\n'; }
#endif
    void println() { std::cout.put('\n'); }

    void close_sync() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
}
#pragma endregion
using namespace std;
using i64 = long long;

// #define t_case
auto solve() {
    i64 q;
    std::cin >> q;
    std::stack<std::pair<i64, i64> > stack;
    while (q--) {
        i64 op;
        std::cin >> op;
        if (op == 1) {
            i64 x;
            std::cin >> x;
            if (stack.empty() or stack.top().first != x)
                stack.emplace(x, 1);
            else
                stack.top().second++;
        } else if (op == 2) {
            if (stack.top().second == 1)
                stack.pop();
            else
                stack.top().second--;
        } else if (op == 3) {
            std::println("{}", stack.empty() ? 0 : stack.top().first);
        } else {
            i64 k;
            std::cin >> k;
            auto gcd = stack.top().first;
            for (i64 offset = k;;) {
                auto &&[val, cnt] = stack.top();
                offset -= cnt;
                gcd = std::gcd(gcd, val);
                if (offset < 1) {
                    if (offset == 0)
                        stack.pop();
                    else
                        cnt = -offset;
                    break;
                }
                stack.pop();
            }
            stack.emplace(gcd, k);
        }
    }
}

auto main() -> signed {
    std::close_sync();
    i64 t{1};
#ifdef t_case
    std::cin >> t;
#endif
    while (t--)
        solve();
    return 0;
}

风暴山脉

本题考查单调栈

为什么要用单调栈?

单调栈是用来求一个点两边最早大于或者小于的点的位置的 (这很显然对吧) 我们从左往右扫 当前扫到的数和栈顶元素比较

1. 这个数大于栈顶 那很显然栈顶右边第一个大于他的数找到了
2. 这个数小于栈顶 那很显然这个数左边第一个大于他的数也找到了

所以单调栈是可以用来求两边第一个大于/小于这个数的位置的

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int h[N], v[N], ans[N], mx;
stack<int> s;
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i] >> v[i]; 
    for (int i = 1; i <= n; i++)
    {
        while (!s.empty() && h[s.top()] < h[i])
        {
        	ans[i] += v[s.top()];
        	s.pop();
		}
		if (!s.empty()) ans[s.top()] += v[i];
        s.push(i);
    }
    for (int i = 1; i <= n; i++) mx = max(mx, ans[i]);
    cout << mx << endl;
}

营救小卓

本题考查dfs

搜索时记得判断是否经过小卓的位置就行了

#ifdef _MSC_VER

import std.compat;

#else
#include <bits/stdc++.h>
template <typename... Args>
void print(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
}
template <typename... Args>
void println(const std::string_view fmt, const Args &...args) {
    std::cout << std::vformat(fmt, std::make_format_args(args...));
    std::cout.put('\n');
}
void print(const std::string_view s) { std::cout << s; }
void println(const std::string_view s) { std::cout << s << '\n'; }
#endif

void println() { std::cout << '\n'; }

using namespace std;

void solve() {
    const array<pair<int64_t, int64_t>, 4> &dxy = {pair < int64_t, int64_t > {0, -1},
                                                   pair < int64_t, int64_t > {-1, 0},
                                                   pair < int64_t, int64_t > {0, 1},
                                                   pair < int64_t, int64_t > {1, 0}};
    int64_t n, k, r, c;
    cin >> n >> k >> r >> c;
    vector matrix(n, vector<int64_t>(n));
    for (auto &&line: matrix)
        for (auto &&cell: line)
            cin >> cell;    // 输入矩阵
    int64_t ans{numeric_limits<int64_t>::max()};    // 初始化答案为 INT64_MAX
    vector visited(n, vector<bool>(n, false));  // 标记所有点没走过
    // 实现匿名函数递归 声明dfs函数
    function<void(const int64_t &, const int64_t &, const int64_t &, const bool &)> dfs =
            [&](const int64_t &x, const int64_t &y, const int64_t &cost, const bool &isSaved) {
                if (cost > k)   // 如果费用超出了，直接return
                    return;
                if (x == n - 1 and y == n - 1 and isSaved) {
                    ans = min(ans, cost);   // 到达终点了，并且救下来了
                    return;
                }
                for (auto &&[dx, dy]: dxy) {
                    // 遍历上下左右四个方向
                    auto px = dx + x, py = dy + y;
                    if (px < 0 or py < 0 or px >= n or py >= n or visited[px][py])
                        continue; // 超出边界就直接continue
                    visited[px][py] = true; // 标记这个地方走过了
                    // cost + matrix[px][py] 表示走这个节点的总花费
                    // isSaved or (px == r and py == c) 表示，已经救下了或者当前节点可以救
                    dfs(px, py, cost + matrix[px][py], isSaved or (px == r and py == c));
                    visited[px][py] = false;// 撤销标记，回溯
                }
            };
    // 标记起点走过了
    visited[0][0] = true;
    // 给定初始化信息，r == 0 and c == 0 表示判断小卓在不在起点
    dfs(0, 0, matrix[0][0], r == 0 and c == 0);
    // 如果找得到就打印，否则打印 -1
    println("{}", ans == numeric_limits<int64_t>::max() ? -1 : ans);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int64_t t{1};
//    cin >> t;
    while (t--)
        solve();
    return 0;
}