UCAS卜算

1st Divide & Conquer

A - 区间最大值不小于和

题目

给一个长度为\(n\)的数组, 目标是判断对数组所有下标对\((i, j)\)（\(1 \leq i \leq j \leq n\)），是否都满足 \(\max(a_i, a_{i+1}, \cdots, a_{j-1}, a_j) \geq a_i + a_{i+1} + \cdots + a_{j-1} + a_j\)（\(1 \leq i \leq j \leq n\)）这个条件。

输入格式：

第一行包含一个整数\(t\)（\(1 \leq t \leq 10^5\)），表示测试用例数量。

每个测试用例包含两行:

1.第一行是一个整数\(n\)（\(1 \leq n \leq 2 \cdot 10^5\)），表示数组的长度。

2.第二行包含 \(n\) 个整数，构成数组 \(a[1..n]\)（\(-10^9 \leq a_i \leq 10^9\)）。

输出格式：

对于每个测试用例，如果对所有下标对\((i, j)\)（\(1 \leq i \leq j \leq n\)），都满足\(\max(a_i, a_{i+1}, \cdots, a_{j-1}, a_j) \geq a_i + a_{i+1} + \cdots + a_{j-1} + a_j\)（\(1 \leq i \leq j \leq n\)）这个条件，则输出 “YES”，否则输出 “NO”

思路

核心思想是将“检查所有子数组”的问题转化为“以每个元素 \(a_i\) 作为最大值的子数组中，是否存在和大于 \(a_i\) 的情况”。

1. 前缀和预处理 (Prefix Sum):

   计算数组 \(a\) 的前缀和数组 \(pre\)，以便在 \(O(1)\) 时间内计算任意子数组的和。

   公式：\(Sum(l, r) = pre[r] - pre[l-1]\)。

2. 确定最大值作用范围 (Monotonic Stack):

   对于每个元素 \(a_i\)，利用单调栈找到它作为最大值的左右边界：

   • \(L[i]\)：左侧第一个严格大于 \(a_i\) 的下标。
   • \(R[i]\)：右侧第一个大于等于 \(a_i\) 的下标（处理相等元素防止重复计算）。
   • \(a_i\) 是区间 \((L[i], R[i])\) 即 \([L[i]+1, R[i]-1]\) 内的最大值。

3. 区间最值查询 (Segment Tree / RMQ):

   在确定的范围 \((L[i], R[i])\) 内，我们需要找到一个子区间 \([l, r]\)（必须包含 \(i\)），使得子数组和最大。

   要使 \(Sum(l, r) = pre[r] - pre[l-1]\) 最大，需满足：

   • \(pre[r]\) 最大，其中 \(r \in [i, R[i]-1]\)。

   • \(pre[l-1]\) 最小，其中 \(l-1 \in [L[i], i-1]\)。

     利用线段树（或稀疏表）维护 \(pre\) 数组的区间最小值和最大值。

4. 校验条件:

   遍历每个 \(i\)，计算 \(max\_sum = \max(pre[i \dots R[i]-1]) - \min(pre[L[i] \dots i-1])\)。

   如果 \(max\_sum > a_i\)，说明存在反例，输出 NO；否则遍历结束后输出 YES。

伪代码

ALGORITHM Check-Subarray-Condition
    INPUT: 
        n: Integer (length of array)
        A: Array of integers A[1...n]
    OUTPUT: 
        "YES" if condition holds, "NO" otherwise

    // 1. Prefix Sums
    P[0] ← 0
    FOR i ← 1 TO n DO P[i] ← P[i-1] + A[i]

    // 2. Monotonic Stack for Boundaries
    // L[i]: First index to left > A[i] (or 0)
    // R[i]: First index to right >= A[i] (or n+1)
    L, R ← Compute-Boundaries-Stack(A) 

    // 3. RMQ Structure (Segment Tree) on Prefix Sums
    Tree ← Build-Segment-Tree(P)

    // 4. Validate Condition
    FOR i ← 1 TO n DO
        // Maximize subarray sum in valid range: P[high] - P[low]
        // high ∈ [i, R[i]-1], low ∈ [L[i], i-1]
        max_P ← Query-Max(Tree, i, R[i] - 1)
        min_P ← Query-Min(Tree, L[i], i - 1)

        IF (max_P - min_P) > A[i] THEN
            RETURN "NO"
        END IF
    END FOR

    RETURN "YES"
END ALGORITHM

复杂度

时间：\(O(N \log N)\)：单调栈 \(O(N)\)，主循环 \(N\) 次，每次线段树查询 \(O(\log N)\)。

空间：\(O(N)\)：前缀和、栈数组、线段树均为线性空间。

B - 能耗最小问题

题目

有一个长度为\(2^n\)的区域，里面一共有k个目标点分布在区域内。

处理区域时，可选择以下两种操作之一：

1.直接处理整个区域，若区域内无目标点，能耗=A；若区域内有目标点，能耗=B×目标点数量×区域长度。

2.分割区域再处理，若当前区域长度大于等于2，将其等分为两个子区域，分别计算两个子区域的最小能耗，当前区域能耗等于两个子区域能耗之和，得到的子区域同样可以用两种操作继续处理。

如何处理能让能耗最小？

输入：

1.第一行是四个整数\(n, k, A, B\)（\(1 \leq n \leq 30, 1 \leq k \leq 10^5, 1 \leq A, B \leq 10^4\)），其中\(n\)表示区域的长度为\(2^n\)，\(k\)表示一共有个\(k\)目标点，\(A\)表示当一个区域内没有目标点时，直接处理这个空区域所需的能耗，\(B\)表示当区域内有目标点时，计算能耗的系数。

2.第二行包含\(k\)个整数，\(a_1, a_2, a_3, \cdots, a_k\)（\(1 \leq a_i \leq 2^n\)） ，每个\(a_i\)表示目标点的位置。

输出：

输出一个整数，表示处理该区域所需的最小能耗。

算法思路

本题采用 分治算法 (Divide and Conquer) 求解，核心在于利用“排序+二分查找”来加速稀疏区间的查询。

1. 预处理：排序 (Sorting)
   • 将所有目标点的位置数组 \(Pos\) 按升序排序。
   • 目的：排序后，任意物理区间 \([L, R]\) 内的目标点在 \(Pos\) 数组中也是连续存储的。我们可以通过维护两个下标 \(idx\_start\) 和 \(idx\_end\) 来标识当前区间包含的目标点范围，从而在 \(O(1)\) 时间内算出点数。
2. 分治递归 (Recursive Strategy)
   • 定义函数 Solve(L, R, idx_start, idx_end) 处理物理区间 \([L, R]\)。
   • 计算点数：\(count = idx\_end - idx\_start\)。
3. 决策逻辑 (Decision Logic)
   • 操作一：整体处理 (Whole Processing)
     • 若 \(count == 0\)（空区间）：能耗为 \(A\)。
     • 若 \(count > 0\)（非空）：能耗为 \(B \times count \times (R - L + 1)\)。
   • 操作二：分割处理 (Split Processing)
     • 若区间长度为 1（叶子节点）：无法分割，返回整体处理的能耗。
     • 若区间长度 \(> 1\)：
       • 计算物理中点 \(mid = \lfloor (L+R)/2 \rfloor\)。
       • 利用 二分查找 在 \(Pos[idx\_start \dots idx\_end-1]\) 中找到第一个大于 \(mid\) 的下标 \(idx\_mid\)。
       • 递归计算：\(Cost_{split} = Solve(Left) + Solve(Right)\)。
   • 最优解：\(Result = \min(Cost_{whole}, Cost_{split})\)。

伪代码

ALGORITHM Minimize-Energy
    INPUT: 
        n, k, A, B: Integers
        Pos: Array of target positions [1...k]
    OUTPUT: 
        Minimum energy consumption

    // 1. Sort for binary search strategy
    Sort Pos in ascending order

    // 2. Start recursion covering full range [1, 2^n]
    // Index range [1, k+1) covers all targets
    RETURN Solve(1, 2^n, 1, k + 1)

    // Recursive Helper Function
    FUNCTION Solve(L, R, idx_start, idx_end)
        count ← idx_end - idx_start
        
        // Base Case 1: Empty region
        IF count = 0 THEN RETURN A

        length ← R - L + 1
        cost_whole ← B * count * length

        // Base Case 2: Leaf node (cannot split)
        IF L = R THEN RETURN cost_whole

        // Recursive Step: Try splitting
        mid ← floor((L + R) / 2)
        
        // Find split index: first element > mid
        idx_mid ← BinarySearch_UpperBound(Pos, mid, idx_start, idx_end)

        cost_split ← Solve(L, mid, idx_start, idx_mid) + 
                     Solve(mid + 1, R, idx_mid, idx_end)

        RETURN Min(cost_whole, cost_split)
    END FUNCTION

END ALGORITHM

复杂度

1. 时间复杂度 (Time Complexity):

   \[O(n \cdot k \cdot \log k)\]

   • 排序：耗时 \(O(k \log k)\)。
   • 递归树结构：虽然总空间大小是 \(2^n\)，但这是一个稀疏递归。程序在遇到空区间时会立即返回 \(A\)，不再分裂。因此，只有包含目标点的节点及其直接兄弟节点会被访问。
   • 计算量：每一层（共 \(n\) 层）被处理的有效节点数与目标点数量 \(k\) 呈线性关系。每个节点内部执行一次二分查找，耗时 \(O(\log k)\)。
   • 总计：\(O(k \log k + n \cdot k \log k) \approx O(n k \log k)\)。

2. 空间复杂度 (Space Complexity):

   \[O(n + k)\]

   • 辅助空间：存储 \(Pos\) 数组占用 \(O(k)\)。
   • 栈空间：递归深度最大为 \(n\)，占用 \(O(n)\)。

C - 稠密有向无环图的构造

题目

给定正整数\(n\)，需要构建一个包含\(n\)个顶点的简单有向无环图。使得距离为\(2\)的点对的个数\(k\geq \frac{n(n-1)}{2} - n \lceil \log_2 n \rceil\)。点对(\(u\),\(v\))之间的距离指\(u\)到\(v\)的最短路长度。

示例：现有一个有向无环图，其边集为\(1→2、1→4、2→3、4→3、4→5、3→5\)； 则该图中距离为\(2\)的点对的个数\(k\)为\(3\)，分别是\(1→3、1→5、2→5\)。

算法思路

该算法采用 分治法 (Divide and Conquer) 思想，递归地构建一个类似“二叉搜索树”结构的图，利用枢纽节点（Pivot）最大化路径长度为 2 的点对数量。

1. 枢纽选择：在当前区间 \([L, R]\) 中选择中点 \(mid\) 作为枢纽节点（Pivot）。
2. 构建桥梁：
   • 将左区间 \([L, mid-1]\) 中的所有节点直接指向枢纽 \(mid\)。
   • 将枢纽 \(mid\) 直接指向右区间 \([mid+1, R]\) 中的所有节点。
   • 效果：左区间任意节点 \(u\) 和右区间任意节点 \(v\) 之间必然存在一条路径 \(u \to mid \to v\)，其长度恰好为 2。
3. 递归处理：对左右子区间重复上述过程，填补内部的边。
4. 结果：通过这种层级化的连接，每一层递归都建立了大量跨越左右区域的长度为 2 的路径，从而满足题目关于 \(k\) 的下界要求。

伪代码

ALGORITHM Construct-Dense-DAG
    INPUT: 
        n: Integer (number of vertices)
    OUTPUT: 
        Edges: List of directed edges (u, v)

    // Main entry point
    FUNCTION Main()
        Edges ← Empty List
        // Start recursion on the full range [1, n]
        Solve(1, n, Edges)
        RETURN Edges
    END FUNCTION

    // Recursive Divide and Conquer Procedure
    PROCEDURE Solve(L, R, Edges)
        // Base Case: If the range has less than 2 nodes, no edges needed
        IF L ≥ R THEN
            RETURN
        END IF

        // 1. Select Pivot (Middle element)
        mid ← floor((L + R) / 2)

        // 2. Connect Left Sub-range to Pivot [L...mid-1] -> mid
        FOR u ← L TO mid - 1 DO
            Append (u, mid) to Edges
        END FOR

        // 3. Connect Pivot to Right Sub-range mid -> [mid+1...R]
        FOR v ← mid + 1 TO R DO
            Append (mid, v) to Edges
        END FOR

        // 4. Recursively process sub-ranges
        Solve(L, mid - 1, Edges)
        Solve(mid + 1, R, Edges)

    END PROCEDURE
END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(n \log n)\)
   • 递归深度：每次将区间减半，递归树深度为 \(\log_2 n\)。
   • 每层操作：在每一层递归中，区间内的每个节点（除了枢纽自身）都会被访问一次并创建一条边。每一层的总操作量约为 \(O(n)\)。
   • 总复杂度：层数 \(\times\) 每层操作量 = \(O(n \log n)\)。
2. 空间复杂度 (Space Complexity): \(O(n \log n)\)
   • 存储边集：生成的边数等于时间复杂度，即 \(O(n \log n)\)，这是存储输出所需的空间。
   • 递归栈：栈深度为 \(O(\log n)\)。
   • 总空间：由输出规模主导，为 \(O(n \log n)\)。

D - “中间数”计数问题

题目

初始时，集合\(S\)中只有元素\(1\)。给定一个正整数\(N\)，

需要不断对\(S\)执行以下操作，直到不能继续为止：

1. 在\(1\)到\(N\)（包含\(1\)和\(N\)）的范围内，找出所有的正整数\(x\)，使满足\(\min_{y \in S} |x - y|\)最大且大于\(1\)。
2. 若\(x\)唯一，将其加入\(S\)；
3. 若这样的\(x\)有多个，挑出其中最小的那个，将其加入\(S\)；
4. 当再也找不到符合条件的\(x\)时，停止操作。

最后，求集合\(S\)中元素的总个数。

输入格式：

共一行。

第一行，一个正整数\(N\)。

输出格式：

共一行。

第一行，一个正整数表示最终集合\(S\)中元素的总个数。

算法思路

本题本质是模拟区间递归分割的过程，采用 分治法 结合 记忆化搜索 求解。

1. 分治逻辑：

   • 寻找满足条件的 \(x\) 实质上是在寻找当前区间 \([1, r]\) 的中点。

   • 将长度为 \(r\) 的区间从“中点”分为左右两段。由于“中点”同时属于左、右子区间，根据 容斥原理，总点数计算公式为：

     \[Count(Total) = Count(Left) + Count(Right) - 1\]

2. 状态转移：

   • 若 \(r\) 为奇数：中点使得左右区间长度相等，均为 \((r+1)/2\)。
   • 若 \(r\) 为偶数：中点使得左区间长度为 \(r/2\)，右区间长度为 \(r/2 + 1\)。

3. 基准情形：

   • 当区间长度 \(r \le 2\) 时，无法再插入满足“距离 \(>1\)”的点，仅含端点，返回 1。
   • 当 \(r=3\) 时，区间为 \([1, 3]\)，插入 \(2\)，共 2 个点。

4. 优化：

   • 由于递归中 \(r\) 的值呈指数衰减，且存在大量重复子问题（如 \(DFS(100)\) 和 \(DFS(101)\) 都会用到 \(DFS(50)\)），利用哈希表记录已计算结果，将复杂度降至对数级。

伪代码

ALGORITHM Count-Intermediate-Numbers
    INPUT: 
        N: Positive Integer (Range limit)
    OUTPUT: 
        Total number of elements in Set S

    // Global Memoization Table to store results for range length r
    GLOBAL Memo ← Empty Hash Map

    FUNCTION Main()
        // Start recursion with the full range length N
        result ← DFS(N)
        PRINT result
    END FUNCTION

    FUNCTION DFS(r)
        // 1. Check Memoization Cache
        IF r is in Memo THEN
            RETURN Memo[r]
        END IF

        // 2. Base Cases
        IF r ≤ 2 THEN
            // Range too small to add intermediate points (gap <= 1)
            // Effectively counts the starting point of the segment
            RETURN 1
        ELSE IF r = 3 THEN
            // Special case: [1, 2, 3] -> 2 points (e.g., {1, 3} logic in code base)
            RETURN 2
        END IF

        // 3. Divide Step
        // Calculate split point based on parity
        mid_len ← floor((r + 1) / 2)

        IF (r mod 2) = 0 THEN
            // Even case: Splits into unequal halves
            // e.g., 4 splits to lengths 2 and 3
            left_count  ← DFS(mid_len)
            right_count ← DFS(mid_len + 1)
            total ← left_count + right_count - 1
        ELSE
            // Odd case: Splits into equal halves
            // e.g., 5 splits to lengths 3 and 3
            sub_count ← DFS(mid_len)
            total ← 2 * sub_count - 1
        END IF

        // 4. Store and Return
        Memo[r] ← total
        RETURN total
    END FUNCTION

END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(\log N)\)
   • 每次递归 \(r\) 近似减半。在递归树中，虽然节点看似很多，但不同的参数 \(r\) 值非常稀疏。
   • 对于输入 \(N\)，仅会出现形如 \(\lfloor N/2^k \rfloor\) 或 \(\lceil N/2^k \rceil\) 的值。独立状态数约为 \(2 \log N\)。
   • 配合记忆化搜索，每个状态仅计算一次。
2. 空间复杂度 (Space Complexity): \(O(\log N)\)
   • 栈空间：递归深度为 \(\log N\)。
   • 存储空间：哈希表存储的独立状态数也为 \(O(\log N)\)。

2st Dynamic Programming 1

A - 前缀和非负的排序数

题目

有 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 排成一个长度为 \(2n\) 的序列，要求任意前缀和 \(\ge 0\)​，问有多少种不同的排列。数据范围 \(0 \leq n \leq 20\)。

输入输出格式

项目	格式
输入	一个整数 \(n\)，代表 \(+1\) 和 \(-1\) 的个数
输出	一个整数，代表满足条件的排列数

算法思路

该问题即求解 卡特兰数 (Catalan Number)，但通过 动态规划 (Dynamic Programming) 求解。

1. 状态定义：设 \(dp[b]\) 表示当前处理了若干个数字后，前缀和（Balance） 为 \(b\) 的方案数。
2. 状态转移：遍历总步数 \(s\)（从 0 到 \(2n-1\)）。对于每一个可能的前缀和 \(b\)：
   • 计算已使用的 \(+1\) 个数 (\(plus\)) 和 \(-1\) 个数 (\(minus\))。
   • 放置 +1：若 \(plus < n\)，则可以将当前状态转移到新的前缀和 \(b+1\)。
   • 放置 -1：若 \(b > 0\)（保证非负前缀和）且 \(minus < n\)，则可以将当前状态转移到新的前缀和 \(b-1\)。
3. 滚动数组：每一轮迭代生成一个新的 \(ndp\) 数组覆盖旧的 \(dp\)，以此推进步数。
4. 结果：迭代 \(2n\) 步后，\(dp[0]\) 即为最终回到原点（总和为 0）且过程始终非负的方案数。

伪代码

ALGORITHM Count-Valid-Permutations
    INPUT: n (Integer)
    OUTPUT: count (Integer)

    // Handle edge case based on code logic
    IF n = 0 THEN
        RETURN 0
    END IF

    // dp[b] stores the number of paths ending with balance b
    // Size needs to accommodate max balance n
    Initialize array dp[0...2n] with 0
    dp[0] ← 1

    // Iterate through each step of the sequence
    FOR s ← 0 TO 2n - 1 DO
        Initialize array ndp[0...2n] with 0
        
        // Iterate through all possible balances
        FOR b ← 0 TO s + 1 DO
            IF dp[b] = 0 THEN CONTINUE

            // Calculate used counts of +1 and -1
            plus_used ← (s + b) / 2
            minus_used ← s - plus_used

            // Transition 1: Add a +1
            IF plus_used < n THEN
                ndp[b + 1] ← ndp[b + 1] + dp[b]
            END IF

            // Transition 2: Add a -1
            // Condition b > 0 ensures prefix sum remains non-negative
            IF b > 0 AND minus_used < n THEN
                ndp[b - 1] ← ndp[b - 1] + dp[b]
            END IF
        END FOR

        // Update state for next step
        dp ← ndp
    END FOR

    RETURN dp[0]

END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(n^2)\)
   • 外层循环遍历步数 \(s\)，执行 \(2n\) 次。
   • 内层循环遍历前缀和 \(b\)，最大不超过 \(n\)（实际上是 \(\min(s, n)\)）。
   • 总操作次数约为 \(n + (n-1) + \dots \approx n^2\) 量级。
   • 对于 \(n=20\)，计算量非常小。
2. 空间复杂度 (Space Complexity): \(O(n)\)
   • 需要两个数组 dp 和 ndp，长度约为 \(2n\)。
   • 空间消耗随 \(n\) 线性增长。

B - 最大路径权重问题

题目描述

给定一个\(n×m\)的矩阵\(A\)，元素 \(a_{i,j} \ge 0\)。

定义一条路径是从 \((1,1)\) 到 \((n,m)\)，每一步只能向右或向下移动的点的序列。

一条路径的权值是路径上所有点的 \(a_{i,j}\) 之和。

设 \(P\) 是所有路径的集合。

现允许将矩阵中恰好一个元素的值改为 \(0\)。

对于任意修改方案\(M\)（即选择一个位置 \((p,q)\) 将其值置 \(0\)），定义：

\[ F(M) = \max_{\pi \in P} \text{weight}(\pi \mid M) \]

其中 \(\text{weight}(\pi \mid M)\) 是在修改 \(M\) 下路径 \(\pi\) 的权值。

请求出：

\[ \min_{M} F(M) \]

输入：

第一行两个整数 \(n,m\)。

下面 \(n\) 行每行 \(m\) 个整数 \(a_{i,j}\)

输出：

输出一个整数，表示所有修改方案中最大路径权重的最小值。

算法思路

可利用 动态规划 (DP) 和 对角线特性 将时间复杂度从暴力枚举的 \(O(N^2 M^2)\) 优化至 \(O(NM)\)。

1. 双向 DP 预处理：
   • 计算 \(F[i][j]\)：从起点 \((1,1)\) 到 \((i,j)\) 的最大路径和。
   • 计算 \(G[i][j]\)：从 \((i,j)\) 到终点 \((n,m)\) 的最大路径和。
   • 经过点 \((i,j)\) 的最大路径总权重为 \(Val(i,j) = F[i][j] + G[i][j] - A[i][j]\)。
2. 对角线分组 (Diagonal Grouping)：
   • 关键性质：任意从起点到终点的路径，必然经过且仅经过一次满足 \(i+j=k\) 的某条对角线上的一个点。
   • 对于每个对角线和 \(k\) (\(2 \le k \le n+m\))，记录该对角线上所有点对应的 \(Val(i,j)\) 中的 最大值 (\(D1[k]\)) 和 次大值 (\(D2[k]\))。
3. 枚举与决策：
   • 遍历每个点 \((p,q)\) 作为被修改点（变 0）。
   • 经过 \((p,q)\) 的路径：新权重为 \(Val(p,q) - A[p][q]\)。
   • 不经过 \((p,q)\) 的路径：这些路径必须经过对角线 \(p+q\) 上的其他点。若 \(Val(p,q)\) 是该对角线的最大值，则不经过它的最大路径为次大值 \(D2[p+q]\)；否则为最大值 \(D1[p+q]\)。
   • 当前方案的最大路径为 \(\max(\text{经过}, \text{不经过})\)，取所有方案的最小值。

Pseudo-code

ALGORITHM Min-Max-Path-Optimized
    INPUT: n, m, Matrix A[1...n][1...m]
    OUTPUT: min_ans
    Initialize F[n+2][m+2], G[n+2][m+2] with -INFINITY
    F[1][1] ← A[1][1]
    FOR i ← 1 TO n DO
        FOR j ← 1 TO m DO
            IF i=1 AND j=1 CONTINUE
            F[i][j] ← A[i][j] + MAX(F[i-1][j], F[i][j-1])
        END FOR
    END FOR
    G[n][m] ← A[n][m]
    FOR i ← n DOWNTO 1 DO
        FOR j ← m DOWNTO 1 DO
            IF i=n AND j=m CONTINUE
            G[i][j] ← A[i][j] + MAX(G[i+1][j], G[i][j+1])
        END FOR
    END FOR
    Initialize D1[n+m+2], D2[n+m+2] with 0
    FOR i ← 1 TO n DO
        FOR j ← 1 TO m DO
            val ← F[i][j] + G[i][j] - A[i][j]
            k ← i + j
            IF val > D1[k] THEN
                D2[k] ← D1[k]
                D1[k] ← val
            ELSE IF val > D2[k] THEN
                D2[k] ← val
            END IF
        END FOR
    END FOR
    min_ans ← INFINITY
    FOR p ← 1 TO n DO
        FOR q ← 1 TO m DO
            pass_zero ← F[p][q] + G[p][q] - 2 * A[p][q] // Value if A[p][q] becomes 0
            k ← p + q
            orig_val ← F[p][q] + G[p][q] - A[p][q]
            // If current point contributed to the max on diagonal, take second max
            no_pass ← (orig_val == D1[k]) ? D2[k] : D1[k]
            min_ans ← MIN(min_ans, MAX(pass_zero, no_pass))
        END FOR
    END FOR
    RETURN min_ans
END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(NM)\)
   • 计算 \(F\) 和 \(G\) 需要遍历矩阵两次，耗时 \(O(NM)\)。
   • 计算对角线最大值/次大值需要遍历矩阵一次，耗时 \(O(NM)\)。
   • 最终枚举 \((p,q)\) 计算答案需要遍历矩阵一次，耗时 \(O(NM)\)。
   • 总时间复杂度线性于矩阵元素个数。
2. 空间复杂度 (Space Complexity): \(O(NM)\)
   • 需要 \(F\) 和 \(G\) 两个辅助矩阵，以及 \(A\) 本身，空间为 \(O(NM)\)。
   • \(D1\) 和 \(D2\) 数组大小为 \(O(N+M)\)，相对可忽略。

C - 最小化最大值之和

题目

给出一个长度为n的序列h，请将h分成若干段，满足每段数字之和都不超过m，并最小化每段的最大值之和。

输入的第一行包含两个整数n和m。第2到第(n+1)行表示序列h，每行一个整数。

输出一行一个整数表示答案。

算法思路

该算法使用 动态规划 (DP) 结合 单调队列 和 双栈优化 来解决问题。

1. DP状态定义：设 \(f[i]\) 为将前 \(i\) 个数分成若干段，且每段和不超过 \(m\) 的最小“每段最大值之和”。

   状态转移方程为：\(f[i] = \min_{j < i} \{ f[j] + \max(h[j+1 \dots i]) \}\)，其中 \(\sum_{k=j+1}^i h[k] \le m\)。

2. 单调队列优化：

   • 维护一个存储下标的单调递减队列 \(q\)。对于队列中相邻的两个下标 \(q[k]\) 和 \(q[k+1]\)，区间 \((q[k], q[k+1]]\) 内的最大值即为 \(h[q[k+1]]\)。
   • 这使得转移方程转化为寻找队列中某位置对应的 \(f[\dots] + h[q[k]]\) 的最小值。

3. 双栈模拟队列 (Min-Queue)：

   • 为了在 \(O(1)\) 时间内查询队列中所有候选转移值的最小值，代码使用两个栈（左栈、右栈）来模拟队列。
   • 左栈负责队头弹出，右栈负责队尾推入。当左栈为空需要弹出时，将右栈元素重构（Rebuild）倒序填入左栈。
   • 每个栈元素维护当前栈状态下的最小值，从而实现全局最小值的快速查询。

Pseudo-code

ALGORITHM Minimize-Max-Sum
    INPUT: n, m, array h[1...n]
    OUTPUT: f[n]

    Initialize f[0...n] with 0
    Initialize Monotonic Queue Q with Two Stacks (LeftStack, RightStack)
    // q stores indices, tmpf stores potential transition values
    
    st ← 1, current_sum ← 0

    FOR i ← 1 TO n DO
        current_sum ← current_sum + h[i]
        
        // 1. Maintain Window Constraint (sum <= m)
        WHILE current_sum > m DO
            current_sum ← current_sum - h[st]
            st ← st + 1
        END WHILE

        // 2. Maintain Monotonicity (Decreasing h)
        // Remove elements from back if they are smaller than current h[i]
        WHILE Q is not empty AND h[Q.back] ≤ h[i] DO
            PopBack(Q) // Updates RightStack pointers
        END WHILE

        // 3. Calculate transition value for current element
        // If Q empty, prev segment ends at st-1, else at Q.back
        prev_idx ← (Q is empty) ? (st - 1) : Q.back
        val ← f[prev_idx] + h[i]
        
        // 4. Push current index and value to Queue
        PushBack(Q, i, val) // Pushes to RightStack

        // 5. Remove expired elements from front
        WHILE Q.front < st DO
            PopFront(Q) // Updates LeftStack; Rebuilds if LeftStack empty
        END WHILE

        // 6. Calculate DP value
        // Case A: Max is h[Q.front], prev segment ends at st-1
        option1 ← f[st - 1] + h[Q.front]
        // Case B: Minimum from the optimized stacks
        option2 ← GetMin(LeftStack, RightStack)
        
        f[i] ← MIN(option1, option2)
    END FOR

    RETURN f[n]
END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(N)\)
   • 遍历：主循环遍历 \(i\) 从 1 到 \(n\)。
   • 窗口调整：指针 \(st\) 单调向右移动，最多移动 \(n\) 次。
   • 单调队列操作：每个元素最多进队（Push）一次，出队（Pop）一次。
   • 双栈重构：虽然 rebuild 看起来耗时，但在均摊分析下，每个元素只会被移动到左栈一次。因此所有栈操作的均摊复杂度为 \(O(1)\)。
   • 总时间复杂度为线性。
2. 空间复杂度 (Space Complexity): \(O(N)\)
   • 需要数组 \(h, f, q, tmpf\) 以及栈结构，大小均与 \(N\) 成正比。

D - 合法的h序列

题目

对于某个整数序列 \(h_1, h_2, ..., h_n\)，定义一种操作：选取一个位置 i，满足 1 ≤ i < n 且 \(h_i,h_(i+1)≥1\)，令 \(h_i\) 和 \(h_(i+1)\) 同时减 1。

称一个序列是合法的，当且仅当能通过若干次操作，使它所有位置上的值相等。

现在给出 n 和每个位置上 \(h_i\) 的上界 \(H_i\)（即 0 ≤ \(h_i\) ≤ \(H_i\) ），问有多少个合法的 h 序列。

输入格式：

输入的第一行包含 n 。第二行包含 \(H_1, H_2, ..., H_n\)

输出格式：

输出符合条件的 n 元组数量，对 \(10^9 + 7\) 取模。

算法思路

1. 数学模型转换
   • 设 \(x_i\) 为对相邻位置 \((i, i+1)\) 执行减法操作的次数。若序列 \(h\) 最终能变为全 \(t\) 序列，则需满足：\(h_i = x_{i-1} + x_i + t\)（约定 \(x_0 = x_n = 0\)）。
   • 给定上界 \(H_i\)，即约束条件为：\(0 \le x_{i-1} + x_i \le H_i - t\)，且所有 \(x_i \ge 0\)。
2. 分类讨论
   • \(n\) 为偶数：交错和 \(\sum (-1)^i h_i = 0\)，此时常数 \(t\) 对合法性无独立影响。计算 \(t=0\) 时满足 \(x_{i-1} + x_i \le H_i\) 的序列 \(x\) 数量即可覆盖所有合法 \(h\)。
   • \(n\) 为奇数：交错和 \(\sum (-1)^i h_i = t\)，说明每个 \(h\) 序列唯一对应一个 \(t\)。需遍历 \(t \in [0, \min(H)]\)，累加满足 \(x_{i-1} + x_i \le H_i - t\) 的方案数。
3. 动态规划优化
   • 状态 \(dp[v]\) 表示当前位置操作次数为 \(v\) 的方案数。
   • 转移方程：\(dp_{new}[u] = \sum_{v=0}^{M_i - u} dp[v]\)。利用前缀和将转移优化至 \(O(1)\)，总复杂度线性。

伪代码

ALGORITHM Count-Legal-Sequences
INPUT: n, H[1...n]
OUTPUT: count
FUNCTION Solve-DP(M)
    dp ← [1]
    FOR i ← 1 TO n DO
        L ← M[i]
        IF L < 0 THEN RETURN 0
        S ← PrefixSum(dp)
        dp_new ← Array(L + 1)
        FOR u ← 0 TO L DO
            v_max ← MIN(Size(dp) - 1, L - u)
            IF v_max >= 0 THEN dp_new[u] ← S[v_max]
        END FOR
        dp ← dp_new
    END FOR
    RETURN dp[0]
IF n % 2 == 0 THEN
    PRINT Solve-DP(H)
ELSE
    ans ← 0
    FOR t ← 0 TO MIN(H) DO
        ans ← (ans + Solve-DP(H - t)) % MOD
    END FOR
    PRINT ans
END ALGORITHM

复杂度分析

• 时间复杂度
  • \(n\) 为偶数：\(O(n \cdot \max(H))\)。仅需执行一次 DP，每层状态数为 \(O(H)\)。
  • \(n\) 为奇数：\(O(n \cdot \max(H)^2)\)。需枚举 \(t\)（共 \(O(H)\) 次），每次执行 \(O(n \cdot H)\) 的 DP。
• 空间复杂度: \(O(\max(H))\)。
  • 仅需存储当前层和前缀和数组，空间随 \(H\) 线性增长。

3st Dynamic Programming 1

A - 最短序列长度

题目描述

有一个序列 \(S\) 。序列 \(S\) 由 \(0\)，\(1\) 和 \(2\) 构成。对序列 \(S\) 可以执行任意次操作，每次操作都为以下三种操作之一：

• 将任意一个 \(2\) 改为 \(0\) 或 \(1\)。
• 选择两个相邻的 \(0\) 删除，并将剩下的部分连接起来。
• 选择两个相邻的 \(1\) 删除，并将剩下的部分连接起来。

求能得到的最短序列的长度。

输入：

输入一个长度为 \(n\) 的字符串（\(1\leq n\leq 2 \times 10^5\)）。字符串由数字 \(0\)，\(1\) 和 \(2\) 构成，表示初始序列 \(S\)。

输出：

输出一个整数，表示能得到的最短序列的长度

算法思路

该问题可以抽象为栈消除模型。由于序列最终能通过消除相邻的 \(00\) 或 \(11\) 缩减，任何序列最终都会被简化为一个交替序列（如 \(0101...\) 或 \(1010...\)）。

1. 交替栈性质：
   • 一个交替序列由其长度和末尾字符（栈顶）唯一确定。
   • 例如，末尾为 \(0\) 且长度为 \(3\) 的序列必然是 \(010\)。
   • 当新加入字符 \(c\) 时：
     • 若 \(c\) 与栈顶相同，发生消除：长度减 \(1\)，栈顶变为原倒数第二位字符（即 \(1-c\)）。
     • 若 \(c\) 与栈顶不同，发生增长：长度加 \(1\)，栈顶变为 \(c\)。
2. 通配符处理：
   • 数字 \(2\) 可以是 \(0\) 或 \(1\)。这会导致多种可能的栈状态。
   • 由于交替序列的特性，对于固定的栈顶字符，所有可能的长度具有相同的奇偶性。因此，我们可以用一个区间 \([min\_len, max\_len]\) 来维护每种栈顶字符对应的可能长度范围。
3. 动态规划 (DP)：
   • 维护状态 States[top] = \([L, H]\)，表示以 top (0, 1 或 None) 为栈顶时，交替序列长度的最小值和最大值。
   • 遍历字符串，根据当前字符的身份更新所有状态。
   • 最终结果为所有可能状态中最小长度的全局最小值。

伪代码

ALGORITHM Shortest-Sequence-Length
    INPUT: String S of length n
    OUTPUT: Minimum possible length
    States ← {None: [0, 0]}
    FOR each char c IN S DO
        NextStates ← Empty Map
        Identities ← (c == '2') ? {0, 1} : {Integer(c)}
        FOR id IN Identities DO
            FOR top, [low, high] IN States DO
                IF top == None THEN
                    UpdateRange(NextStates, id, 1, 1)
                ELSE IF id == top THEN
                    IF low == 1 THEN
                        UpdateRange(NextStates, None, 0, 0)
                        low_next ← 2
                    ELSE
                        low_next ← low - 1
                    END IF
                    high_next ← high - 1
                    IF high_next >= low_next THEN
                        UpdateRange(NextStates, 1 - id, low_next, high_next)
                    END IF
                ELSE
                    UpdateRange(NextStates, id, low + 1, high + 1)
                END FOR
            END FOR
        END FOR
        States ← NextStates
    END FOR
    RETURN MIN(low for all [low, high] in States)
END ALGORITHM

复杂度分析

• 时间复杂度：\(O(n)\)。我们只需遍历一次长度为 \(n\) 的字符串。在每一步中，由于 States 最多只有 \(3\) 个键（\(0, 1, None\)），更新操作是常数时间的。
• 空间复杂度：\(O(1)\)。虽然输入占用了 \(O(n)\) 空间，但算法执行过程中仅需维护固定数量的状态变量（三个长度区间），与 \(n\) 无关。

B - 放石头

题目

有 \(k\) 种颜色的石头，知道每种颜色的石头的数量，需要将石头放成一排，要求：

• 第一块和最后一块石头的颜色为 \(p,q\)
• 相邻的石头颜色不能相同

如果存在满足条件的排列方案，输出 \(1\)，如果没有合法方案则输出 \(0\)。

输入格式：

第一行输入三个整数 \(k,p,q\) 分别代表石头有 \(k\) 种颜色，第一块和最后一块的石头颜色分别是 \(p,q\)，第二行输入 \(k\) 个数，第 \(j\) 个数表示颜色为 \(j\) 的石头的数量。

输出格式：

整数 \(0\)或 \(1\)，有解输出 \(1\)，无解输出 \(0\)。

算法思路

该问题属于组合构造的可行性判定。核心思想是利用鸽巢原理（Pigeonhole Principle）及其变体，判断在“相邻元素不同色”且“首尾颜色固定”的约束下，是否存在合法的排列。

1. 首尾预留：

   题目固定了第一块为颜色 \(p\)，最后一块为颜色 \(q\)。因此，我们首先从对应的颜色计数中扣除这两块石头。如果某种颜色的石头数量在扣除后变为负数，则直接不可行。

2. 核心判定准则：

   对于 \(n\) 个位置的排列，若要满足相邻不同色，任意颜色 \(i\) 的数量 \(C_i\) 必须满足：

   \[C_i \le \text{剩余所有颜色数量之和} + 1\]

   或者等价于：

   \[C_i \le \lceil n / 2 \rceil\]

   但在首尾固定的情况下，限制会根据颜色 \(i\) 是否处于边界而变化。

3. 计算流程：

   • 统计所有石头的总数 \(n\)。
   • 将颜色 \(p\) 和 \(q\) 的计数各减 1。
   • 在剩余的石头中，找到数量最多的颜色 \(max\_color\)。
   • 恢复真实频次：将 \(max\_color\) 之前预留给首尾的数量加回去，得到该颜色在全序列中的总数 \(C_{max}\)。
   • 计算隔离物：计算除了 \(max\_color\) 以外，其他所有颜色的石头总数 \(rest\_sum\)。
   • 最终判定：如果 \(C_{max} > rest\_sum + 1\)，说明即使用掉所有的“隔离物”也无法完全分隔开最大频次的颜色，输出 0；否则输出 1。

伪代码

ALGORITHM Check-Stone-Arrangement
    INPUT: k, p, q, Array C[1...k]
    OUTPUT: 1 if possible, 0 otherwise

    // 1. Pre-process fixed positions
    C[p] ← C[p] - 1
    C[q] ← C[q] - 1

    // 2. Identify the most frequent color in remaining set
    max_idx ← 1
    FOR i ← 2 TO k DO
        IF C[i] > C[max_idx] THEN
            max_idx ← i
        END IF
    END FOR

    // 3. Restore its global total count
    max_count ← C[max_idx]
    IF max_idx == p THEN max_count ← max_count + 1
    IF max_idx == q THEN max_count ← max_count + 1

    // 4. Calculate the sum of all other colors
    total_others ← 0
    FOR i ← 1 TO k DO
        IF i != max_idx THEN
            // If i was p or q, their modified counts are included here
            total_others ← total_others + C[i]
        END IF
    END FOR

    // 5. Final validation based on separator logic
    IF max_count > total_others + 1 THEN
        RETURN 0
    ELSE
        RETURN 1
    END IF
END ALGORITHM

复杂度分析

• 时间复杂度: \(O(k)\)
  • 只需对长度为 \(k\) 的颜色数组进行常数次遍历（寻找最大值和求和）。
  • 使用了排序 \(O(k \log k)\)，但在该逻辑下 \(O(k)\) 遍历已足够。
• 空间复杂度: \(O(k)\)
  • 需要存储 \(k\) 种颜色的数量。

综上所述，该算法能在线性时间内准确判定给定的石头分布是否能构成合法的序列。

C - 物品出售

题目描述

有 $N $件物品，每件物品属于两种类型之一：

1. 类型 A（普通物品）： 只能直接出售，价值为 P。
2. 类型 B（可升级物品）： 有两个价格：
   • 不升级时可以直接出售，价值为 \(P_1\)；
   • 若先支付固定费用$ C $对其进行升级，再出售可以得到 \(P_2\)，且 \(P_2 > P_1\)。

整个过程中：

• 一开始你没有任何现金。最后所有物品都需要卖完。
• 你可以按任意顺序进行以下操作：
  • 出售一件尚未出售的物品（若为类型 B，可以选择“先升级再出售”或“不升级直接出售”）。
  • 只要当前现金\(\ge C\)，就可以为某件尚未升级的类型 B 物品支付 \(C\) 进行升级（升级操作本身不产生收入，收入体现在之后以 \(P_2\) 出售该物品）。

问：在最优操作顺序和升级选择下，你最终最多能得到多少现金？

输入

1. 第一行：两个整数$ N,C$ \((1 \le N \le 1000, 1 \le C \le 5000)\)，分别表示物品数量和每次升级的固定费用。

接下来 \(N\) 行，每行描述一个物品：

1. 若该行为一个整数 \(P\ (1 \le P \le 10000)\)，表示这是类型 A 物品，直接出售价值为 \(P\)；
2. 若该行为两个整数 \(P_1,\ P_2\ (1 \le P_1 < P_2 \le 10000)\)，表示这是类型 B 物品，不升级售价为 \(P_1\)，升级后售价为 \(P_2\)。

输出

输出一个整数，表示在最优策略下可以获得的最大总现金。

算法思路

1. 核心转化：
   • 对于类型 B 物品，升级后的净收益增量为 \(\Delta = P_2 - P_1 - C\)。
   • 若 \(\Delta \le 0\)，该物品无论何时都不应升级，视为基础价值为 \(P_1\) 的普通物品。
   • 若 \(\Delta > 0\)，该物品为“优质物品”。在理想状态（现金充足）下应全部升级，总收益为 \(\text{所有物品基础价值} + \sum \Delta_{\text{优质}}\)。
2. 启动资金约束：
   • 升级需要预付现金 \(C\)。初始现金为 0。
   • 我们首先卖出所有类型 A 和 \(\Delta \le 0\) 的类型 B 物品，积累初始资金 \(S_0\)。
   • 若 \(S_0 \ge C\)，直接升级所有优质物品，收益最大。
   • 若 \(S_0 < C\)，存在资金缺口 \(D = C - S_0\)。必须从优质物品中挑选一部分，不进行升级直接以 \(P_1\) 出售，用以填补缺口 \(D\)。
3. 背包模型优化：
   • 目标：从优质物品集合中选择一个子集“牺牲”（不升级），使得它们的 \(P_1\) 之和 \(\ge D\)，且这些物品的 \(\Delta\) 之和最小。
   • 状态定义：\(dp[s]\) 表示凑齐 \(s\) 元基础现金所损失的最小 \(\Delta\)。
   • 这是一个 0/1 背包问题。由于 \(s\) 超过 \(C\) 之后对开启第一笔升级没有额外贡献，可将所有 \(s > C\) 的状态统一截断处理。

Pseudo-code

ALGORITHM Maximize-Cash
    INPUT: N, C, Items (Type A: {P}, Type B: {P1, P2})
    OUTPUT: Max total cash
    base_total ← 0, S0 ← 0, total_profit ← 0
    GoodItems ← Empty List
    FOR each item DO
        IF item is Type A THEN
            base_total ← base_total + P, S0 ← S0 + P
        ELSE
            delta ← P2 - P1 - C
            base_total ← base_total + P1
            IF delta > 0 THEN
                Append {P1, delta} to GoodItems
                total_profit ← total_profit + delta
            ELSE
                S0 ← S0 + P1
            END IF
        END IF
    END FOR
    IF GoodItems is empty OR S0 >= C THEN
        RETURN base_total + total_profit
    END IF
    D ← C - S0
    dp[0...C] ← INFINITY
    dp[0] ← 0
    FOR {p1, delta} IN GoodItems DO
        FOR s FROM C DOWNTO 0 DO
            IF dp[s] == INFINITY CONTINUE
            next_s ← MIN(C, s + p1)
            dp[next_s] ← MIN(dp[next_s], dp[s] + delta)
        END FOR
    END FOR
    min_loss ← INFINITY
    FOR s FROM D TO C DO
        min_loss ← MIN(min_loss, dp[s])
    END FOR
    RETURN base_total + total_profit - min_loss
END ALGORITHM

复杂度分析

1. 时间复杂度: \(O(N \cdot C)\)
   • 预处理物品需 \(O(N)\)。
   • 0/1 背包过程有两层循环：物品数 \(N_{good} \le N\)，现金上限 \(C\)。总复杂度为 \(O(N \cdot C)\)。
   • 给定 \(N=1000, C=5000\)，总计算量约 \(5 \times 10^6\)，符合时限。
2. 空间复杂度: \(O(C)\)
   • 使用了一维滚动数组优化背包空间，大小为 \(O(C)\)。物品列表存储需 \(O(N)\)。

D - 环区间覆盖

题目

有一个由$ n $个点构成的环，这些点按顺时针依次编号为\(1,2,\dots,n\)。 现在给出\(k\)个“覆盖区间”，每个区间由一对整数 \((a,b)\) 表示，含义如下：

• 从点 \(a\) 出发，沿顺时针方向走，到达点 \(b\)为止（包含端点 \(a\) 和 \(b\)），经过的所有点都被这个区间覆盖；
• 若 \(b \ge a\)，则覆盖的是点 \(a,a+1,\dots,b\)；
• 若 \(b < a\)，则区间“跨过”编号\(n\) 又回到 1，即覆盖点$ a, a+1, , n, 1, 2, , b$

你可以任选若干个给定区间。 问：是否存在一种选择方式，使得环上所有点\(1\sim n\)都至少被一个选中的区间覆盖？ 如果存在，要求输出所需区间数量的最小值；否则输出 impossible。

输入

• 第一行两个整数 \(n,k\)
• 接下来$ k$ 行，每行两个整数 \(a,b\)表示一个区间。

输出

• 若无论如何选择都不能覆盖整个环，输出一行： impossible
• 否则输出一个整数，表示完成覆盖所需的最少区间数量

算法思路

1. 破环成链：环形结构难以直接处理，将其倍长展开为线性区间 \([1, 2n]\)。若原区间 \((a, b)\) 满足 \(a \le b\)，则生成线性区间 \([a, b]\) 和 \([a+n, b+n]\)；若 \(a > b\)，则生成 \([a, b+n]\)。
2. 贪心预处理：定义 \(f[i]\) 为以位置 \(i\) 或 \(i\) 之前的位置为起点所能达到的最远右端点。通过一次 \(O(N+K)\) 的扫描，利用前缀最大值确保 \(f[i]\) 随 \(i\) 单调递增，从而满足贪心策略：每次转移都选择能跳得最远的区间。
3. 倍增加速跳转：构建倍增跳转表 \(trans[j][i]\)，表示从位置 \(i\) 开始，经过 \(2^j\) 个区间后能达到的“首个未覆盖位置”（即最远右端点 \(+1\)）。
4. 起点枚举与覆盖验证：遍历所有给定区间的起点 \(s\)。若从 \(s\) 出发能够覆盖到 \(s+n\)，则说明完成了一次环形覆盖。利用倍增表在 \(O(\log n)\) 时间内找出覆盖长度 \(n\) 所需的最少区间数。

伪代码

ALGORITHM Min-Ring-Coverage
INPUT: n, k, Intervals[(a, b)]
OUTPUT: Min count or "impossible"
Initialize f[1..2n+1] where f[i] = i-1
FOR each (a, b) IN Intervals DO
    IF a <= b THEN
        f[a] ← MAX(f[a], b), f[a+n] ← MAX(f[a+n], b+n)
    ELSE
        f[a] ← MAX(f[a], b+n)
FOR i FROM 2 TO 2n DO f[i] ← MAX(f[i], f[i-1])
FOR i FROM 1 TO 2n+1 DO trans[0][i] ← MIN(2n+1, f[i] + 1)
FOR j FROM 1 TO log2(2n) DO
    FOR i FROM 1 TO 2n+1 DO
        trans[j][i] ← trans[j-1][trans[j-1][i]]
ans ← INF
FOR each starting point s IN original Intervals DO
    IF f[s] < s CONTINUE
    curr ← s, steps ← 0, target ← s + n
    FOR j FROM log2(2n) DOWNTO 0 DO
        IF trans[j][curr] < target AND trans[j][curr] > curr THEN
            curr ← trans[j][curr]
            steps ← steps + (1 << j)
    IF trans[0][curr] >= target THEN ans ← MIN(ans, steps + 1)
RETURN (ans == INF) ? "impossible" : ans

复杂度分析

• 时间复杂度：\(O((N+K)\log N)\)。
  • 预处理 \(f\) 数组耗时 \(O(N+K)\)。
  • 构建倍增表耗时 \(O(N \log N)\)。
  • 枚举起点并倍增查询耗时 \(O(K \log N)\)。
• 空间复杂度：\(O(N \log N)\)。
  • 主要消耗在于倍增跳转表 \(trans[j][i]\)，其空间规模为 \(O(2N \cdot \log 2N)\)。

4st Linear Programming

A - 资源调度优化

题目

在连续的 \(N\) 天内，每天需要消耗一定数量的资源。第 \(i\) 天的需求量为 \(r_i\)。为了满足这些需求，你可以通过以下三种方式获取“可用资源”：

1、直接购买： 每单位资源花费 \(p\) 元，购买后立即可以使用 2、快周期回收： 将使用过的旧资源送去快修，耗时 \(m\) 天，每单位费用 \(f\) 元。 3、慢周期回收： 将使用过的旧资源送去慢修，耗时 \(n\) 天，每单位费用 \(s\) 元。

补充规则：

• 每天使用完的旧资源可以暂时囤积，留到以后某天再送去回收。
• 已知回收参数满足：\(n > m\) 且 \(s < f\)（即用时间换取更低的成本）。

编程任务： 设计一个算法，计算在满足这 天所有资源需求的前提下，所需的最小总费用。

输入格式

• 第 1 行包含 6 个正整数：\(N, p, m, f, n, s\)

• \(N\)：计划的总天数 (\(N \le 2000\))。

• \(p\)：单单位新资源的价格

• \(m, f\)：快回收所需天数及单价。

• \(n, s\)：慢回收所需天数及单价

• 接下来的 \(N\) 行：每行一个正整数 \(r_i\)，代表第 \(i\) 天的资源需求量。

输出格式

• 输出一个整数，表示 \(N\) 天的最小总花费

算法逻辑概述

本实验采用 SSP (Successive Shortest Path) 算法求解最小费用最大流。该算法基于贪心策略，在残量网络中迭代寻找单位费用最小的增广路径，直至无法满足更多流量需求。

核心步骤

1. 图初始化：根据拆点法构建包含源点 \(S\)、汇点 \(T\) 及 \(2N\) 个中间节点的流网络。
2. 最短路搜索：在残量网络中运行 SPFA (Shortest Path Faster Algorithm)。由于图中存在反向边导致的负费用（用于反悔机制），Dijkstra 算法不直接适用，SPFA 能有效处理此类负权边（无负环）。
3. 流量增广与反悔：
   • 计算当前最短路径上的瓶颈容量 \(flow\)。
   • 累加费用：\(\text{TotalCost} += flow \times \text{distance}[T]\)。
   • 更新残量网络：正向边容量减少 \(flow\)，反向边容量增加 \(flow\)。反向边的存在使得算法具备反悔能力，即后续决策可退回原本分配给某路径的流，将其重新分配以获得全局最优。

算法设计伪代码

Algorithm: Minimum Cost Maximum Flow (SSP using SPFA)
Input: Source $S$, Sink $T$, Graph $G(V, E)$
Output: Minimum Total Cost
Function MinCostMaxFlow(S, T):
    Initialize min_cost = 0
    
    // Loop until no augmenting path exists from S to T
    // 循环直到残量网络中源点与汇点不连通
    While True:
        
        // Step 1: Find the shortest path based on edge costs using SPFA
        // 使用 SPFA 算法寻找单位费用最小的路径
        Initialize dist[] = INFINITY
        dist[S] = 0
        Queue Q.push(S)
        
        While Q is not empty:
            u = Q.pop()
            For each edge e(u, v) in Graph:
                // Relaxation: check if a cheaper path exists with available capacity
                // 松弛操作：若边有剩余容量且存在更低费用的路径
                If e.capacity > 0 AND dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    Record predecessor(v) = u, pre_edge(v) = e
                    If v is not in Q:
                        Q.push(v)
        
        // If Sink T is unreachable, the algorithm terminates
        // 若汇点不可达，说明已达到最大流或需求已满足
        If dist[T] == INFINITY:
            Break
            
        // Step 2: Calculate bottleneck capacity along the path
        // 回溯路径，计算瓶颈流量
        flow = INFINITY
        curr = T
        While curr != S:
            edge = pre_edge(curr)
            flow = min(flow, edge.capacity)
            curr = predecessor(curr)
            
        // Step 3: Update residual graph and accumulate cost
        // 更新残量网络（正向减，反向加）及总费用
        min_cost += flow * dist[T]
        curr = T
        While curr != S:
            edge = pre_edge(curr)
            edge.capacity -= flow
            // Update reverse edge capacity for potential flow redirection
            // 增加反向边容量以支持反悔机制
            reverse_edge(edge).capacity += flow
            curr = predecessor(curr)
            
    Return min_cost

复杂度分析

空间复杂度

1. 节点规模：\(V = 2N + 2\)（源点、汇点、\(N\) 个供应点、\(N\) 个需求点）。
2. 边规模：每种策略对应一组边。购买、快洗、慢洗、囤积、源汇连接各需 \(N\) 条边。考虑到反向边，总边数 \(E \approx 12N\)。
3. 结论：采用邻接表存储，空间复杂度为 \(O(V+E) = O(N)\)。对于 \(N=2000\)，内存占用极低。

时间复杂度

SSP 算法的时间复杂度公式为 \(O(k \cdot C_{SPFA})\)，其中 \(k\) 为增广次数。

1. 增广次数 \(k\)： 算法的主要约束在于填满 \(N\) 条从需求点到汇点的边（容量为 \(r_i\)）。在大多数实际算例中，增广路径的查找次数与天数 \(N\) 呈线性相关，即 \(k \approx O(N)\)。

2. 单次 SPFA 复杂度： SPFA 的平均时间复杂度为 \(O(E)\)。在本题构建的分层图（Layered Graph）结构中，不存在复杂的环路，SPFA 效率接近最优。

3. 综合复杂度：

   \[ T \approx O(N \times E) = O(N \times 12N) = O(N^2) \]

4. 数值验证： 当 \(N = 2000\) 时，\(N^2 = 4 \times 10^6\)。现代 C++ 编译程序的执行速度约为 \(10^8\) 指令/秒，因此理论运行时间在毫秒级别，完全满足时限要求。

B - 人员雇佣计划

题目

一项工程共需 n 天完成，其中第 i 天至少需要 ai 人在岗。 现有 m 种雇佣方式，第 j 种方式可以雇佣一名从第 sj 天工作到第 tj 天的员工，雇佣单价为 cj 元。 请问在满足每一天人数需求的前提下，最少需要支付多少费用？

输入格式

第一行包含两个整数 n, m，表示总天数和雇佣方式的种类。 第二行包含 n 个非负整数，表示每天至少需要的人数 ai。 接下来的 m 行，每行包含三个整数 sj, tj, cj，表示该种方式的工作起始时间、结束时间和单人费用。

输出格式

仅包含一个整数，表示完成工程所需的最低总费用。

思路：最小费用最大流模型

为了解决区间覆盖与成本最小化的问题，我们需要将问题转化为最小费用最大流 (Minimum Cost Maximum Flow, MCMF) 模型。利用流量守恒定律来模拟人员的在岗状态。

建模核心：差分约束建图 我们不直接对每天的需求 \(a_i\) 连边，而是利用差分数组 \(D_i = a_i - a_{i-1}\) 来表示人员的变化量。

1. 节点定义：建立源点 \(S\)、汇点 \(T\) 以及代表时刻的节点 \(1, 2, \dots, N+1\)。
2. 供需平衡 (Supply & Demand)：
   • 若 \(D_i > 0\)（需求增加）：表示第 \(i\) 天比前一天多需要 \(D_i\) 人。从 \(S\) 向 \(i\) 连边，容量 \(D_i\)，费用 0。
   • 若 \(D_i < 0\)（需求减少）：表示第 \(i\) 天比前一天可以释放 \(|D_i|\) 人。从 \(i\) 向 \(T\) 连边，容量 \(|D_i|\)，费用 0。
3. 雇佣操作 (Hiring)：
   • 每种方案 \((s, t, c)\) 代表一个人从第 \(s\) 天工作到第 \(t\) 天（第 \(t+1\) 天离开）。
   • 从节点 \(s\) 向 \(t+1\) 连边，容量 \(\infty\)，费用 \(c\)。
4. 辅助边 (Carry-over)：
   • 为了允许“人手过剩”（即某天的人数超过 \(a_i\)），我们需要允许流量“流过”需求点而不立即去汇点。
   • 从节点 \(i+1\) 向 \(i\) 连边，容量 \(\infty\)，费用 0。这代表第 \(i+1\) 天多余的人手可以填补第 \(i\) 天的差分需求（在数学上等价于利用长区间覆盖短区间）。

通过求解从 \(S\) 到 \(T\) 的最小费用最大流，即可得到满足所有需求前提下的最小总花费。

伪代码

Algorithm: Min-Cost Max-Flow (SSP with SPFA+SLF)
Input: Days N, Schemes M, Requirements a1 ... aN
Output: Minimum Cost*
Function Solve():
    Calculate difference array D[i] = a[i] - a[i-1]
    
    // Build Graph
    For i from 1 to N+1:
        If D[i] > 0:
            AddEdge(Source, i, capacity=D[i], cost=0)
        If D[i] < 0:
            AddEdge(i, Sink, capacity=-D[i], cost=0)
        If i > 1:
            AddEdge(i, i-1, capacity=INFINITY, cost=0) // Aux edge for flow carry-over
            
    For each Scheme (s, t, cost):
        AddEdge(s, t+1, capacity=INFINITY, cost=cost)

    // Main Loop
    While SPFA_with_SLF(Source, Sink) finds a path:
        Calculate bottleneck flow f along the path
        min_cost += f * dist[Sink]
        
        Update residual graph:
            For each edge in path:
                edge.capacity -= f
                reverse_edge.capacity += f
                
    Return min_cost

算法复杂度分析

本实验采用了基于 SPFA (Shortest Path Faster Algorithm) 的 SSP (Successive Shortest Path) 算法，并配合 SLF (Small Label First) 优化和 静态数组（链式前向星） 存图。

时间复杂度

SSP 算法的总复杂度公式为：\(T \approx O(K \cdot C_{SPFA})\)

其中 \(K\) 为最大流量（增广次数），\(C_{SPFA}\) 为单次寻找增广路的时间。

1. 增广次数 \(K\)： 在本题模型中，流量由源点流出，源点连边的总容量为 \(\sum_{D_i > 0} D_i\)。虽然题目未给出具体流量上限，但增广次数受限于总需求人数的变化量，通常在可控范围内。
2. 单次 SPFA 复杂度： SPFA 的平均复杂度为 \(O(kE)\)，其中 \(E\) 为边数，\(k\) 为常数（通常 \(k \approx 2\)）。
   • SLF 优化：针对本题特殊的“长链+回边”结构，SLF 优化（当新节点距离小于队首时插到队头）能极大地减少节点重复入队的次数。
   • 实际表现：在 \(N=1000, M=10000\) 的规模下，优化后的 SPFA 接近线性查找。

综合复杂度：\(T \approx O(\text{TotalFlow} \times (N+M))\)

空间复杂度

使用静态数组（链式前向星）存图：\(S = O(N + M)\)

1. 节点数：\(N \approx 1000\)。
2. 边数：\(2 \times (N + M)\)（正反向边）。

C - 最少操作数列

题目

定义初始数列为每个数字都为 0 的数列。 定义一次操作为将数列的一个区间中每一个数的值增加 1，规定该区间的长度不能超过 m。 给定一个长度为 n 的数列 a，第 i 个数为 ai。 你需要回答 q 次询问。每次询问给定 l, r，你需要回答将一个长度为 r − l + 1 的初始数列变为 a 中的 [l, r]（即数列 al, al + 1, ⋯, ar）至少需要多少次操作。

输入格式

第一行三个整数 n, m, q。 第二行 n 个整数，第 i 个为 ai。 接下来 q 行，每行两个整数，表示 l, r。

对于 100% 的数据，保证 1 ≤ m ≤ n ≤ 105，1 ≤ q ≤ 105，0 ≤ ai ≤ 109，1 ≤ l ≤ r ≤ n。

输出格式

q 行，每行一个整数，表示至少需要的操作次数。

https://www.luogu.com.cn/problem/solution/P7908

D - 最大和乘积

题目描述

共有 n 个元素，标号 1 ∼ n，每个元素 j 有两个正整数权值 aj, bj。 你要确定一个 [1, n] ∩ ℕ 的子集 S，从而最大化

\[ \left(\sum_{k=1}^na_k[k\in S]\right)\left(\sum_{k=1}^nb_k[k\notin S]\right) \]

这个问题显然不可做，因此保证每个 aj, bj 分别在 [1, A] ∩ ℕ, [1, B] ∩ ℕ 内独立均匀随机生成。 现在给定 n, A, B 和每个元素的两个权值 (aj, bj)，请求出这个最大的答案。

输入格式

本题每个测试点中有多组测试数据。 第一行四个整数，T, n, A, B，T 表示该组数据内的数据组数，n, A, B 表示该测试点内的所有数据均对应此 n, A, B。 接下来每组数据占 n 行，其中第 j 行两个整数 aj, bj。

保证 aj, bj 在对应范围内独立均匀随机生成。 对于所有的数据，保证 10 ≤ n ≤ 3000，10^{4 ≤ A, B ≤ 10}12，1 ≤ T ≤ 50。

算法思路

1. 比例排序（Ratio Sorting）：为了最大化和的乘积，核心思想是优先将“\(a\) 权值相对 \(b\) 权值更高”的元素放入集合 \(S\)。因此，首先根据 \(\frac{a_j}{b_j}\) 的比值对所有元素进行降序排序。
2. 随机性利用（Randomness Exploitation）：题目保证权值是独立均匀随机生成的。在这种分布下，最优解对应的集合 \(S\) 极大概率是排序后序列的一个前缀，或者与某个前缀非常接近。
3. 局部搜索/剪枝搜索（Local Search/DFS）：
   • 预处理排序后的前缀和 \(preA\)（\(a\) 的累加）和后缀和 \(sufB\)（\(b\) 的累加）。
   • 枚举可能的“分割点” \(i\)。在分割点附近的一小段区间内进行深度优先搜索（DFS），允许少量元素偏离“前缀必选”的规则。
   • 搜索过程中，对于区间外的元素，直接通过预处理的汇总值计算贡献，从而在极小的搜索空间内找到全局最优值。

伪代码

ALGORITHM Max-Sum-Product
    INPUT: T, n, A, B, Weights[(a_1, b_1), ..., (a_n, b_n)]
    OUTPUT: Maximum product of (sum of a in S) * (sum of b not in S)
    FOR each test case DO
        FOR j FROM 1 TO n DO Items[j].ratio ← a_j / b_j
        SORT Items in descending order of ratio
        preA[0] ← 0, sufB[n + 1] ← 0
        FOR j FROM 1 TO n DO preA[j] ← preA[j-1] + Items[j].a
        FOR j FROM n DOWNTO 1 DO sufB[j] ← sufB[j+1] + Items[j].b
        ans ← 0
        mid ← n / 2
        FOR i FROM MAX(1, mid - 100) TO MIN(n, mid + 100) DO
            L ← MAX(1, i - 6), R ← MIN(n, i + 6)
            DFS(L, R, preA[L-1], sufB[R+1])
        END FOR
        PRINT ans
    END FOR
    FUNCTION DFS(idx, end, curA, curB)
        IF idx > end THEN
            ans ← MAX(ans, curA * curB)
            RETURN
        DFS(idx + 1, end, curA + Items[idx].a, curB)
        DFS(idx + 1, end, curA, curB + Items[idx].b)
    END FUNCTION
END ALGORITHM

复杂度分析

1. 时间复杂度 (Time Complexity): \(O(T \cdot (n \log n + \Delta \cdot 2^{2 \cdot \text{TEMP}}))\)
   • 排序：每组数据 \(O(n \log n)\)。
   • 搜索：枚举 \(\Delta\)（代码中为 \(DELTA\)）个位置，每个位置进行深度为 \(2 \times TEMP\) 的 DFS。由于 \(TEMP\) 是常数（如 7），该部分复杂度在随机数据下表现极佳。
   • 对于 \(n=3000\)，\(T=50\)，总计算量在时限内绰绰有余。
2. 空间复杂度 (Space Complexity): \(O(n)\)
   • 需要存储 \(n\) 个元素的权值、比例以及前缀/后缀和数组。

这项算法通过利用数据随机性，将原本指数级的子集搜索问题，降维到了有序序列附近的局部搜索问题。

Test

分而治之

找中位数：快速选择算法 (Quick Select)

算法思路：

基于快速排序 (Quick Sort) 的 Partition思想。随机选择一个基准值 (Pivot)，将数组分为两部分：左边小于 Pivot，右边大于 Pivot。判断 Pivot 的最终位置索引与目标中位数索引 \(k\) 的关系：若相等则找到；若 \(k\) 小于 Pivot 索引，则在左半区继续找；否则在右半区找。平均情况不需要排序整个数组。

伪代码：

FUNCTION FindMedian(A, n)
    INPUT: Array A of size n
    OUTPUT: The median value
    k <- FLOOR(n / 2) // 中位数的目标索引
    left <- 0
    right <- n - 1
    WHILE left <= right DO
        pivotIndex <- Partition(A, left, right) // 将A划分为两部分并返回基准下标
        IF pivotIndex == k THEN
            RETURN A[k]
        ELSE IF pivotIndex < k THEN
            left <- pivotIndex + 1 // 在右半边查找
        ELSE
            right <- pivotIndex - 1 // 在左半边查找
        ENDIF
    ENDWHILE
ENDFUNCTION

复杂度分析：

• 时间复杂度：平均 \(O(N)\)，最坏 \(O(N^2)\) (发生于每次 Partition 极度不平衡时，可用 Randomized Partition 优化)。
• 空间复杂度：\(O(1)\) (迭代写法) 或 \(O(\log N)\) (递归栈)。

找众数：摩尔投票算法 (Boyer-Moore Voting)

2. 排序遍历法 (Sorting)

算法思路：

首先将数组排序。排序后，相同的元素会连续排列。只需遍历一次排序后的数组，统计当前连续元素的长度。如果当前连续长度超过了历史最大长度，则更新结果。该方法牺牲了时间以换取空间效率。

伪代码：

FUNCTION FindModeSorting(A, n)
    INPUT: Array A of size n
    OUTPUT: The mode value
    Sort A in ascending order
    mode <- A[0]
    maxCount <- 1
    currentCount <- 1
    FOR i FROM 1 TO n - 1 DO
        IF A[i] == A[i-1] THEN
            currentCount <- currentCount + 1
        ELSE
            currentCount <- 1
        ENDIF
        IF currentCount > maxCount THEN
            maxCount <- currentCount
            mode <- A[i]
        ENDIF
    ENDFOR
    RETURN mode
ENDFUNCTION

复杂度分析：

• 时间复杂度：\(O(N \log N)\)，主要消耗在排序操作上（如快排或归并排序）。
• 空间复杂度：\(O(1)\) 或 \(O(\log N)\)，取决于排序算法是否为原地排序 (In-place) 以及递归栈的深度。

动态规划

字符串A和字符串B，每次可以删除一个字符，问最少的删除次数，能够使得这两个字符串相等。

算法思路

该问题本质上是求解两个字符串的最长公共子序列 (LCS) 的变种。使得两个字符串相等的最小删除次数，等于两个字符串的总长度减去它们最长公共子序列长度的两倍。

或者直接定义 \(dp[i][j]\) 为使字符串 \(A\) 的前 \(i\) 个字符和 \(B\) 的前 \(j\) 个字符相等所需的最小删除次数：

1. 初始化：如果一个字符串为空，另一个字符串必须全部删除。即 \(dp[i][0] = i\)，\(dp[0][j] = j\)。
2. 状态转移：
   • 若 \(A[i] == B[j]\)，不需要删除，继承之前的状态：\(dp[i][j] = dp[i-1][j-1]\)。
   • 若 \(A[i] \neq B[j]\)，则需要删除 \(A[i]\) 或 \(B[j]\)，取最小值并加1：\(dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1])\)。

伪代码

FUNCTION MinDeletions(A, B)
    INPUT: String A (length m), String B (length n)
    OUTPUT: Integer min_ops

    DECLARE dp[0...m][0...n] AS INTEGER
    
    FOR i FROM 0 TO m DO
        dp[i][0] <- i    // B为空，需删除A的所有字符
    ENDFOR
    FOR j FROM 0 TO n DO
        dp[0][j] <- j    // A为空，需删除B的所有字符
    ENDFOR

    FOR i FROM 1 TO m DO
        FOR j FROM 1 TO n DO
            IF A[i] == B[j] THEN
                dp[i][j] <- dp[i-1][j-1]    // 字符匹配，无额外删除
            ELSE
                dp[i][j] <- 1 + MIN(dp[i-1][j], dp[i][j-1])    // 删除A[i]或B[j]
            ENDIF
        ENDFOR
    ENDFOR

    RETURN dp[m][n]
ENDFUNCTION

复杂度分析

1. 时间复杂度：\(O(m \times n)\)

   需要填充一个 \(m \times n\) 的二维数组，每个单元格的计算仅涉及常数次比较和加法操作。

2. 空间复杂度：\(O(m \times n)\)

   需要存储 \(dp\) 表。注：通过使用滚动数组优化，空间复杂度可降低至 \(O(\min(m, n))\)。

线性规划：搬家问题

卡车每次容量为Q，共m个箱子和n个物品都要搬走，每个箱子和每个物品都有容量，物品要放到箱子里，一个箱子可以放多件物品。最小化卡车搬运趟数。

算法思路

基于贪心策略 (First Fit Decreasing) 分两步解决：

1. 物品入箱：将物品和箱子均按容量降序排序，优先把大物品放入能容纳它的最大箱子，若无法放入则无解。
2. 箱子装车：统计已使用的箱子（视作刚性物体，体积为其容量），按容量降序排序。遍历箱子，优先放入当前已开启且剩余空间足够的卡车趟次，若放不下则开启新一趟。

伪代码

Plaintext

FUNCTION MinTruckTrips(items, boxes, Q)
    INPUT: Array items (size n), Array boxes (size m), Integer Q
    OUTPUT: Integer count

    Sort items descending; Sort boxes descending
    box_current_load[0...m-1] <- 0
    
    // Stage 1: Put items into boxes
    FOREACH item IN items DO
        placed <- FALSE
        FOR i FROM 0 TO m-1 DO
            IF box_current_load[i] + item <= boxes[i] THEN
                box_current_load[i] <- box_current_load[i] + item
                placed <- TRUE; BREAK
            ENDIF
        ENDFOR
        IF NOT placed THEN RETURN "Impossible"
    ENDFOREACH

    // Stage 2: Put used boxes into truck
    // Collect capacity of boxes that are not empty
    used_boxes <- [boxes[i] FOR i FROM 0 TO m-1 WHERE box_current_load[i] > 0]
    Sort used_boxes descending
    
    trips_remaining_space <- [] // List storing remaining space of each trip
    
    FOREACH box_cap IN used_boxes DO
        IF box_cap > Q THEN RETURN "Impossible"
        fit_in_trip <- FALSE
        FOR k FROM 0 TO length(trips_remaining_space) - 1 DO
            IF trips_remaining_space[k] >= box_cap THEN
                trips_remaining_space[k] <- trips_remaining_space[k] - box_cap
                fit_in_trip <- TRUE; BREAK
            ENDIF
        ENDFOR
        IF NOT fit_in_trip THEN 
            APPEND (Q - box_cap) TO trips_remaining_space
        ENDIF
    ENDFOREACH

    RETURN length(trips_remaining_space)
ENDFUNCTION

复杂度分析

1. 时间复杂度：\(O(N \cdot M + M^2)\)。第一阶段最坏需遍历所有箱子尝试放入物品 (\(N \times M\))；第二阶段最坏需比较所有已开启的趟次 (\(M^2\))。排序开销为 \(O(N \log N + M \log M)\)。
2. 空间复杂度：\(O(M)\)。用于存储箱子负载状态和卡车每趟的剩余空间。