高级完善程序技巧

概念讲解

什么是高级完善程序？

高级完善程序是 CSP-S 初赛的重要题型，要求考生根据上下文推断缺失的代码。

与 J 级的区别

  • 涉及更复杂的算法（DP、图论、数据结构）
  • 代码量更大，逻辑更复杂
  • 需要理解算法整体思路

解题技巧

1. 理解算法意图

先通读整个程序，理解它要解决什么问题。

2. 分析变量含义

弄清楚每个变量代表什么，如何变化。

3. 推断缺失逻辑

根据已有代码和输出，推断缺失部分的逻辑。

4. 验证答案

将选项代入，用样例验证是否正确。

考点分析

初赛考查方式

  1. 完善程序题： 补全复杂算法的缺失代码
  2. 选择题： 选择正确的代码片段

常见题型

  • 动态规划
  • 搜索算法
  • 图论算法
  • 数据结构操作

例题精讲

例题 1：二分查找

题目： 补全二分查找代码。

12345678910int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;
    while (______) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) ______;
        else ______;
    }
    return -1;
}

解析： 二分查找的关键是正确更新 left 和 right。

答案：left <= right、left = mid + 1、right = mid - 1

例题 2：快速排序

题目： 补全快速排序的分区函数。

123456789101112int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = ______;
    for (int j = low; j < high; j++) {
        if (______) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(______, a[high]);
    return ______;
}

解析： 分区函数将数组分为两部分，左边小于 pivot，右边大于 pivot。

答案：low - 1、a[j] <= pivot、a[i + 1]、i + 1

练习题

  1. 补全归并排序代码
查看答案

归并排序的关键代码：

12345678910111213141516171819void merge(int a[], int l, int mid, int r) {
    int temp[r - l + 1];
    int i = l, j = mid + 1, k = 0;
    
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    
    for (int i = 0; i < k; i++) {
        a[l + i] = temp[i];
    }
}
  1. 补全 Dijkstra 算法代码
查看答案

Dijkstra 算法的关键代码：

12345678910111213141516171819void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
  1. 补全背包 DP 代码
查看答案

0-1 背包的关键代码：

1234567891011int knapsack(int n, int W, int w[], int v[]) {
    int dp[W + 1] = {0};
    
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

注意：0-1 背包要逆序遍历，完全背包要正序遍历。

易错点

⚠️ 注意：

  1. 先理解算法再做题
  2. 注意边界条件
  3. 代入样例验证
  4. 注意变量的含义和变化