2025暑假CSP笔试笔记

完善程序

【noip2013】序列重排

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

const int SIZE=100; 
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。

void swap3(int p){
    int start1, end1, start2, end2, i, j, temp;
    start1 = 1;
    end1 = p;
    start2 = p + 1;
    end2 = n;
    while (true) {
        i = start1;
        j = start2;
        while ((i <= end1) && (j <= end2)) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j++;
        }
        if (i <= end1)
            start1 = i;
        else if (④) {
            start1 =⑤;
            end1 =⑥;
            start2 = j;
        }else
            break;
    }
}

二、最大子矩阵和

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

#include <iostream>
using namespace std;
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
int rowsum[SIZE + 1][SIZE + 1];
int m,n,i,j,first,last,area,ans;
int main(){
    cin >> m >> n;
    for(i = 1;i <= m;i++){
        for(j = 1;j <= n;j++){
            cin >> matrix[i][j];
        }
    }
    ans = matrix[1][1];
    for(i = 1;i <= m;i++){
        rowsum[i][0] = 0;
    }
    for(i = 1;i <= m;i++){
        for(j = 1;j <= n;j++){
            rowsum[i][j] = rowsum[i][j - 1] + matrix[i][j];
        }
    }
    for(first = 1;first <= n;first++){
        for(last = first;last <= n;last++){
            area = 0;
            for(i = 1;i <= m;i++){
                area += rowsum[i][last] - rowsum[i][first - 1];
                if(area > ans)ans = area;
                if(area < 0)area = 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

坐标统计

#include <iostream>
using namespace std;
const int SIZE = 100;
int x[SIZE],y[SIZE],f[SIZE];
int n,i,j,max_f,ans;
int main(){
    cin >>n;
    for(i = 1;i <= n;i++){
        cin >>x[i] >> y[i];
    }
    max_f = 0;
    for(i = 1;i <= n;i++){
        f[i] = 0;
        for(j = 1;j <= n;j++){
            if(x[j] < x[i] && y[j] < y[i]){
                f[i]++;
            }
        }
        if(f[i] >= max_f){
            max_f = f[i];
            ans = i;
        }
    }
    for(i = 1;i <= n;i++){
        cout << f[i] <<endl;
    }
    cout << ans << endl;
}

深度优先搜索算法

方阵填数

右上左数

#include <iostream>
#include <iomanip>
using namespace std;
int a[10][10];
void f(int x,int y,int k){
    a[x][y] = k;
    if(y + 1 <= 4 && a[x][y + 1] == 0){
        f(x,y + 1,k + 1);
    }
    if(x + 1 <= 4 && a[x + 1][y] == 0){
        f(x + 1,y,k + 1);
    }
    if(y - 1 >= 1 && a[x][y - 1] == 0){
        f(x,y - 1,k + 1);
    }
    if(x - 1 >= 1 && a[x - 1][y] == 0){
        f(x - 1,y,k + 1);
    }
}
int main(){
    f(1,1,1);
    for(int i = 1;i <= 4;i++){
        for(int j = 1;j <= 4;j++){
            cout << setw(5) << a[i][j];
        }
    }
    return 0;
}

快速排序

#include <iostream>
using namespace std;
int a[100] = {0};
int n;
void quickSort(int left,int right){
    if(left >= right){
        return;
    }
    int i = left;
    int j = right;
    int mid = (left + right) / 2;
    int p = a[mid];
    while(i <= j){
        while(a[i] < p){
            i++;
        }
        while(a[j] > p){
            j--;
        }
        if(i <= j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(left < j){
        quickSort(left,j);
    }
    if(i < right){
        quickSort(i,right);
    }
}
int main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    quickSort(0,n - 1);
    for(int i = 0;i < n;i++){
        cout << a[i] << " ";
    }
    return 0;
}