第一次作业解题报告

答案已在课程网站全部 AC，本人课程网站 ID along4llm

AI 协作题 (1): 区间最大值不小于和

题目分析

题目要求判断数组中所有子区间 $[i, j]$ 是否满足 $max (a_{i} \dots a_{j}) \geq \sum_{k = i}^{j} a_{k}$ 。如果存在任意一个子区间使得“区间和 > 区间最大值”，则输出 NO，否则输出 YES。

解题思路

暴力枚举所有子区间的时间复杂度为 $O (N^{2})$ ，对于 $N = 2 \cdot 1 0^{5}$ 的数据规模会超时。我们需要一个 $O (N)$ 或 $O (N lo g N)$ 的解法。

核心观察：如果条件不满足，必然存在某个元素 $a_{k}$ 作为最大值的某个区间，其区间和超过了 $a_{k}$ 。因此，我们只需要对数组中的每一个元素 $a_{i}$ ，找到它是最大值的“最大可能区间” $[L_{i}, R_{i}]$ （即左边第一个比它大的数之后，到右边第一个比它大的数之前）。（因为所有输入都是正整数）

可以用单调栈在 $O (n)$ 的时间获得区间坐标，因为每个元素只需要进栈出栈一次
利用前缀和在 $O (n)$ 的时间获得区间和

如果在这个范围内，存在包含 $a_{i}$ 的子区间使得和大于 $a_{i}$ ，则条件被破坏。实际上，在本题逻辑下，我们可以通过检查每一个元素 $a_{i}$ 对应的最大可能区间 $[L_{i}, R_{i}]$ 的总和是否 $> a_{i}$ 来快速判断。

该代码是 Gemini 3.0 协助生成的，但是 GPT 5.1 一直觉得算法存在漏洞要求我添加线段树（但毕竟通过了全部 AC）

并且 GPT 5.1 使用具体案例向我说明了代码实现的漏洞，对于 [3,3,-3] 来说区间 [0,1] 是坏区间。但是 Gemini 生成的代码也确实输出的 YES，但是洛谷也确实全部通过了 AC

求 left_bound, right_bound 和 prefix_sum
 
我直接给出结果：
 
a = [3, 3, -3]
left_bound  = [-1, -1,  1]
right_bound = [ 3,  3,  3]   # n = 3
prefix_sum  = [0, 3, 6, 3]
 
 
对每个 i 算 [l,r] 和 current_sum：
 
i = 0：
 
l = left_bound[0] + 1 = 0
 
r = right_bound[0] - 1 = 2
 
区间 [0,2] 的和：prefix_sum[3] - prefix_sum[0] = 3
 
3 > a 吗？否。
 
i = 1：
 
l = 0, r = 2，区间和一样是 3 ≤ a。
 
i = 2：
 
l = 2, r = 2，区间和 = -3 ≤ a2
。
 
所以整个循环中都没有 current_sum > a[i]，
程序会输出 "YES" —— 但题目真实答案是 "NO"。
 
原因：
 
它只检查了以某个元素为“峰值”的最大区间 [l,r]。
 
但坏的区间 [0,1] 是 [0,2] 的一个子区间：
 
整体 [0,2] 的和是 3，不超；
 
子区间 [0,1] 的和却是 6，已经炸了。
 
所以这个实现没检查到所有可能的坏区间，逻辑上是不够的。

仔细看了题目要求后反应过来了，题目的输入中规定了全为正整数，所以不需要线段树来对付有负数的情况。最终实现 $O (N)$ 的复杂度。（样式案例给了大模型一些误导，让 GPT 5 没有意识到输入全为正整数）。GPT 好的一点是能够

代码实现

import sys
 
# 增加递归深度，防止深层递归挂掉（虽然本题主要用迭代）
sys.setrecursionlimit(200000)
 
def solve():
    # 读取所有输入
    input = sys.stdin.read
    data = input().split()
    iterator = iter(data)
    
    try:
    	# 读取总案例数
        num_test_cases = int(next(iterator))
    except StopIteration:
        return
 
    results = []
    
    for _ in range(num_test_cases):
    	# 每个案例的长度
        n = int(next(iterator))
        a = []
        for _ in range(n):
            a.append(int(next(iterator)))
            
        # 1. 预处理前缀和
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i+1] = prefix_sum[i] + a[i]
            
        # 2. 利用单调栈找左右边界
        # left_bound[i] 表示 a[i] 左边第一个 > a[i] 的位置
        # right_bound[i] 表示 a[i] 右边第一个 > a[i] 的位置
        left_bound = [-1] * n
        right_bound = [n] * n
        
        stack = []
        for i in range(n):
            while stack and a[stack[-1]] <= a[i]:
                stack.pop()
            if stack:
                left_bound[i] = stack[-1]
            stack.append(i)
            
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and a[stack[-1]] <= a[i]:
                stack.pop()
            if stack:
                right_bound[i] = stack[-1]
            stack.append(i)
            
        # 3. 检查逻辑
        possible = True
        for i in range(n):
            # 区间是 (left_bound[i], right_bound[i]) -> [left_bound[i]+1, right_bound[i]-1]
            l = left_bound[i] + 1
            r = right_bound[i] - 1
            
            # 计算该区间和
            current_sum = prefix_sum[r+1] - prefix_sum[l]
            
            if current_sum > a[i]:
                possible = False
                break
        
        if possible:
            results.append("YES")
        else:
            results.append("NO")
            
    print('\n'.join(results))
 
if __name__ == "__main__":
    solve()

复杂度

前缀和，单调栈以及最后的遍历都只需要 $O (n)$ 的时间复杂度，不存在递归等逻辑，用到的空间也是 $O (n)$

时间，空间都是复杂度 $O (n)$

可以通过全部测试

AI 协作题 (2): 稠密有向无环图的构造

题目分析

目标是构造一个有 $n$ 个顶点的 DAG，使得距离为 2 的点对数量 $k \geq \frac{n ( n - 1 )}{2} - n ⌈ lo g_{2} n ⌉$ 。这意味着“非距离为 2”的点对数量非常少（不超过 $O (n lo g n)$ ）。

同时 GPT 5 对题目的展开分析也很不错下面我从 0 到 1、完整复现“怎么想到”这种构造的理论思路。这是很多竞赛选手第一次看到都会一脸懵的问题，我给你拆得非常细，保证懂。

1. 我们到底想要什么？

题目要求：构造一个 DAG，使得：

$(u, v) : d i s t (u, v) = 2 \geq \frac{n ( n - 1 )}{2} - n ⌈ lo g_{2} n ⌉$

也就是说——我们想让尽可能多的点对之间的距离等于 2。

目标：让大量点对之间存在 2 跳路径 $u \to x \to v$ 。

注意：如果 u 和 v 之间有直接边 u→v，那么距离是 1，这样我们就失去了一个距离 = 2 的点对。

因此问题变成：

2. “我想要距离=2，但不想要距离=1”

也就是说我们要：

**产生很多三角结构 $u \to mi d \to v * *$
但 不能有直接边 $u \to v$ 。

于是一个成功的构造必须：

有一个“中间点”承担很多 pair
中间点连接两侧大量点
但不能使这些点彼此相邻

这强烈暗示：

3. 把点集分成左右两半，中间点连接整个两半

想象我们把 [1..n] 区间：

左半 S   中点 mid   右半 T

如果：

S 中所有点 $\to mi d$
$mi d \to T$ 中所有点

则任意 $u \in S, v \in T$ 都有：

$u \to mi d \to v$

于是我们立即获得：

$∣ S ∣ \cdot ∣ T ∣ 对距离 = 2 的点对$

而且如果我们保证图中所有边是从小编号指向大编号就没有环，这是一个天然的 DAG。

现在我们获得了大量距离=2点对！

4. 如何让每一层都这么做？用“分治”！

刚才我们把 [1..n] 分成了：

左 [1..mid−1]
中点 mid
右 [mid+1..n]

这个操作只保证了跨越中点的 (左→右) 点对有距离 2。

但是左右两边内部的点对怎么办？

答案是 —— 继续递归。

例如左边 [1..mid−1] 再次做同样的操作：

左左 —— 中左 —— 右左

右边 [mid+1..n] 继续做：

左右 —— 中右 —— 右右

这样每一层都会再贡献大量的距离=2点对。

5. 这个构造为什么边数不爆炸？

每一次“选中点 mid 并把它左右全连”时：

左边大小约为 k/2
右边大小约为 k/2
加的边大约是 k−1 条

递归深度是： $⌈ lo g_{2} n ⌉$

所以每个点，最多被连：

向右连 log n 次
或向左连 log n 次

因此：

$总边数 \leq n \cdot ⌈ lo g_{2} n ⌉$

这完全满足题目要求 ( $m \leq n (n - 1) /2$ )。

6. 距离 = 2 的点对数量为什么够大？

每一层都把某个区间拆成：

左  — mid — 右

并产生：

$∣ 左 ∣ \cdot ∣ 右 ∣$

个 “跨越 mid” 的距离=2点对。

而把所有层累积起来，总共产生点对数量：

$\frac{n ( n - 1 )}{2} - n ⌈ lo g_{2} n ⌉$

也就是说损失的点对只有每层 n 个（因为每层只对每个点产生 1 个“不可跨越”限制），而层数是 log n，因此损失是 ( $n lo g n$ )，其余全部都保持距离 2。

7. 换句话说，这个构造在做什么？

它在构造一个 完全有向图，但是：

不允许任何直接边 $u \to v$ （因为会变成距离 1）
所以必须由第三点“弯一下”
但如果所有点都有第三点，就需要一个超级中心，但是 DAG 不能有“入所有边并出所有边”的中心
于是我们像 二叉树 一样，把“中心任务”分散到 log n 层

从而：

每一层负责一部分点对的距离 = 2
累积 log n 层就覆盖了几乎全体点对

这就是分治大法的核心思想。

8. 构造的本质数学结构

我们其实构造了一个 顶点在分治树中的 LCA：

点 u 和 v 的最小公共区间节点 mid 正好是它们距离 = 2 的中转点。

因此：

$d i s t (u, v) = 2 ⟺ L C A (u, v) 是该层的 mid$

这也是为什么整个图无环、边数小，并且距离结构清晰。

9. 总结（完全理解后你应该能复述）

想要大量距离 = 2，必须让大量点对有共同中转。
但 DAG 不允许所有点共享同一个中转（会形成环）。
于是把点序列按二分不断切开，每一层选择一个 mid 点作为“中转”。
该 mid 连接它左右的点，贡献大量距离=2点对。
递归继续产生下一层贡献。
最终损失的点对数量只是每层 n，总共 n log n。
达成题目要求。

构造策略

利用 分治（递归） 思想。

将节点集合分为左集合 $L$ 、中间节点 $mi d$ 、右集合 $R$ 。
让 $L$ 中所有点指向 $mi d$ 。
让 $mi d$ 指向 $R$ 中所有点。

这样，任何 $u \in L, v \in R$ 的路径都是 $u \to mi d \to v$ ，距离正好为 2。递归处理 $L$ 和 $R$ 内部的连边。

代码实现 (Python)

import sys
 
# 增加递归深度
sys.setrecursionlimit(5000)
 
def solve():
    try:
        line = sys.stdin.read().split()
        if not line: return
        n = int(line[0])
    except ValueError:
        return
 
    edges = []
 
    def build(nodes):
        if not nodes:
            return
        
        # 取中间节点
        mid_idx = len(nodes) // 2
        mid_node = nodes[mid_idx]
        
        left_part = nodes[:mid_idx]
        right_part = nodes[mid_idx+1:]
        
        # 左边所有点 -> 中间点
        for u in left_part:
            edges.append((u, mid_node))
            
        # 中间点 -> 右边所有点
        for v in right_part:
            edges.append((mid_node, v))
            
        # 递归处理
        build(left_part)
        build(right_part)
 
    # 生成 1 到 n 的列表
    all_nodes = list(range(1, n + 1))
    build(all_nodes)
 
    print(len(edges))
    for u, v in edges:
        print(f"{u} {v}")
 
if __name__ == "__main__":
    solve()

时间递推式可以写成：

$T (k) = 2 T (k /2) + C k (C 为常数)$

这是典型的 Master 定理形式：

$(a = 2), (b = 2), (f (k) = C k)$
比较 $(k^{l o g_{b} a} = k^{l o g_{2} 2} = k^{1} = k)$

属于 第二种情况： $(f (k) = Θ (k^{l o g_{b} a}))$

所以：

$T (k) = Θ (k lo g k)$

时间复杂度是 O (n log n)

再加上最后输出所有边 print(len(edges)) 和循环输出每条边，也是 O(m)，而 m 本身就是 O (n log n) 级别（下面第 4 点会讲），

所以 总时间复杂度仍是 O (n log n)。

4. 边的数量 m 的规模（顺便一并分析一下）

在一次对长度为 k 的 nodes 的调用中：

left_part = nodes[:mid_idx]          # 长度 L
right_part = nodes[mid_idx+1:]       # 长度 R
# 有 L + R = k - 1
 
for u in left_part: edges.append(...)
for v in right_part: edges.append(...)

这一层新加的边数 = len(left_part) + len(right_part) = k - 1。

记 E(k) 是长度为 k 的子问题产生的总边数，则有：

$E (k) = E (k_{left}) + E (k_{right}) + (k - 1)$

其中 $(k_{left} + k_{right} = k - 1)$ 。

这和前面的时间递推形式本质上一样，所以解出来也是：

$E (k) = Θ (k lo g k)$

特别地，当 k = n 时：

👉 边的总数 m = len(edges) 是 O (n log n) 级别的。

这也解释了为什么前面说输出 m 条边的时间复杂度也是 O (n log n)。

5. 空间复杂度分析

空间主要来自三部分：

all_nodes = list(range(1, n+1))
- 占 O(n) 空间
edges 存所有边
- 条数 m = O (n log n)，因此 edges 占 O (n log n) 空间
递归调用栈
- 递归深度 ≈ log₂ n（每次长度差不多除 2）
- 每一层局部变量常数级 → 调用栈占 O (log n) 空间

切片 nodes[:mid_idx] 和 nodes[mid_idx+1:] 会不断分配新列表，但旧的子列表在递归返回后会被回收，整体“峰值”仍然被 edges 主导。

所以总空间复杂度：

👉 空间复杂度为 O (n log n)（由 edges 主导）

6. 总结一句话版本

递归部分的时间：

$T (n) = 2 T (n /2) + O (n) \Rightarrow T (n) = O (n lo g n)$

总边数 m = O (n log n)，输出也要 O (n log n) 时间
所以 总时间复杂度：O (n log n)
边数组 edges 里存了 O (n log n) 条边
再加上节点数组和递归栈
所以 空间复杂度：O (n log n)

改错题 (1): 能耗最小问题

错误原因分析

GPT 给出的代码超时（TLE），原因在于递归过程中 solve_segment 的开销过大。每次递归调用 bisect_right 和 bisect_left 都是在整个 points 数组上进行二分查找。

优化方案

在递归时，不仅传递区间的物理范围 $[L, R]$ ，同时传递该区间对应的目标点在 points 数组中的下标范围 $[pl, p r]$ 。这样可以在极小的范围内进行切分，大幅减少二分查找的开销。

修正后的代码

import sys
from bisect import bisect_right
 
def solve_segment(L, R, points, pl, pr, A, B):
    # 当前区间内的目标点数量
    cnt = pr - pl
    
    # 1. 如果没有目标点，直接返回 A
    if cnt == 0:
        return A
    
    # 计算当前区间长度
    length = R - L + 1
    
    # 2. 计算直接处理整个区间的代价
    cost_whole = B * cnt * length
    
    # 3. 如果区间长度为1，无法继续分割，返回直接处理代价
    if L == R:
        return cost_whole
    
    # 4. 分割处理
    mid = (L + R) // 2
    
    # 核心优化：在 [pl, pr] 范围内寻找分割点
    split_idx = bisect_right(points, mid, lo=pl, hi=pr)
    
    # 递归计算左右子区间，传入对应的下标范围
    cost_left = solve_segment(L, mid, points, pl, split_idx, A, B)
    cost_right = solve_segment(mid + 1, R, points, split_idx, pr, A, B)
    
    return min(cost_whole, cost_left + cost_right)
 
def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    iterator = iter(input_data)
    try:
        n = int(next(iterator))
        k = int(next(iterator))
        A = int(next(iterator))
        B = int(next(iterator))
        
        points = []
        for _ in range(k):
            points.append(int(next(iterator)))
            
        points.sort()
        
        total_len = 1 << n
        # 初始调用，传入整个 points 数组的下标范围 [0, k]
        print(solve_segment(1, total_len, points, 0, k, A, B))
        
    except StopIteration:
        pass
 
if __name__ == "__main__":
    # 增加递归深度以防万一
    sys.setrecursionlimit(200000)
    main()

预处理排序：O (k log k)
分治递归：最多 O (k n) 个区间，每个区间 bisect 一次 O (log k)
递归总时间 O (k n log k)
空间：O (k + n)

改错题 (2): “中间数”计数问题

错误原因分析

超时问题：原代码使用了简单的递归 dfs(r)，导致大量重复计算。
边界错误 (Wrong Answer)：当 $N = 2$ 时，最大距离为 1，不满足题目“距离大于 1”的条件，因此不能加入新点，答案应为 1。原代码错误地输出了 2。

优化方案

使用哈希搜索解决超时问题。
修正主函数的边界判断：当 $n \leq 2$ 时，直接输出 1。

修正后的代码

import sys
 
# 使用字典进行记忆化，存储 {长度: 节点数}
memo = {}
 
def solve(length):
    # 边界条件：
    # 只有当区间长度 >= 4 时，切分后的子段长度才可能 >= 2，
    # 从而产生距离 > 1 的新点。
    if length < 4:
        return 0
    
    if length in memo:
        return memo[length]
    
    # 当前能加 1 个点，然后裂变为两段
    left_len = length // 2
    right_len = length - left_len
    
    res = 1 + solve(left_len) + solve(right_len)
    memo[length] = res
    return res
 
def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    try:
        n = int(input_data[0])
    except ValueError:
        return
    
    # 修正逻辑：
    # 如果 n=1，集合 {1}，距离0，停止。ans=1。
    # 如果 n=2，集合 {1}，区间[1,2]最大距离1，不满足 >1，停止。ans=1。
    # 只有 n > 2 时，第一步才能加入 N，集合变为 {1, N}，并继续递归。
    if n <= 2:
        print(1)
        return
        
    ans = 2 + solve(n - 1)
    print(ans)
 
if __name__ == "__main__":
    main()

时间复杂度：O (n) （递归二分划分长度为 n 的区间，节点总数线性，memo 只会剪枝）

空间复杂度：O (n) （字典最多存 O (n) 个 length，递归栈 O (log n)）

along's Garden

Recent Writing

卷积神经网络 CNN简史与原理

大模型使用技巧

手撕梯度下降

Recent posts

读论文感想

llama3.2的实现,轻量化微调,及Triton优化

卜东波算法第一次作业

卜东波算法第一次作业

第一次作业解题报告

AI 协作题 (1): 区间最大值不小于和

题目分析

解题思路

代码实现

复杂度

AI 协作题 (2): 稠密有向无环图的构造

题目分析

1. 我们到底想要什么？

2. “我想要距离=2，但不想要距离=1”

3. 把点集分成左右两半，中间点连接整个两半

4. 如何让每一层都这么做？用“分治”！

5. 这个构造为什么边数不爆炸？

6. 距离 = 2 的点对数量为什么够大？

7. 换句话说，这个构造在做什么？

8. 构造的本质数学结构

9. 总结（完全理解后你应该能复述）

构造策略

代码实现 (Python)

4. 边的数量 m 的规模（顺便一并分析一下）

5. 空间复杂度分析

6. 总结一句话版本

改错题 (1): 能耗最小问题

错误原因分析

优化方案

修正后的代码

改错题 (2): “中间数”计数问题

错误原因分析

优化方案

修正后的代码

Graph View

Table of Contents