【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。有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n) 、空间复杂度为 O(n)

可以用时间换空间，使用时间复杂度为O(n^2)、空间复杂度为 O(1) 的算法：

本题答案：

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int a[SIZE] , n; 
void swap(int p){
    int i,j,temp;
    for(i = p+1 ; i <= n; i ++){
        temp = a[i];
        for(j = i ; j >= i-p+1 ; j --){
            a[j] =a[j-1];
        }
        a[i-p] = temp; 
    }
}
int main(){
    int p;
    cin >> n >> p;
    for (int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    swap(p);
    for (int i = 1 ; i <= n ; i ++){
        cout <<  a[i];
    }
    return 0;
}

【noip2014】最大子矩阵：

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

本题答案：

#include<bits/stdc++.h>
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(){
    scanf("%d",&n);
    m=n;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++){
            scanf("%d", &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;
            }
        }
    printf("%d\n", ans);
    return 0;
}

矩阵转换

题目1

#include<bits/stdc++.h>
using namespace std;
int main(){
    int arr[3][2] = {
        {1,2},
        {3,4},
        {5,6}
    };
    int brr[2][3] = { 0 };
    for (int i = 0 ; i < 2 ; i++){
        for(int j = 0 ; j < 3 ; j ++){
            brr[i][j] = arr[j][i];
        }
    }
    for (int i = 0 ; i < 2 ; i++){
        for(int j = 0 ; j < 3 ; j ++){
            cout << brr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

题目2

#include<bits/stdc++.h>
using namespace std;
int* Matr(const int* matrix , int size_r , int size_c , int* new_matrix){
    int flag = 0 ;
    for (int i = 0 ; i < size_r * size_c ; i++){
        cout << matrix[i] << " ";
        flag++;
        if(flag == size_c){
            cout << endl;
            flag = 0;
        }
    }
    for(int row = 0 ; row < size_r ; row++){
        for(int col = 0 ; col< size_c ; col++){
            new_matrix[col * size_r + row] = matrix[row * size_c + col];
        }
    }
    for (int i = 0 ; i < size_r * size_c ; i++){
        cout << new_matrix[i] << " ";
        flag++;
        if(flag == size_r){
            cout << endl;
            flag = 0;
        }
    }
    return new_matrix;
}
int main(){
    int arr[6] = {1,2,3,4,5,6};
    int row = -1 , col = -1;
    int* brr = new int[row * col];
    matrix(arr,row,col,brr);
    return 0;
}

第一节

【noip2013】序列重排：

本题答案：

【noip2014】最大子矩阵：

本题答案：

矩阵转换

题目1

题目2