2025暑假CSP笔试笔记

完善程序

【noip2013】序列重排

全局数组变量 a 定义如下：

  1. const int SIZE=100; 
  2. int a[SIZE],n;

它记录着一个长度为 n 的序列 a[1] ，a[2] ，… ， a[n] 。现在需要一个函数，以整数 p(1 ≤p≤ n) 为参数，

实现如下功能： 将序列 a 的前 p 个数与后 n-p 个数对调， 且不改变这 p 个数（或 n-p 个数）之间的相对位置。

例如，长度为 5 的序列 1， 2，3，4，5，当 p=2 时重排结果为 3，4， 5，1，2。

  1. void swap3(int p){
  2.     int start1, end1, start2, end2, i, j, temp;
  3.     start1 = 1;
  4.     end1 = p;
  5.     start2 = p + 1;
  6.     end2 = n;
  7.     while (true) {
  8.         i = start1;
  9.         j = start2;
  10.         while ((i <= end1) && (j <= end2)) {
  11.             temp = a[i];
  12.             a[i] = a[j];
  13.             a[j] = temp;
  14.             i++;
  15.             j++;
  16.         }
  17.         if (i <= end1)
  18.             start1 = i;
  19.         else if (④) {
  20.             start1 =⑤;
  21.             end1 =⑥;
  22.             start2 = j;
  23.         }else
  24.             break;
  25.     }
  26. }

二、最大子矩阵和

给出 m行 n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。 输入第一行包含两个整数 m和 n，即矩阵的行数和列数。之后 m行，每行 n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。

  1. #include <iostream>
  2. using namespace std;
  3. const int SIZE = 100;
  4. int matrix[SIZE + 1][SIZE + 1];
  5. int rowsum[SIZE + 1][SIZE + 1];
  6. int m,n,i,j,first,last,area,ans;
  7. int main(){
  8.     cin >> m >> n;
  9.     for(i = 1;i <= m;i++){
  10.         for(j = 1;j <= n;j++){
  11.             cin >> matrix[i][j];
  12.         }
  13.     }
  14.     ans = matrix[1][1];
  15.     for(i = 1;i <= m;i++){
  16.         rowsum[i][0] = 0;
  17.     }
  18.     for(i = 1;i <= m;i++){
  19.         for(j = 1;j <= n;j++){
  20.             rowsum[i][j] = rowsum[i][j - 1] + matrix[i][j];
  21.         }
  22.     }
  23.     for(first = 1;first <= n;first++){
  24.         for(last = first;last <= n;last++){
  25.             area = 0;
  26.             for(i = 1;i <= m;i++){
  27.                 area += rowsum[i][last] - rowsum[i][first - 1];
  28.                 if(area > ans)ans = area;
  29.                 if(area < 0)area = 0;
  30.             }
  31.         }
  32.     }
  33.     cout << ans << endl;
  34.     return 0;
  35. }