题解：P5461 赦免战俘

思路：

在做这道题之前，建议大家去做一下 P5732杨辉三角，为什么这样说呢？因为这道题其实有一个递推解，和杨辉三角极为相似。我们把整个方阵看作一个二维数组

a

，并将

a

数组归零，将方阵第一项设为

a[1][1]

，从而防止数组越位。这样可以发现

a[i][j]

的值便等于

a[i-1][j+1]

的值加上

a[i-1][j]

的值除以

2

的余数。接着，我们将

a[1][1]

的值为

0

，再定义

n2

表示方阵的边长，于是就这样写下了代码。

CPP

#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

的话，这个问题不就解决了吗？

CPP

#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

开始。

代码：

CPP

#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;
}

题解：P5461 赦免战俘

文章操作

思路：

代码：

相关推荐

评论

题解：P5461 赦免战俘