CSP-J 2023 初赛试题解析（第三部分：完善程序（1-2））

第一题补全后完整代码：

 #include <iostream> 
 #include <vector>

 using namespace std;

 int find_missing(vector<int>& nums) {
 int left = 0, right = nums.size() - 1;
while (left < right){
   int mid = left + (right-left) / 2;
   if (nums[mid] == mid+ nums[0] ) {
       left=mid+1;
    }else{
      right=mid;
    }
   }
  return left+nums[0];
 }

 int main() {
    int n;
 cin >> n;
 vector<int> nums(n);
 for (int i= 0; i< n; i++) cin >> nums[i];
 int missing_number = find_missing(nums);
 if(missing_number == nums[n-1] ) {
     cout << "Sequence is consecutive" << endl;
 }else{
    cout << "Missing number is " << missing_number << endl;
 }
 return 0;
 }

第二题补全后完整代码：

 #include <iostream>
 #include <string>
 #include <vector>
 using namespace std;
 
 int min(int x, int y, int z) {
   return min(min(x, y), z);
 } 

 int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
   
    for (int i = 0; i <= m; i++) {
          for (int j = 0; j <= n; j++) {
                  if (i == 0)
                         dp[i][j] = j;
                  else if (j == 0)
                         dp[i][j] = i;
                  else if (  str1[i-1]==str2[j-1] )
                         dp[i][j] = dp[i-1][j-1] ;
                  else
                         dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i-1][j-1] );
           }
    }
    return dp[m][n];
 }

 int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: "
           << edit_dist_dp(str1, str2) << endl;
    return 0;
 }