#竞赛/技巧

一、动态规划与二维数组的化学反应

1. 经典模型

// 数字三角形最大路径和（NOIP 2005普及组真题）
for(int i = n-2; i >=0; i--)
    for(int j=0; j<=i; j++)
        dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);

// 网格路径计数（注意初始化边界）
dp[0][0] = 1;
for(int i=0; i<m; i++)
    for(int j=0; j<n; j++)
        if(grid[i][j] !=障碍)
            dp[i][j] += dp[i-1][j] + dp[i][j-1];

2. 状态压缩技巧

// 滚动数组优化（适用于只需要前一行状态的DP）
int dp[2][N]; // 奇偶滚动
for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]) + val;

---

二、二维差分高阶应用

1. 区域修改模板

// 给子矩阵(x1,y1)-(x2,y2)增加k
diff[x1][y1] += k;
diff[x1][y2+1] -= k;
diff[x2+1][y1] -= k;
diff[x2+1][y2+1] += k;

// 最终通过二维前缀和还原
for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++)
        diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];

2. 真题应用场景

• 图像滤镜处理（区域模糊/锐化）

• 棋盘覆盖问题

• 实时统计区域最大值

---

三、特殊遍历模式扩展

1. Z字形遍历（适合矩阵压缩场景）

for(int i=0; i<n; i++){
    if(i%2 ==0)
        for(int j=0; j<m; j++) cout << a[i][j];
    else
        for(int j=m-1; j>=0; j--) cout << a[i][j];
}

2. 菱形遍历（处理中心扩散问题）

int directions[4][2] = {{1,1}, {1,-1}, {-1,-1}, {-1,1}}; // 四象限扩散
for(int step=1; step<=radius; step++)
    for(int dir=0; dir<4; dir++)
        for(int k=0; k<step; k++)
            // 处理(x+dx*step, y+dy*step)

---

四、图论问题中的二维映射

1. 网格坐标转换

// 将二维坐标编码为一维（用于并查集/哈希存储）
int hash(int x, int y) { return x*1000 + y; } // 假设列数<1000

// 解码函数
pair<int,int> decode(int num) {
    return {num/1000, num%1000};
}

2. BFS优化模板

// 使用方向数组 + 队列
struct Node { int x, y, step; };
queue<Node> q;
bool vis[N][N]; // 必须的访问标记

while(!q.empty()){
    auto t = q.front(); q.pop();
    for(int i=0; i<4; i++){
        int nx = t.x + dx[i], ny = t.y + dy[i];
        if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]){
            vis[nx][ny] = true;
            q.push({nx, ny, t.step+1});
        }
    }
}

---

五、输入输出优化秘籍

1. 快速读入模板

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

// 使用方法
for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        a[i][j] = read();

2. 输出优化技巧

// 预先分配缓冲区（减少cout调用次数）
string buf;
for(int i=0; i<n; i++){
    for(int j=0; j<m; j++)
        buf += to_string(a[i][j]) + " ";
    buf += "\n";
}
cout << buf;

---

六、致命错误案例库

1. 经典翻车现场

// 错误案例1：行列颠倒
int arr[3][4];
for(int i=0; i<4; i++) // 错误！行数应该是3
    for(int j=0; j<3; j++) // 错误！列数应该是4
        cin >> arr[i][j];

// 错误案例2：忘记初始化
int local_arr[100][100]; // 不会自动初始化为0！
memset(local_arr, -1, sizeof(local_arr)); // 正确做法

2. 越界的幽灵

// 正确边界检查模板
#define inRange(x, y) (x >=0 && x <n && y >=0 && y <m)

// 错误写法：先访问后判断
if(a[x][y] > 0 && x <n && y <m) // 可能已越界！

---

七、综合训练营

1. 经典变式题

• 矩阵中的最长递增路径（DFS+记忆化）

• 01矩阵中的最大正方形（动态规划）

• 稀疏矩阵的压缩存储（三元组表示法）

2. CSP-J 仿真题

// 2023模拟题：激光路径计算
题目描述：
给定n×m网格，某些格子有反射镜（/ 或 \），
求从左上角向右发射的激光最终位置。

解题思路：
1. 使用方向数组记录光线状态
2. 遇到镜子时改变方向
3. 设置访问标记防止无限循环

---

八、时空复杂度速查表

操作	时间复杂度	空间复杂度	应用场景
暴力遍历	O(n²)	O(1)	小规模数据(n≤1000)
二维前缀和查询	O(1)	O(n²)	频繁子矩阵求和
BFS搜索最短路径	O(nm)		迷宫类问题
动态规划路径计数			网格路径问题
矩阵快速幂	O(n³logk)	O(n²)	矩阵递推问题（进阶）