第四章 阅读程序

第一课 模拟策略

【NOIP2011】（累加）

例：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int i,n,m,ans;
  5.     cin>>n>>m;
  6.     i=n;
  7.     ans=0;
  8.     while (i<=m){
  9.         ans+=i;
  10.         i++;
  11.     }
  12.     cout<<ans<<endl;
  13.     return 0;
  14. }

360截图20250812204621958.jpg

答案：× × √ √ B A

解析： 360截图20250812205130993.jpg

第二课 字符处理

【NOIP2009】（二分字符排序）

例：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=50;
  4. void getnext(char str[]){
  5.     int l=strlen(str),i,j,k,temp;
  6.     k=l-2;
  7.     while (k>=0 && str[k]>str[k+1]) k--;
  8.     i=k+1;
  9.     while (i<l && str[i]>str[k]) i++;
  10.     temp=str[k];
  11.     str[k]=str[i-1];
  12.     str[i-1]=temp;
  13.     for (i=l-1;i>k;i--){
  14.         for (j=k+1;j<i;j++){
  15.             if (str[j]>str[j+1]){
  16.                 temp=str[j];
  17.                 str[j]=str[j+1];
  18.                 str[j+1]=temp;
  19.             }
  20.         }
  21.     }
  22.     return ;
  23. }
  24. int main(){
  25.     char a[maxn];
  26.     int n;
  27.     cin>>a>>n;
  28.     while (n>0){
  29.         getnext(a);
  30.         n--;
  31.     }
  32.     cout<<a<<endl;
  33.     return 0;
  34. }

360截图20250813161402228.jpg

答案：× √ √ √ A B

解析： 360截图20250813161619313.jpg

第三课 枚举算法

【NOIP2013】（判断字符是否为回文）

例：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     string str;
  5.     cin>>str;
  6.     int n=str.size();
  7.     bool isPlalindrome=true; // isPlalindrome译为：回文数
  8.     for (int i=0;i<n/2;i++){
  9.         if (str[i]!=str[n-i-1]){
  10.             isPlalindrome=false;
  11.             break;
  12.         }
  13.     }
  14.     if (isPlalindrome) cout<<"Yes";
  15.     else cout<<"No";
  16.     return 0;
  17. }

360截图20250815155532057.jpg

答案：× √ √ √ A B

解析：360截图20250815155716936.jpg

【NOIP2013】本题的函数写法

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool is_Plalindrome(string s){
  4.     int size=s.size();
  5.     for (int i=0;i<size;i++){
  6.         if (s[i]!=s[size-i-1]) return false;
  7.     }
  8.     return true;
  9. } // 判断回文字符串函数
  10. int main(){
  11.     string str;
  12.     cin>>str;
  13.     int n=str.size();
  14.     if (is_Plalindrome(str)) cout<<"Yes";
  15.     else cout<<"No";
  16.     return 0;
  17. }

【NOIP2017】（字符串中第一个仅出现一次的字母）

例：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int t[256];
  5.     string s;
  6.     int i;
  7.     cin>>s;
  8.     for (i=0;i<256;i++) t[i]=0;
  9.     for (i=0;i<s.length();i++) t[s[i]]++;
  10.     for (i=0;i<s.length();i++){
  11.         if (t[s[i]]==1){
  12.             cout<<s[i]<<endl;
  13.             return 0;
  14.         }
  15.     }
  16.     cout<<"no";
  17.     return 0;
  18. }

360截图20250815161747673.jpg

答案：× × √ × B B

解析：360截图20250815161842489.jpg 360截图20250815161851285.jpg

第四课 排序算法

【NOIP2010】（给定两个有序数列，合并成一个新的数列）

例：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE=100;
  4. int na,nb,a[SIZE],b[SIZE],i,j,k;
  5. int main(){
  6.     cin>>na;
  7.     for (i=1;i<=na;i++) cin>>a[i];
  8.     cin>>nb;
  9.     for (i=1;i<=nb;i++) cin>>b[i];
  10.     i=1;
  11.     j=1;
  12.     while ((i<=na) && (j<=nb)){
  13.         if (a[i]<=b[j]){
  14.             cout<<a[i]<<' ';
  15.             i++;
  16.         }
  17.         else{
  18.             cout<<b[j]<<' ';
  19.             j++;
  20.         }
  21.     }
  22.     if (i<=na){
  23.         for (k=i;k<=na;k++) cout<<a[k]<<' ';
  24.     }
  25.     if (j<=nb){
  26.         for (k=j;k<=nb;k++) cout<<b[k]<<' ';
  27.     }
  28.     return 0;
  29. }

360截图20250816162045354.jpg

答案：√ √ × √ A A

解析：360截图20250816162155989.jpg

附：归并排序

1.算法介绍

  • 归并排序是一种高效的 分治法(Divide and Conquer)排序算法，核心思想：
  • 1️⃣ 分解：将数组递归拆分为最小单位（单个元素）
  • 2️⃣ 合并：将有序子数组合并为更大有序数组
  • ✅ 时间复杂度：最优/平均/最坏均为 O(n log n)
  • ✅ 稳定性：稳定排序（相同元素顺序不变）
  • ✅ 适用场景：大数据量、链表排序、外部排序

2. 分治思想图解

  1. 初始数组： [38, 27, 43, 3, 9, 82, 10]  
  2.             ↓ 分解  
  3. [38, 27, 43]      [3, 9, 82, 10]  
  4.     ↓ 分解             ↓ 分解  
  5. [38] [27, 43]    [3,9] [82,10]  
  6.      ↓ 合并           ↓ 合并  
  7. [27, 38, 43]      [3,9,10,82]  
  8.             ↓ 合并  
  9.      [3,9,10,27,38,43,82]

3. 合并操作详解

核心步骤：合并两个有序数组

  1. Left数组: [27, 38, 43]   Right数组: [3, 9, 10, 82]  
  2. Step1: 比较左首(27) vs 右首(3) → 取较小值 3  
  3. Step2: 比较 27 vs 9 → 取 9  
  4. Step3: 比较 27 vs 10 → 取 10  
  5. Step4: 直接追加左数组：[27,38,43]  
  6. 结果：[3, 9, 10, 27, 38, 43, 82]

4. C++ 代码实现

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int arr[7]={38,27,43,3,9,82,10};
  4. int brr[7];
  5. void merge(int a[],int b[],int l,int mid,int r){
  6.     // 合并为有序数列
  7.     int i=l,j=mid+1,k=l;
  8.     // 从左右两边依次判断较小值进行合并
  9.     while (i<=mid && j<=r){
  10.         if (a[i]<=a[j]) b[k++]=a[i++];
  11.         else b[k++]=a[j++];
  12.     }
  13.     while (i<=mid) b[k++]=a[i++];
  14.     while (j<=r) b[k++]=a[j++];
  15.     for (int i=l;i<=r;i++) a[i]=b[i];
  16. }
  17. void mergeSort(int a[],int l,int r){
  18.     // 分解原数组
  19.     if (l>=r) return ;
  20.     // 计算中间值
  21.     int mid=(l+r)/2;
  22.     mergeSort(a,l,mid); // 左数列
  23.     mergeSort(a,mid+1,r); // 右数列
  24.     // 合并
  25.     merge(arr,brr,l,mid,r);
  26. }
  27. int main(){
  28.     mergeSort(0,9); // 左边界和右边界
  29.     for (int i=0;i<9;i++) cout<<arr[i]<<' ';
  30.     return 0;
  31. }

输出：3 9 10 27 38 43 82

5. 关键点分析

  • 递归深度：共 log₂n 层分解
  • 合并成本：每层合并需 O(n) 操作
  • 空间复杂度：O(n)（临时数组开销）
  • 优化策略：
    • 小数组用插入排序减少递归开销
    • 避免频繁内存分配（全局复用 temp 数组）

6. 与快速排序对比

360截图20250820170055818.jpg

7. 可视化演示推荐

🔗归并排序动画演示

（动态理解分解与合并过程）

总结

归并排序以时间换空间，凭借稳定且可预测的性能，成为大规模数据排序的基石算法！

第五课 搜索算法

1.二分查找

1.标准二分查找

代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE=105;
  4. int n,x,arr[SIZE];
  5. int binary_search(int x){
  6.     int l=0,r=n;
  7.     while (l+1<r){
  8.         int mid=(l+r)>>1;
  9.         if (x==arr[mid]) return mid;
  10.         else if (x>arr[mid]) l=mid;
  11.         else r=mid;
  12.     }
  13.     return -1;
  14. }
  15. int main(){
  16.     cin>>n;
  17.     for (int i=0;i<n;i++) cin>>arr[i];
  18.     cin>>x;
  19.     cout<<binary_search(x);
  20.     return 0;
  21. }

2.给定两个数组，从A数组中找出B数组中的内容，并按从小到大进行排序

代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE=10005;
  4. int n,m,arr[SIZE],brr[SIZE];
  5. int binary_search(int x){
  6.     int l=0,r=n+1;
  7.     while (l+1<r){
  8.         int mid=(l+r)>>1;
  9.         if (x==arr[mid]) return mid;
  10.         else if (x>arr[mid]) l=mid;
  11.         else r=mid;
  12.     }
  13.     return 0;
  14. }
  15. int main(){
  16.     cin>>n>>m;
  17.     for (int i=1;i<=n;i++) cin>>arr[i];
  18.     for (int i=1;i<=m;i++) cin>>brr[i];
  19.     sort(arr+1,arr+n+1);
  20.     sort(brr+1,brr+m+1);
  21.     // 二分查找
  22.     for (int i=1;i<=m;i++){
  23.         if (binary_search(brr[i])) cout<<brr[i]<<' ';
  24.     }
  25.     return 0;
  26. }

3.[USACO05FEB] 进击的奶牛

360截图20250823172235241.jpg

代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a[100005];
  4. int main(){
  5.     cin>>n>>m;
  6.     for (int i=1;i<=n;i++) cin>>a[i];
  7.     sort(a+1,a+n+1);
  8.     int l=0,r=a[n]+1,mid;
  9.     while (l+1!=r){
  10.         mid=(l+r)/2;
  11.         int cnt=1,pre=a[1];
  12.         for (int i=2;i<=n;i++){
  13.             if (a[i]-pre>=mid){
  14.                 cnt++;
  15.                 pre=a[i];
  16.             }
  17.         }
  18.         if (cnt>=m) l=mid;
  19.         else r=mid;
  20.     }
  21.     cout<<l;
  22.     return 0;
  23. }

2.深度优先搜索（DFS）

1.引子（给方阵以“右、下、左、上”的顺序填数引入深搜）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[10][10];
  4. void f(int x,int y,int k){
  5.     a[x][y]=k;
  6.     if (y+1<=4 && a[x][y+1]==0) f(x,y+1,k+1);
  7.     if (x+1<=4 && a[x+1][y]==0) f(x+1,y,k+1);
  8.     if (y-1>=1 && a[x][y-1]==0) f(x,y-1,k+1);
  9.     if (x-1>=1 && a[x-1][y]==0) f(x-1,y,k+1);
  10. }
  11. int main(){
  12.     f(1,1,1);
  13.     for (int i=1;i<=4;i++){
  14.         for (int j=1;j<=4;j++) cout<<setw(5)<<a[i][j];
  15.         cout<<endl;
  16.     }
  17.     return 0;
  18. }

输出：

  1.     1    2    3    4
  2.    16   15   14    5
  3.    11   12   13    6
  4.    10    9    8    7

2.深搜的基础框架

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,path[410][3];
  4. char a[30][30];
  5. void print(int k){
  6.     for (int i=1;i<=k;i++){
  7.         cout<<'('<<path[i][1]<<','<<path[i][2]<<')';
  8.         if (i!=k) cout<<"->";
  9.     }
  10.     exit(0);
  11. }
  12. void dfs(int x,int y,int k){
  13.     path[k][1]=x;
  14.     path[k][2]=y;
  15.     a[x][y]='1';
  16.     if (x==n && y==n) print(k);
  17.     if (a[x][y-1]=='0') dfs(x,y-1,k+1);
  18.     if (a[x-1][y]=='0') dfs(x-1,y,k+1);
  19.     if (a[x][y+1]=='0') dfs(x,y+1,k+1);
  20.     if (a[x+1][y]=='0') dfs(x+1,y,k+1);
  21. }
  22. int main(){
  23.     cin>>n;
  24.     for (int i=1;i<=n;i++){
  25.         for (int j=1;j<=n;j++) cin>>a[i][j];
  26.     }
  27.     dfs(1,1,1);
  28.     return 0;
  29. }

附：快速排序

  1. #include <iostream>
  2. using namespace std;
  3. int a[100] = {0};
  4. int n;
  5. void quickSort(int left,int right){
  6.     if(left >= right){
  7.         return;
  8.     }
  9.     int i = left;
  10.     int j = right;
  11.     int mid = (left + right) / 2;
  12.     int p = a[mid];
  13.     while(i <= j){
  14.         while(a[i] < p){
  15.             i++;
  16.         }
  17.         while(a[j] > p){
  18.             j--;
  19.         }
  20.         if(i <= j){
  21.             swap(a[i],a[j]);
  22.             i++;
  23.             j--;
  24.         }
  25.     }
  26.     if(left < j){
  27.         quickSort(left,j);
  28.     }
  29.     if(i < right){
  30.         quickSort(i,right);
  31.     }
  32. }
  33. int main(){
  34.     cin >> n;
  35.     for(int i = 0;i < n;i++){
  36.         cin >> a[i];
  37.     }
  38.     quickSort(0,n - 1);
  39.     for(int i = 0;i < n;i++){
  40.         cout << a[i] << " ";
  41.     }
  42.     return 0;
  43. }