前言

总体来说，本次比赛做的还是比较差，同学们还需要加油努力。本次比赛中发现了两名使用 ChatGPT 编写代码的选手（@，@），为了比赛的公平性，已经取消其成绩。

A. 小凯的排序课

本题为签到题，考察简单 for 循环和 if-else if-else 语句。此外，可以使用映射关系的数据结构，来减少代码量，提高编码效率

C++ 实现

#include <bits/stdc++.h>

using namespace std;
unordered_map<string, string> dict = {
    {"quick sort"    , "O(nlogn) O(logn) No" },
    {"merge sort"    , "O(nlogn) O(n) Yes"   },
    {"heap sort"     , "O(nlogn) O(1) No"    },
    {"shell sort"    , "O(n^{1.3~2}) O(1) No"},
    {"counting sort" , "O(n+m) O(n+m) Yes"   },
    {"insertion sort", "O(n^2) O(1) Yes"     },
    {"bubble sort"   , "O(n^2) O(1) Yes"     },
    {"selection sort", "O(n^2) O(1) No"      },
};
void solve() {
    string s;
    getline(cin, s);
    cout << dict[s] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    cin.ignore();    // 注意要 ignore，否则第一行的行尾换行符会影响 getline
    while (t--)
        solve();
    return 0;
}

Python 实现

mp = {
    "quick sort": "O(nlogn) O(logn) No",
    "merge sort": "O(nlogn) O(n) Yes",
    "heap sort": "O(nlogn) O(1) No",
    "shell sort": "O(n^{1.3~2}) O(1) No",
    "counting sort": "O(n+m) O(n+m) Yes",
    "insertion sort": "O(n^2) O(1) Yes",
    "bubble sort": "O(n^2) O(1) Yes",
    "selection sort": "O(n^2) O(1) No",
}
for _ in range(int(input())):
    print(mp[input()])

Java 实现

import java.util.*;

public class Main {
    private static final Scanner scanner = new Scanner(System.in);
    private static final HashMap dict = new HashMap() {{
        put("quick sort"    , "O(nlogn) O(logn) No" );
        put("merge sort"    , "O(nlogn) O(n) Yes"   );
        put("heap sort"     , "O(nlogn) O(1) No"    );
        put("shell sort"    , "O(n^{1.3~2}) O(1) No");
        put("counting sort" , "O(n+m) O(n+m) Yes"   );
        put("insertion sort", "O(n^2) O(1) Yes"     );
        put("bubble sort"   , "O(n^2) O(1) Yes"     );
        put("selection sort", "O(n^2) O(1) No"      );
    }};

    private static void solve() {
        System.out.println(dict.get(scanner.nextLine()));
    }

    public static void main(String[] args) {
        int t = scanner.nextInt();
        for (scanner.skip("\n"); t != 0; t--)   // skip同理C++的ignore
            solve();
        scanner.close();
    }
}

B. 顽强拼搏的小硕

本题考察分治算法的运用。这题容易踩的一个坑就是，容易想到直接排序后直接打印第 $k$ 个元素，但是在数据范围中却是会超时的。桶排序开不下空间桶，用映射优化又会超时，即使是目前最快的排序算法——tim sort也会超时两个点，所以明显这道题正解不是排序。

思路一

在学习快速排序的时候，我们知道一个基准数的性质，那就是基准数左边的数一定小于基准数，基准数右边的数一定大于基准数，利用这个性质，我们可以在快排的时候避免排序多余的部分，只需要排序包含第 $k$ 小的元素的区间即可。也就是说，在我们进行分治的时候，我们只需要治理含第 $k$ 小的元素的区间。为此，我们可以利用快速排序的分治思想来解决这道题。

这还是一道卡其他语言空间的题目，即使用了正确的算法，给定两倍空间，Python和Java还是会MLE

C语言实现（代码改于洛谷P1923题解）

#include <stdio.h>
#include <stdlib.h>
void swap(long long *a, long long *b) {
    long long tmp = *a;
    *a = *b;
    *b = tmp;
}
long long x[5000005], k;
void qselect(long long l, long long r) {
    long long i = l, j = r, mid = x[(l + r) / 2];
    do {
        while (x[j] > mid)
            j--;
        while (x[i] < mid)
            i++;
        if (i <= j) {
            swap(x + i, x + j);
            i++;
            j--;
        }
    } while (i <= j);
    // 快排后数组被划分为三块： l<=j<=i<=r
    if (k <= j)
        qselect(l, j); // 在左区间只需要搜左区间
    else if (i <= k)
        qselect(i, r); // 在右区间只需要搜右区间
    else             // 如果在中间区间直接输出
    {
        printf("%lld", x[j + 1]);
        exit(0);
    }
}
signed main() {
    long long n;
    scanf("%lld", &n);
    for (long long i = 0; i < n; i++)
        scanf("%lld", &x[i]);
    scanf("%lld", &k);
    qselect(0, n - 1);
    return 0;
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;  // 别名

void quick_select(vector<i64> &arr, const i64 &l, const i64 &r, const i64 &k) {
    auto i = l, j = r, mid = arr[(l + r) >> 1];
    while (i <= j) {
        while (arr[j] > mid)
            j--;
        while (arr[i] < mid)
            i++;
        if (i <= j)
            swap(arr[i++], arr[j--]);
    }
    if(k <= j)
        quick_select(arr, l, j, k);
    else if(i <= k)
        quick_select(arr, i, r, k);
    else {
        cout << arr[j + 1];
        exit(0);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;
    vector<i64> arr(n);
    for (auto &&i: arr)
        cin >> i;
    i64 k;
    cin >> k;
    quick_select(arr, 0, n - 1, k);
    return 0;
}

思路二

STL 大法好，STL 给我们提高了一个 $O(n)$ 求区间第 $k$ 小元素的函数，我们直接使用它即可（注意，你需要打开 O2 优化）

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector arr(n, 0ll);
    for (auto &&i : arr)
        cin >> i;
    int k;
    cin >> k;
    // C++20之前的 nth_element 用法如下
    // nth_element(arr.begin(), arr.begin() + k, arr.end());
    ranges::nth_element(arr, arr.begin() + k);
    cout << arr[k];
    return 0;
}

C. 村长的雪糕

本题考察二分答案

思路

这题第一眼很容易想到暴力模拟，枚举出买多少根雪糕，枚举到最小能吃到 $n$ 个雪糕的个数是多少。但是看一眼数据范围，$10^5 \times 10^{12} = 10^{17}$ 明显是大于我们暴力 $O(n)$ 的最大范围（$10^8$）的。考虑使用更第时间复杂度如 $O(logn)$ 的算法。我们知道，二分答案的时间复杂度是 $O(logn * f(n))$ ，这里的 $f(n)$ 是 check 函数的时间复杂度。根据题意，check 函数应为判断买 $mid$ 个雪糕能否完成任务，采用模拟算法来实现的话，时间复杂度是 $O(log_3{mid})$ 。最终的时间复杂度为 $O(logn)$ 可以满足数据范围。

C++朴素实现

#include <bits/stdc++.h>
using namespace std;
int64_t n;
bool check(int64_t mid) {
    auto res = mid;
    while (mid >= 3) {
        auto t = mid / 3;
        res += t;
        mid -= t << 1;
    }
    return res < n;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n) {
        int64_t l = 0, r = 1e12 + 5;
        while (l < r) {
            auto mid = (l + r) >> 1;
            if(check(mid))
                l = mid + 1;
            else
                r = mid;
        }
        cout << l << endl;
    }
    return 0;
}

C++ STL实现

需要注意的是，你需要打开 O2 优化

#include <bits/stdc++.h>
using namespace std;
constexpr int64_t maxn = 1e12 + 1;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64_t n;
    auto &&answer_range = views::iota(0ll, maxn);
    auto check = [&](auto mid) {
        auto res = mid;
        while (mid >= 3) {
            auto t = mid / 3;
            res += t;
            mid -= t << 1;
        }
        return res < n;
    };
    while (cin >> n)
        cout << *ranges::partition_point(answer_range, check) << endl;
    return 0;
}

Python 实现

from sys import stdin
input = stdin.readline
n = 0

def check(mid):
    global n
    res = mid
    while mid >= 3:
        t = mid // 3
        res += t
        mid -= t << 1
    return res < n

while True:
    try:
        n = int(input())
        l, r = 0, 10 ** 12 + 5
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                l = mid + 1
            else:
                r = mid
        print(l)
    except:
        break

Java 实现

import java.util.*;
import java.util.function.*;

public class Main {
    private static final Scanner scanner = new Scanner(System.in);

    public static void solve() {
        var n = scanner.nextLong();
        LongFunction<Boolean> check = (long mid) -> {
            var res = mid;
            while (mid >= 3) {
                var t = mid / 3;
                res += t;
                mid -= t << 1;
            }
            return res < n;
        };
        long l = 0, r = (long) (1e12 + 1);
        while(l < r) {
            var mid = (l + r) >> 1;
            if(check.apply(mid))
                l = mid + 1;
            else
                r = mid;
        }
        System.out.println(l);
    }

    public static void main(String[] args) {
        while (scanner.hasNext())
            solve();
        scanner.close();
    }
}

D. 副队长的堆

本题考察堆的构建和实现。这题的实现比较底层，相比起洛谷或其他地方的堆模板题，该题更深入了优先队列的底层，提供直接访问堆内部成员的要求，灵活性更高

思路

模拟实现堆

C 语言朴素实现

#include <stdio.h>
#include <stdbool.h>

typedef unsigned long long u64;

u64 heap[1000005];
u64 size = 0;

void swap(u64 *a, u64 *b) {
    u64 t = *a;
    *a = *b;
    *b = t;
}

void down(u64 i) {
    u64 parent = i;
    u64 child = parent << 1 | 1;
    while (child < size) {
        if (child + 1 < size && heap[child] > heap[child + 1])
            child++;
        if (heap[parent] <= heap[child])
            return;
        swap(&heap[parent], &heap[child]);
        parent = child;
        child = parent << 1 | 1;
    }
}

void up(u64 i) {
    u64 child = i;
    u64 parent = (child - 1) >> 1;
    while (child > 0 && heap[parent] > heap[child]) {
        swap(&heap[parent], &heap[child]);
        child = parent;
        parent = (child - 1) >> 1;
    }
}

void pop() {
    if (size == 0)
        return;
    swap(&heap[0], &heap[--size]);
    down(0);
}

void push(u64 val) {
    heap[size] = val;
    up(size++);
}

bool empty() {
    return size == 0;
}

int main() {
    u64 op;
    while (scanf("%llu", &op), op != 0) {
        if (op == 1) {
            if (empty())
                printf("-1\n");
            else {
                for (u64 i = 0; i < size; i++)
                    printf("%llu ", heap[i]);
                printf("\n");
            }
        } else if (op == 2) {
            u64 val;
            scanf("%llu", &val);
            push(val);
        } else if (op == 3) {
            if (empty())
                printf("-1\n");
            else
                printf("%llu\n", heap[0]);
        } else if (op == 4) {
            if (!empty())
                pop();
        }
    }
    return 0;
}

C++ STL实现

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<uint64_t> heap;
    int op;
    while (cin >> op and op) {
        if (op == 1) {
            if (heap.empty())
                cout << -1;
            else
                for (auto &&i: heap)
                    cout << i << ' ';
            cout << endl;
        } else if (op == 2) {
            uint64_t v;
            cin >> v;
            heap.emplace_back(v);
            // C++20之前
            // push_heap(heap.begin(), heap.end(), greater<int64_t>());
            ranges::push_heap(heap, greater<>());
        } else if (op == 3) {
            if (heap.empty())
                cout << -1 << endl;
            else
                cout << heap.front() << endl;
        } else if (not heap.empty()) {
            // C++20之前
            // pop_heap(heap.begin(), heap.end(), greater<int64_t>());
            ranges::pop_heap(heap, greater<>());
            heap.pop_back();
        }
    }
    return 0;
}

Python 实现

from sys import stdin
from heapq import *
input = stdin.readline
heap = []
while True:
    line = list(map(int, input().split()))
    op = line[0]
    if op == 0:
        break
    if op == 1:
        if len(heap) == 0:
            print(-1)
        else:
            for i in heap:
                print(i, end=" ")
            print()
    elif op == 2:
        heappush(heap, line[1])
    elif op == 3:
        if len(heap) == 0:
            print(-1)
        else:
            print(heap[0])
    elif op == 4:
        if len(heap) != 0:
            heappop(heap);

Java 实现

本来想写的，但是这语言又臭又长又难用的，就去掉了。实现思路参考纯 C 语言实现

E. 严格的考勤

签到题，小学生都会算的时间题，人为算出时间，直接打印即可

思路

打印以下内容

[07-08 13:56] [07-08 16:30]
[07-10 13:58] [07-10 16:36]

Python实现

其他语言自己写

print("[07-08 13:56] [07-08 16:30]")
print("[07-10 13:58] [07-10 16:36]")