题解：P5461 赦免战俘

wangyang168 · 2025-06-29 10:36:16 · 题解

思路：

在做这道题之前，建议大家去做一下 P5732杨辉三角，为什么这样说呢？因为这道题其实有一个递推解，和杨辉三角极为相似。我们把整个方阵看作一个二维数组 a，并将 a 数组归零，将方阵第一项设为 a[1][1]，从而防止数组越位。这样可以发现 a[i][j] 的值便等于 a[i-1][j+1] 的值加上 a[i-1][j] 的值除以 2 的余数。接着，我们将 a[1][1] 的值为 0，再定义 n2 表示方阵的边长，于是就这样写下了代码。

#include<bits/stdc++.h>
using namespace std;
int shj(int n){
    return 1<<n;
}
int main(){
    bool a[5000][5000]={0};
    int n;
    cin>>n;
    int n2=shj(n);
    a[1][1]=0;
    for(int i=1;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            a[i][j]=(a[i-1][j+1]+a[i-1][j])%2;
        }
    }
    for(int i=1;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

然而却输出了一堆 0。

我们继续来看，方阵第一行大多都是 0，然而第一行的最后一个是 1，如果把第一个设为 0 并没有什么用，但如果我们把 a[1][n2] 设为 1 的话，这个问题不就解决了吗？

#include<bits/stdc++.h>
using namespace std;
int shj(int n){
    return 1<<n;
}
int main(){
    bool a[5000][5000]={0};
    int n;
    cin>>n;
    int n2=shj(n);
    a[1][n2]=1;
    for(int i=1;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            a[i][j]=(a[i-1][j+1]+a[i-1][j])%2;
        }
    }
    for(int i=1;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

然而却依然是一堆 0。

我们再来看，我们虽然把 a[1][n2] 定为 1，可当进行循环后又被覆盖了。因为方阵第一行最开始就被定义好了，所以解决这个问题的办法就是：从第二行开始运行！ 即为跳过第一行，外层的循环从 2 开始。

代码：

#include<bits/stdc++.h>
using namespace std;
int shj(int n){
    return 1<<n;
}
int main(){
    bool a[5000][5000]={0};
    int n;
    cin>>n;
    int n2=shj(n);
    a[1][n2]=1;
    for(int i=2;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            a[i][j]=(a[i-1][j+1]+a[i-1][j])%2;
        }
    }
    for(int i=1;i<=n2;++i){
        for(int j=1;j<=n2;++j){
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}