#竞赛/技巧

一、核心概念精要

1. 内存本质

• 行优先存储：a[2][3] 的内存顺序：a[0][0] → a[0][1] → a[0][2] → a[1][0]...

• 计算元素位置：a[i][j] 地址 = 基地址 + (i * 列数 + j) * sizeof(类型) （笔试可能考察）

2. 特殊声明技巧

// 动态声明（竞赛常用）
const int N = 1005;
int grid[N][N];  // 全局数组自动初始化为0

// 初始化黑科技
int dirs[][3] = {{}, {2,3,4}, {5,6}}; // 第一维可自动推导

---

二、必杀技工具箱

1. 降维打击法

// 将二维转一维处理
for(int k=0; k<n*m; k++){
    int i = k/m;  // 行号
    int j = k%m;  // 列号
    cout << a[i][j];
}

2. 矩阵镜像九式

// 顺时针旋转90度（高频考点！）
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 先转置
    for(int i=0; i<n; i++)
        for(int j=i; j<n; j++)
            swap(matrix[i][j], matrix[j][i]);
    // 再水平翻转
    for(int i=0; i<n; i++)
        reverse(matrix[i].begin(), matrix[i].end());
}

3. 蛇形遍历技巧

// 对角线蛇形输出（NOIP 2013普及组真题）
int dx[] = {-1, 1}, dy[] = {1, -1};
int x = 0, y = 0, dir = 0;
while(/* 未遍历完 */){
    cout << a[x][y];
    x += dx[dir]; y += dy[dir];
    if(越界) { /* 调整方向 */ }
}

---

三、高频考题模式库

1. 矩阵变换三巨头

题型	解题要点	真题案例
旋转矩阵	找旋转前后坐标关系	2021年T2 数字变换
缩放矩阵	处理浮点数时的精度问题	2018年T3 图像处理
对称矩阵	分轴对称为奇偶情况	2020年T4 对称平方数

2. 搜索类问题

// 四方向移动模板（DFS/BFS通用）
const int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
bool vis[N][N]; // 必须的访问标记

void dfs(int x, int y){
    vis[x][y] = true;
    for(int i=0; i<4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]){
            // 处理逻辑
            dfs(nx, ny);
        }
    }
}

---

四、考场生存指南

1. 防爆雷区

• 内存计算：int a[1000][1000] = 1000_1000_4B ≈ 4MB（CSP-J通常允许）

• 越界陷阱：循环条件严格检查 i<n 而非 i<=n

• 初始化的坑：局部数组不会自动初始化为0！

2. 复杂度预判

数据规模	允许时间复杂度	典型算法
n≤100	O(n³)	暴力枚举
n≤500	O(n²)	二维前缀和
n≤1e4	O(n)	单次遍历+哈希

3. 调试锦囊

// 矩阵打印调试函数
void debug(int a[][N], int n, int m){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
            cerr << setw(3) << a[i][j]; // 使用cerr防止影响cout
        cerr << endl;
    }
}

---

五、真题训练包

1. 矩阵查数（2019年CSP-J T2）

   • 关键技巧：利用矩阵有序性进行二分查找

2. 图像模糊（2022年CSP-J T3）

   • 核心考点：二维前缀和快速计算区域平均值

3. 迷宫最短路（2020年CSP-J T4）

   • BFS模板题 + 方向数组应用