题解：P5461 赦免战俘

LG_Sam · 2025-07-08 21:28:09 · 题解

题解：P5461 赦免战俘

题目传送门

本题可以通过递归求解。先用递归分解出左上角矩阵，把左上角矩阵所有元素设为 0 ，即该作弊者被赦免。接着对右上、左下、右下进行同样操作，直到矩阵大小为 1 时停止。

AC code

这里运用了一个小技巧：左移运算符 << 。
i<<n 这行代码相当于 i \times 2^n，不过要注意位运算的优先级很低，和加减法搭配使用时注意加括号。

#include<bits/stdc++.h>
using namespace std;
bool cheaters[1030][1030];//作弊者被处罚的状态，0 表示赦免，1 表示处罚（即棕名）
void init(){//初始化函数，初始每名作弊者都将被处罚
    for(int i=0;i<1030;i++){
        for(int j=0;j<1030;j++){
            cheaters[i][j]=1;
        }
    }
}
void kill(int x,int y,int p){//递归，x 和 y 表示矩阵中左上顶点的坐标，p 表示当前矩阵的大小为 2^p * 2^p
    if(p==0) return;//如果 p 等于 0，说明此时矩阵大小为0，返回
    int s=1<<p-1;//s 表示分出的每个矩阵的边长
    for(int i=x;i<=x+s-1;i++){
        for(int j=y;j<=y+s-1;j++){
            cheaters[i][j]=0;//赦免左上矩阵中的所有作弊者
        }
    }
    kill(x+s,y,p-1);//递归右上矩阵
    kill(x,y+s,p-1);//递归左下矩阵
    kill(x+s,y+s,p-1);//递归右下矩阵
}
int main(){
    init();//初始化
    int n;
    cin>>n;
    kill(1,1,n);//递归整个矩阵，此时左上角的 x 和 y 坐标都为 1，层数为 n
    for(int i=1;i<=1<<n;i++){
        for(int j=1;j<=1<<n;j++){
            cout<<cheaters[i][j]<<" ";//循环输出
        }
        cout<<endl;
    }
    return 0;//完结撒花
}