算法导论-2025fa-OJ

此为 2025 年秋季学期算法导论课程的线上 OJ 题目汇总。

锯木棒

xiaok 大佬最近又雇佣工人给他锯木棒。把一根长为 $L$ 的木棒锯成两段，他需要支付给工人 $L$ 元钱。xiaok 大佬一开始只有长为 $L$ 的一根木棒，他想把它锯成 $n$ 段，每段长度分别为 $L_1, L_2, ..., L_n$ ，问 xiaok 大佬最少要付给工人多少钱？

输入格式: 第一行包含两个整数 $n, L$ （ $1 < n < 10^3$ ， $n < L < 10^9$ ）。第二行包含 $n$ 个整数 $L_1, L_2, ..., L_n$ （ $0 < L_i < L$ ，且保证 $L_1 + L_2 + ... + L_n = L$ ）。

输出格式: 输出一个整数，表示最小花费。

样例输入:

3 21
8 5 8

样例输出:

题解:
{% tabs algo-oj-1 %}

def solve():
    n, L = map(int, input().split())
    lengths = list(map(int, input().split()))
    
    # 将长度排序
    lengths.sort()
    
    total_cost = 0
    
    while len(lengths) > 1:
        # 取出最小的两个元素（在列表开头）
        first = lengths[0]
        second = lengths[1]
        
        # 计算合并费用
        cost = first + second
        total_cost += cost
        
        # 移除前两个元素
        lengths = lengths[2:]
        
        # 将合并后的结果插入到正确位置以保持有序
        # 使用二分查找找到插入位置
        left, right = 0, len(lengths)
        while left < right:
            mid = (left + right) // 2
            if lengths[mid] <= cost:
                left = mid + 1
            else:
                right = mid
        lengths.insert(left, cost)
    
    print(total_cost)

solve()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long L;
    cin >> n >> L;
    vector<long long> lengths(n);
    for (int i = 0; i < n; ++i) {
        cin >> lengths[i];
    }
    
    // 将长度排序
    sort(lengths.begin(), lengths.end());
    
    long long total_cost = 0;
    
    while (lengths.size() > 1) {
        // 取出最小的两个元素（在列表开头）
        long long first = lengths[0];
        long long second = lengths[1];
        
        // 计算合并费用
        long long cost = first + second;
        total_cost += cost;
        
        // 移除前两个元素
        lengths.erase(lengths.begin());
        lengths.erase(lengths.begin());
        
        // 将合并后的结果插入到正确位置以保持有序
        auto it = upper_bound(lengths.begin(), lengths.end(), cost);
        lengths.insert(it, cost);
    }
    
    cout << total_cost << endl;
    return 0;
}

{% endtabs %}

最长公共子序列

1143. 最长公共子序列 | LeetCode

题目描述: 一个字符串 A 的子串被定义成从A中顺次选出若干个字符构成的串。如 A=“cdaad”，顺次选 1, 3, 5 个字符就构成子串 “cad”，现给定两个字符串，求它们的最长公共子串。

输入格式： 第一行包含两个字符串，用空格分隔。两个字符串的长度均小于 $2000$ 。

输出格式： 输出一个整数，表示最长公共子串的长度。

样例输入:

abccd aecd

样例输出:

题解：

{% tabs algo-oj-2 %}

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    
    # 创建二维DP数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# 读取输入
line = input().split()
s1, s2 = line[0], line[1]

result = lcs_length(s1, s2)
print(result)

{% endtabs %}

矩阵连乘规则

给定 $n$ 个矩阵 $\{A_1, A_2, ..., A_n\}$ ，及 $m$ 个矩阵连乘的表达式，判断每个矩阵连乘表达式是否满足矩阵乘法规则。如果满足，则计算矩阵的最小连乘次数；如果不满足，输出“MengMengDa”。

输入格式:
输入数据由多组数据组成 (不超过 10 组样例)。每组数据格式如下：
第一行包含两个整数 $n$ ( $1 \leq n \leq 26$ ) 和 $m$ ( $1 \leq m \leq 3$ )，表示矩阵的个数。
接下来 $n$ 行，每行包含一个大写字母和两个整数 $r$ 和 $c$ ，分别表示矩阵的行数和列数，其中 $1 < r, c < 100$ 。
接下来 $m$ 行，每行包含一个矩阵连乘的表达式（表达式中矩阵个数满足 $2 \leq k \leq 100$ ，其中 $k$ 为表达式中矩阵个数）。

输出格式:
对于每个矩阵连乘表达式，如果运算不满足矩阵乘法规则 (即左矩阵列数与右矩阵行数不同)，则输出“MengMengDa”；否则输出最小矩阵连乘次数。数据保证结果不超过 $10^9$ 。

样例输入

3 2
A 10 100
B 5 50
C 100 5
ACB
ABC

样例输出

7500
MengMengDa

题解：

{% tabs algo-oj-3 %}

def matrix_chain_multiplication(p):
    """
    p: 维度数组，p[i-1]和p[i]是第i个矩阵的行数和列数
    返回最小乘法次数
    """
    n = len(p) - 1  # 矩阵个数
    if n <= 1:
        return 0
    
    # dp[i][j] 表示第i到第j个矩阵的最小乘法次数
    dp = [[float('inf')] * n for _ in range(n)]
    
    # 单个矩阵乘法次数为0
    for i in range(n):
        dp[i][i] = 0
    
    # 长度从2开始
    for length in range(2, n + 1):  # 子链长度
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

def solve():
    import sys
    
    lines = []
    for line in sys.stdin:
        lines.append(line.strip())
    
    i = 0
    while i < len(lines):
        if not lines[i]:
            i += 1
            continue
            
        n, m = map(int, lines[i].split())
        i += 1
        
        # 读取矩阵信息
        matrix_dims = {}
        for j in range(n):
            parts = lines[i].split()
            name = parts[0]
            r, c = int(parts[1]), int(parts[2])
            matrix_dims[name] = (r, c)
            i += 1
        
        # 处理m个表达式
        for expr_idx in range(m):
            expr = lines[i]
            i += 1
            
            # 检查矩阵连乘是否可能
            matrices = list(expr)
            valid = True
            
            # 检查相邻矩阵是否可以相乘
            dims = []
            for j, mat_name in enumerate(matrices):
                if mat_name not in matrix_dims:
                    valid = False
                    break
                r, c = matrix_dims[mat_name]
                if j == 0:
                    dims.append(r)
                else:
                    # 检查前一个矩阵的列数是否等于当前矩阵的行数
                    if dims[-1] != r:
                        valid = False
                        break
                dims.append(c)
            
            if not valid:
                print("MengMengDa")
            else:
                # 计算最小连乘次数
                min_ops = matrix_chain_multiplication(dims)
                print(min_ops)

solve()

{% endtabs %}

沙子的质量

有 $N$ 堆沙子排成一排，编号为 $1$ 到 $N$ （ $N \leq 300$ ）。每堆沙子的质量为一个整数，不超过 $1000$ 。现在要将这些沙子合并成一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的质量之和。合并后，新堆与相邻的沙子堆相邻。不同的合并顺序会导致不同的总代价。例如，对于 $4$ 堆沙子质量分别为 $1, 3, 5, 2$ ：

先合并第 $1$ 和第 $2$ 堆（代价 $4$ ），得到序列 $4, 5, 2$ ；再合并第 $1$ 和第 $2$ 堆（代价 $9$ ），得到 $9, 2$ ；最后合并（代价 $11$ ），总代价为 $4 + 9 + 11 = 24$ 。
或者，先合并第 $1$ 和第 $2$ 堆（代价 $4$ ），得到 $4, 5, 2$ ；再合并第 $2$ 和第 $3$ 堆（代价 $7$ ），得到 $4, 7$ ；最后合并（代价 $11$ ），总代价为 $4 + 7 + 11 = 22$ 。
目标是找到一种合并顺序，使得总代价最小。输出这个最小总代价。

输入格式:
第一行包含一个整数 $N$ （ $1 \leq N \leq 300$ ）。
第二行包含 $N$ 个整数，表示每堆沙子的质量，用单个空格分隔。每个质量不超过 $1000$ 。

输出格式:
输出一个整数，表示合并沙堆的最小总代价。

样例输入

4
1 3 5 2

样例输出

题解：

{% tabs algo-oj-4 %}

def solve():
    n = int(input())
    weights = list(map(int, input().split()))
    
    # 预计算前缀和，方便快速计算区间和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + weights[i]
    
    # sum[i][j] 表示第i到第j堆沙子的总质量
    def get_sum(i, j):
        return prefix_sum[j + 1] - prefix_sum[i]
    
    # dp[i][j] 表示合并区间[i, j]的最小代价
    # 如果i == j，不需要合并，代价为0
    dp = [[0] * n for _ in range(n)]
    
    # 枚举区间长度，从2开始（长度为1的区间代价为0）
    for length in range(2, n + 1):  # 区间长度
        for i in range(n - length + 1):  # 区间起始位置
            j = i + length - 1  # 区间结束位置
            dp[i][j] = float('inf')
            
            # 枚举分割点k
            for k in range(i, j):  # k在[i, j-1]范围内
                cost = dp[i][k] + dp[k + 1][j] + get_sum(i, j)
                dp[i][j] = min(dp[i][j], cost)
    
    print(dp[0][n - 1])

solve()

{% endtabs %}

求第k小

给定 $n$ 个不同的整数元素（ $1 \leq n \leq 10^6$ ），每个元素在 int 范围内。要求找出第 $k$ 小的数（ $1 \leq k \leq n$ ）。

输入格式:
第一行包含两个整数 $n$ 和 $k$ 。
第二行包含 $n$ 个不同的整数，表示元素，用单个空格分隔。

输出格式:
输出一个整数，表示第 $k$ 小的数。

样例输入

5 2
1 5 3 2 4

样例输出

题解：

{% tabs algo-oj-5 %}

def find_kth_smallest(arr, k):
    arr.sort()
    return arr[k - 1]

n, k = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))

print(find_kth_smallest(arr, k))

{% endtabs %}

快速幂

给定整数 $x$ ，求 $f(x)$ 对 $100000007$ 取余的结果，其中 $f(x) = \sum_{i=1}^{x} i^i + 1$ 。

输入格式:
多组测试样例，最多 $50$ 组。每组测试样例给定一个整数 $x$ （ $1 \leq x \leq 25000$ ）。

输出格式:
对每个样例，输出一行，代表 $f(x)$ 对 $100000007$ 取余的结果。

样例输入:

3
4
5

样例输出:

33
289
3414

题解:：

{% tabs algo-oj-6 %}

def fast_power(base, exp, mod):
    """快速幂算法"""
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:  # 等价于 exp % 2 == 1
            result = (result * base) % mod
        exp >>= 1    # 等价于 exp //= 2
        base = (base * base) % mod
    return result

def solve():
    MOD = 100000007
    MAX_X = 25000
    
    # 预计算前缀和
    cumulative_sum = [0] * (MAX_X + 1)
    current_sum = 0
    
    for i in range(1, MAX_X + 1):
        power_ii = fast_power(i, i, MOD)
        current_sum = (current_sum + power_ii) % MOD
        cumulative_sum[i] = current_sum
    
    # 处理多组输入
    try:
        while True:
            line = input().strip()
            if not line:
                continue
            x = int(line)
            result = (cumulative_sum[x] + 1) % MOD
            print(result)
    except EOFError:
        pass

solve()

{% endtabs %}

排列问题

题目描述: 输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。

输入格式: 单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。

输出格式: 打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。

样例输入:

abc,

样例输出:

abc acb bac bca cab cba

题解:

{% tabs algo-oj-7 %}

def permute_unique(s):
    """生成字符串的所有唯一排列"""
    chars = list(s)
    chars.sort()  # 排序以便去重和按字典序输出
    result = []
    used = [False] * len(chars)
    current = []
    
    def backtrack():
        if len(current) == len(chars):
            result.append(''.join(current))
            return
        
        for i in range(len(chars)):
            # 跳过已使用的字符
            if used[i]:
                continue
            
            # 跳过重复字符：如果当前字符与前一个字符相同，且前一个字符未被使用，则跳过
            # 这样可以避免重复排列
            if i > 0 and chars[i] == chars[i-1] and not used[i-1]:
                continue
            
            current.append(chars[i])
            used[i] = True
            backtrack()
            current.pop()
            used[i] = False
    
    backtrack()
    return result

line = input().strip()
# 移除末尾的逗号
s = line.rstrip(',')

# 生成所有排列
permutations = permute_unique(s)

# 按字典序排序（虽然回溯算法已经能保证字典序，但保险起见再排序一次）
permutations.sort()

# 输出结果
print(' '.join(permutations))

{% endtabs %}

进制转换

题目描述: 输入一个十进制正整数，然后输出它所对应的八进制数。

输入格式: 输入一个十进制正整数n(1≤n≤ $10^6$ )。

输出格式: 输出n对应的八进制数，输出在一行。

样例输入:

样例输出:

题解:

{% tabs algo-oj-8 %}

print(oct(int(input().strip()))[2:])

{% endtabs %}

跳台阶

题目描述: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

输入格式: 多组测试样例。每组测试样例包含一个整数n。( $1 ≤ n ≤ 100$ )

输出格式: 每组测试样例输出一行，表示青蛙跳上n级台阶的跳法数量。所得到的结果模 1000000007。

样例输入:

3
4

样例输出:

3
5

题解:

{% tabs algo-oj-9 %}

def jump_ways(n):
    MOD = 1000000007
    if n == 1:
        return 1
    elif n == 2:
        return 2
    
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, (a + b) % MOD
    return b

while True:
    try:
        n = int(input().strip())
        print(jump_ways(n))
    except EOFError:
        break

{% endtabs %}

迷宫游戏

题目描述: 你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前提下，使得你的得分总和尽可能大。

输入格式: 第一行4个整数 $n (≤500)$ , $m$ , $start$ , $end$ 。 $n$ 表示房间的个数，房间编号从0到(n-1)，m表示道路数，任意两个房间之间最多只有一条道路，start 和 end 表示起点和终点房间的编号。第二行包含n个空格分隔的正整数(不超过600)，表示进入每个房间你的得分。再接下来m行，每行3个空格分隔的整数x, y, z (0<z≤200)表示道路，表示从房间x到房间y(双向)的道路，注意，最多只有一条道路连结两个房间，你需要的时间为z。输入保证从start到end至少有一条路径。

输出格式: 占一行，分别最短时间和相应的最大得分，中间用空格隔开。

样例输入:

样例输出:

21 6

题解:

{% tabs algo-oj-10 %}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef pair<int, int> pii; // (distance, node)
typedef pair<int, pii> pip; // (distance, (score, node))

struct Compare {
    bool operator()(const pip& a, const pip& b) {
        if (a.first != b.first) {
            return a.first > b.first; // 按距离从小到大
        }
        return a.second.first < b.second.first; // 距离相同时，按得分从大到小
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    
    vector<int> scores(n);
    for (int i = 0; i < n; i++) {
        cin >> scores[i];
    }
    
    vector<vector<pii>> graph(n);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }
    
    vector<int> dist(n, INT_MAX);
    vector<int> max_score(n, -1);
    vector<bool> visited(n, false);
    
    dist[start] = 0;
    max_score[start] = scores[start];
    
    priority_queue<pip, vector<pip>, Compare> pq;
    pq.push({0, {scores[start], start}});
    
    while (!pq.empty()) {
        auto [d, node_info] = pq.top();
        auto [score, u] = node_info;
        pq.pop();
        
        if (visited[u]) continue;
        if (u == end) break;
        
        visited[u] = true;
        
        for (auto& [v, w] : graph[u]) {
            int new_dist = d + w;
            int new_score = score + scores[v];
            
            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                max_score[v] = new_score;
                pq.push({new_dist, {new_score, v}});
            } else if (new_dist == dist[v] && new_score > max_score[v]) {
                max_score[v] = new_score;
                pq.push({new_dist, {new_score, v}});
            }
        }
    }
    
    cout << dist[end] << " " << max_score[end] << endl;
    
    return 0;
}

{% endtabs %}

Homework

题目描述 临近开学了，大家都忙着收拾行李准备返校，但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上：目前为止还未开动。暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 5 张试卷，其中 4 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

输入格式: 测试数据包括多组。每组测试数据以两个整数 $M,N$ (1 < $M$ < 20, 1 < $N$ < 10000) 开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 $M$ 行，每行包括两个整数 $T,V$ (1 < $T$ < $N$ , 1 < $V$ < 10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。

输出格式: 对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点2位。提示：float 的精度可能不够，你应该使用 double 类型。

样例输入:

样例输出:

37.00

题解：

{% tabs algo-oj-11 %}

{% endtabs %}

哈夫曼编码

题目描述
给定一只含有小写字母的字符串，输出其哈夫曼编码的长度。

输入格式:
第一行一个整数 $T$ ，代表样例的个数，接下来 $T$ 行，每行一个字符串， $0<T<=2000$ ，字符串长度 $0<L<=1500$ .

输出格式:
对于每个字符串，输出其哈夫曼编码长度。

样例输入:

3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq

样例输出:

10
51
115

题解:

{% tabs algo-oj-12 %}

import heapq
from collections import Counter

def huffman_encoding_length(s):
    if not s:
        return 0
    
    # 统计字符频率
    freq_counter = Counter(s)
    frequencies = list(freq_counter.values())
    
    # 只有一个字符的特殊情况
    if len(frequencies) == 1:
        return frequencies[0]
    
    # 构建最小堆
    heapq.heapify(frequencies)
    total_length = 0
    
    # 哈夫曼合并过程
    while len(frequencies) > 1:
        a = heapq.heappop(frequencies)
        b = heapq.heappop(frequencies)
        new_freq = a + b
        total_length += new_freq
        heapq.heappush(frequencies, new_freq)
    
    return total_length

# 主程序
def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    t = int(data[0])
    results = []
    
    for i in range(1, t + 1):
        s = data[i].strip()
        length = huffman_encoding_length(s)
        results.append(str(length))
    
    sys.stdout.write("\n".join(results))

if __name__ == "__main__":
    main()

{% endtabs %}

汽车费用

题目描述
一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里数来付费。没有一辆车子行驶超过 $10$ 公里，一个顾客打算行驶 $n$ 公里 $(1<=n<100)$ ，他可以通过无限次的换车来完成旅程。要求费用最少。

输入格式:
第一行十个整数分别表示行走 $1$ 到 $10$ 公里的费用 $(<=500)$ 。注意这些数并无实际的经济意义，即行驶 $10$ 公里费用可能比行驶一公里少。第二行一个整数 $n$ 表示，旅客的总路程数。

输出格式:
仅一个整数表示最少费用。

样例输入:

12 21 31 40 49 58 69 79 90 101
15

样例输出:

题解:

{% tabs algo-oj-13 %}

def min_cost_to_travel(costs, n):
    # dp[i] 表示行驶 i 公里的最小费用
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # 行驶 0 公里费用为 0

    for i in range(1, n + 1):
        for j in range(1, 11):  # 检查行驶 1 到 10 公里的费用
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + costs[j - 1])
    
    return dp[n]

# 读取输入
costs = list(map(int, input().strip().split()))
n = int(input().strip())

result = min_cost_to_travel(costs, n)
print(result)

{% endtabs %}

八皇后问题

题目描述
努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 $1$ - $99$ 的数字。他又准备了 $8$ 个皇后棋子。 $8$ 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 $8$ 个皇后所在的位置的数字的和是最大的。

输入格式:
输入一个数字 $k(k≤20)$ ，代表棋盘的数量。接下来有 $k$ 个棋盘，每个棋盘有 $64$ 个数字，分成 $8$ 行 $8$ 列输入，每一个数字均小于 $100$ 。

输出格式:
每一个棋盘对应输出最大的数值，一共输出 $k$ 行。

样例输入:

1
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
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

样例输出:

题解:

{% tabs algo-oj-14 %}

{% endtabs %}

法师康的工人

题目描述
三个法师康的工人每天早上 $6$ 点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在 $200$ 时刻开始（从 $6$ 点开始计时，以秒作为单位）在生产线上开始生产，一直到 $1000$ 时刻。第二个工人，在 $700$ 时刻开始，在 $1100$ 时刻结束。第三个工人从 $1500$ 时刻工作到 $2100$ 时刻。期间最长至少有一个工人在生产线上工作的连续时间为 $900$ 秒（从 $200$ 时刻到 $1100$ 时刻），而最长的无人生产的连续时间（从生产开始到生产结束）为 $400$ 时刻（ $1100$ 时刻到 $1500$ 时刻）。你的任务是用一个程序衡量 $N$ 个工人在 $N$ 条产品线上的工作时间列表（ $1≤N≤5000$ ，以秒为单位）。

最长的至少有一个工人在工作的时间段
最长的无人工作的时间段（从有人工作开始计）

输入格式:
输入第 $1$ 行为一个整数 $N$ ，第 $2$ - $N+1$ 行每行包括两个均小于 $1000000$ 的非负整数数据，表示其中一个工人的生产开始时间与结束时间。

输出格式:
输出为一行，用空格分隔开两个我们所求的数。

样例输入:

样例输出:

900 400

题解:

{% tabs algo-oj-15 %}

{% endtabs %}

数据加密

题目描述
密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。现在要求你用下面给定的方法对数据实现加密。给定长度为 $n$ 的字符串 $S$ （ $1<=n<=2000$ ， $S$ 中只有大写字母）作为明文，要求构造一个字符串 $T$ 作为密文，起初 $T$ 是一个空串，之后反复执行以下任意操作：

从 $S$ 的头部删除一个字符，加入到 $T$ 的尾部
从 $S$ 的尾部删除一个字符，加入到 $T$ 的尾部最后 $S$ 会变成空串， $T$ 会变成一个长度为 $n$ 的字符串作为密文。当然并非所有的构造方案都是符合条件的，我们要求构造出的密文 $T$ 的字典序尽可能小，你能找出这个字典序最小的密文吗？

输入格式:
输入包含多组数据，每组数据占两行，第一行为一个整数 $n$ （ $1<=n<=2000$ ）代表字符串 $S$ 的长度，第二行为一个长度为 $n$ 的字符串 $S$ 代表明文，保证 $S$ 中只有大写字母。

输出格式:
对每组数据，输出一行字符串，代表构造出的字典序最小的密文 $T$ 。

样例输入:

6
ACDBCB

样例输出:

ABCBCD

题解:

{% tabs algo-oj-16 %}

{% endtabs %}

简单的密码

题目描述
密码是按特定法则编成，用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。
现在我们定义一种非常简单的密码，它的长度固定为 $n$ （ $n \leq 30$ ）并且每一位只能由数字 $0$ 或者数字 $1$ 组成，但是有一个特殊的要求：一个密码序列中至少要有连续的 $3$ 个 $0$ 出现才可以，否则就是无效的。现在给定你密码序列的长度 $n$ ，你的任务是计算长度为 $n$ 的序列能产生多少种不同的并且有效的密码？

输入格式:
输入包含多组数据，每组数据只有一个正整数 $n$ （ $1 \leq n \leq 30$ ）代表密码序列的长度，单独占一行。

输出格式:
对每组数据，输出一个整数，代表长度为 $n$ 的序列能产生的不同密码的种类数。

样例 1 输入:

样例 1 输出:

样例 2 输入:

样例 2 输出:

样例 3 输入:

样例 3 输出:

题解：

{% tabs algo-oj-17 %}

{% endtabs %}

有趣的素数

题目描述
素数被广泛地应用于密码学中，所谓的公钥就是将想要传递的信息在编码时加入砠数，编码之后传给收信人，任何人收到此信息之后，若没有此收信人所拥有的秘钥，则在解密的过程中将会因为分解质因数过久而无法破解信息，可见素数在密码学中的重要性。
现在给你 $n$ （ $2 \leq n \leq 16$ ）个正整数 $1,2,3...n$ ，你的任务是把这 $n$ 个正整数组成一个环，使得任意相邻的两个整数之和为一个素数，输出有多少种合法方案。

输入格式:
多组输入数据，每组数据只有一个正整数 $n$ （ $2 \leq n \leq 16$ ）代表有 $n$ 个正整数 $1,2,3...n$ 。

输出格式:
对每组数据，输出一个整数，代表有多少种不同的可行方案数。

样例 1 输入:

样例 1 输出:

样例 2 输入:

样例 2 输出:

题解：

{% tabs algo-oj-18 %}

{% endtabs %}

凯撒加密法

题目描述
凯撒加密法，或称恺撒加密、恺撒变换、变换加密，是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
例如，当偏移量是左移 $3$ 的时候：
明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作，得到原来的明文。例如：
明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
现在给定你一个字符串 $S$ （长度不会超过 $1000000$ ）和一个整数 $k$ （ $-1000000000 \leq k \leq 1000000000$ ），分别代表接受者收到的密文和在加密该密文时向后的偏移量，你的任务是计算出原来的明文。
注意：只有字母在加密时才会发生偏移，其它字符保持不变。

输入格式:
输入包含多组数据，其中第一行为数据组数 $T$ （ $T \leq 10$ ）。
每组数据第一行为一个字符串 $S$ ，由数字、字母以及常见字符组成（不含空格），第二行为一个整数 $k$ 代表加密时向后的偏移量（ $|S| \leq 1000000$ , $-1000000000 \leq k \leq 1000000000$ ）。

输出格式:
对每组数据，输出一行字符串，代表输入中的密文对应的明文。

样例 1 输入:

1
DEFGHIJKLMNOPQRSTUVWXYZABC
3

样例 1 输出:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

题解：

{% tabs algo-oj-19 %}

{% endtabs %}

Vigenère 密码

题目描述
$16$ 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。
在密码学中，我们称需要加密的信息为明文，用 $M$ 表示；称加密后的信息为密文，用 $C$ 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 $k$ 。在 Vigenère 密码中，密钥 $k$ 是一个字母串， $k = k_1k_2...k_n$ 。当明文 $M = m_1m_2...m_n$ 时，得到的密文 $C = c_1c_2...c_n$ ，其中 $c_i = m_i \bigoplus k_i$ 。
Vigenère 加密在操作时需要注意：

$\bigoplus$ 运算忽略参与运算的字母的大小写，并保持字母在明文 $M$ 中的大小写形式；
当明文 $M$ 的长度大于密钥 $k$ 的长度时，将密钥 $k$ 重复使用。例如，明文 $M=$ Helloworld，密钥 $k=$ abc时，密文 $C=$ Hfnlpyosnd。

输入格式:
第一行为一个字符串，表示密钥 $k$ ，长度不超过 $100$ ，其中仅包含大小写字母。
第二行为一个字符串，表示经加密后的密文，长度不超过 $1000$ ，其中仅包含大小写字母。

输出格式:
输出共 $1$ 行，一个字符串，表示输入密钥和密文所对应的明文。

样例 1 输入:

CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

样例 1 输出:

Wherethereisawillthereisaway

题解：

{% tabs algo-oj-20 %}

{% endtabs %}

题目总结为 md 文本的 Prompt：

请将题目描述转换为规范的 Markdown 格式，并严格遵循以下要求：

## 1. 标题处理
- **直接使用标题，即若为 `问题 D: algorithm-沙子的质量`，则标题为 `## 沙子的质量`**
- **仅用 `## ` 开头**（例如 `## 沙子的质量`）

## 2. 公式规范
- **行内公式**：必须用 `$` 包裹（如 `$L$`、`$10^3$`、`$a_i$`）
- **块级公式**：用 `$$` 包裹（仅当题目含复杂推导时使用）
- **禁止**：未包裹的数学符号（如 `10^3` → `$10^3$`）、中文括号混用、$ 符号前后多余空格

## 3. 内容结构（严格按此顺序）
**3.1 题目描述**
- 用普通段落描述题意
- 合并零散换行，确保语句连贯
- 保留关键数字、变量名（如 `n ≤ 10^5` → `n ≤ $10^5$`）
- 保证标点符号为英文符号(如逗号、句号)

**3.2 输入/输出格式**
- **必须使用固定前缀**：
  - `**输入格式:**` + 描述（如"第一行包含整数 $n$"，描述需换行）
  - `**输出格式:**` + 描述（如"输出一个整数表示答案"，描述需换行）
- 保留分隔符说明（如"用**单个空格**分隔"）
- 多组输入时明确标注（如"接下来 $T$ 行，每行..."）

**3.3 样例数据**
- **多组样例必须编号（单组样例无需编号）**：
  - `**样例 1 输入**` → `**样例 1 输出**`
  - `**样例 2 输入**` → `**样例 2 输出**`
- **去除样例后的COPY**
- **代码块规范**：
  需要有 ```input 和 ```output 包裹
  ```input
  5
  1 2 3 4 5

**3.4 题解**
- 用 `**题解**：` 开头
- 代码块用 ```Java 包裹
- 不用给出代码，只需保留代码块标记