编辑“︁典型竞赛题型分析”︁（章节）

== 常见题型及分析 ==

=== 1. 动态规划（Dynamic Programming, DP） ===
动态规划是一种通过将问题分解为子问题来优化计算的算法设计方法。典型的动态规划问题具有'''重叠子问题'''和'''最优子结构'''的特性。

==== 示例：斐波那契数列 ====
计算第 n 个斐波那契数（Fibonacci number）是动态规划的经典入门问题。

<syntaxhighlight lang="python">
def fibonacci(n):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
</syntaxhighlight>

'''输入：''' 5  
'''输出：''' 5  
'''解释：''' 使用动态规划避免了递归的重复计算，时间复杂度从 O(2^n) 优化到 O(n)。

==== 实际应用 ====
动态规划广泛应用于背包问题、最长公共子序列（LCS）、最短路径问题（如 Floyd-Warshall 算法）等。

=== 2. 贪心算法（Greedy Algorithm） ===
贪心算法通过每一步的局部最优选择来达到全局最优解，适用于某些特定问题（如活动选择、霍夫曼编码）。

==== 示例：活动选择问题 ====
从一组活动中选出尽可能多的互不冲突的活动。

<syntaxhighlight lang="python">
def activity_selection(start, finish):
    activities = list(zip(start, finish))
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    selected = [activities[0]]
    for act in activities[1:]:
        if act[0] >= selected[-1][1]:  # 检查是否冲突
            selected.append(act)
    return selected
</syntaxhighlight>

'''输入：''' start = [1, 3, 0, 5, 8], finish = [2, 4, 6, 7, 9]  
'''输出：''' [(1, 2), (3, 4), (5, 7), (8, 9)]  
'''解释：''' 每次选择最早结束的活动，确保最大化活动数量。

=== 3. 图论问题（Graph Theory） ===
图论问题涉及图的遍历（DFS/BFS）、最短路径（Dijkstra）、最小生成树（Kruskal/Prim）等。

==== 示例：Dijkstra 算法 ====
求解单源最短路径。

<syntaxhighlight lang="python">
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        current_dist, current_node = heapq.heappop(heap)
        if current_dist > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances
</syntaxhighlight>

'''输入：''' graph = {'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2}, 'C': {'A': 4, 'B': 2}}  
'''输出：''' {'A': 0, 'B': 1, 'C': 3}  
'''解释：''' 从节点 A 出发，计算到其他节点的最短路径。

=== 4. 数学问题（Mathematical Problems） ===
包括数论、组合数学、概率统计等，常见于竞赛中。

==== 示例：快速幂算法 ====
计算 <math>a^b \mod m</math> 的高效方法。

<syntaxhighlight lang="python">
def fast_pow(a, b, m):
    result = 1
    a = a % m
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % m
        a = (a * a) % m
        b = b // 2
    return result
</syntaxhighlight>

'''输入：''' a = 2, b = 10, m = 1000  
'''输出：''' 24  
'''解释：''' 计算 <math>2^{10} \mod 1000 = 1024 \mod 1000 = 24</math>，时间复杂度 O(log b)。