题解 P5461 【赦免战俘】

· · 题解

一份不太常规操作的题解(￣▽￣)"

它的核心是：杨辉三角递推式

杨辉三角的递推式如下

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int yanghui[2][maxn],n;
int main()
{ 
    scanf("%d",&n);
    memset(yanghui,0,sizeof(yanghui));
    for(int i=1;i<=n;i++)
    {
        int k=i%2;//两个数组循环使用
        yanghui[k][i]=1;
        for(int j=1;j<i;j++)
        yanghui[k][j]=yanghui[!k][j]+yanghui[!k][j-1];

        for(int j=1;j<=i;j++)
        printf("%3d ",yanghui[k][j]);

        printf("\n");
    }
    return 0; 
}

输一个16进去的结果是这样：

   1
   1    1
   1    2    1
   1    3    3    1
   1    4    6    4    1
   1    5   10   10    5    1
   1    6   15   20   15    6    1
   1    7   21   35   35   21    7    1
   1    8   28   56   70   56   28    8    1
   1    9   36   84  126  126   84   36    9    1
   1   10   45  120  210  252  210  120   45   10    1
   1   11   55  165  330  462  462  330  165   55   11    1
   1   12   66  220  495  792  924  792  495  220   66   12    1
   1   13   78  286  715 1287 1716 1716 1287  715  286   78   13    1
   1   14   91  364 1001 2002 3003 3432 3003 2002 1001  364   91   14    1
   1   15  105  455 1365 3003 5005 6435 6435 5005 3003 1365  455  105   15    1

现在我把程序里面的输出函数改一下

改成 如果是奇数就输出1，如果是偶数就输出【空格】 试一试

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int yanghui[2][maxn],n,k;
int main()
{ 
    scanf("%d",&k);
    memset(yanghui,0,sizeof(yanghui));
    for(int i=1;i<=n;i++)
    {
        int k=i%2;
        yanghui[k][i]=1;
        for(int j=1;j<i;j++)
        yanghui[k][j]=yanghui[!k][j]+yanghui[!k][j-1];

        for(int j=1;j<=i;j++)////////只改了这个地方！！！
        if(yanghui[k][j]%2)
        printf("1 ");////////只改了这个地方！！！
        else
        printf("  ");

        printf("\n");
    }
    return 0; 
}

输出的结果是这样子

1
1 1
1   1
1 1 1 1
1       1
1 1     1 1
1   1   1   1
1 1 1 1 1 1 1 1
1               1
1 1             1 1
1   1           1   1
1 1 1 1         1 1 1 1
1       1       1       1
1 1     1 1     1 1     1 1
1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

有没有很惊喜！？

这就是类似于题目所描述的答案！

每个2的次方边长方块都是右上角没有东东

而题目的描述是左上角没有东东

输出前面的空格再打印杨辉三角不就完事了吗233333

所以我们现在只需要在原程序的基础上添加一个输出前置空格的语句

并且将输出换成2^p中的k

就像这样：

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int yanghui[2][maxn],n,p;
int main()
{ 
    scanf("%d",&p);
    n=1<<p;
    memset(yanghui,0,sizeof(yanghui));
    for(int i=1;i<=n;i++)
    {
        for(int j=n-i;j>=1;j--)//这个地方！！！
        printf("  ");

        int k=i%2;
        yanghui[k][i]=1;
        for(int j=1;j<i;j++)
        yanghui[k][j]=yanghui[!k][j]+yanghui[!k][j-1];

        for(int j=1;j<=i;j++)////////只改了这个地方！！！
        if(yanghui[k][j]%2)
        printf("1 ");////////只改了这个地方！！！
        else
        printf("  ");

        printf("\n");
    }
    return 0; 
}

现在我们再输入4进去(2^4==16)，出来的就是想要的形式了！

                              1
                            1 1
                          1   1
                        1 1 1 1
                      1       1
                    1 1     1 1
                  1   1   1   1
                1 1 1 1 1 1 1 1
              1               1
            1 1             1 1
          1   1           1   1
        1 1 1 1         1 1 1 1
      1       1       1       1
    1 1     1 1     1 1     1 1
  1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

再结合一下题意 填充上0！

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int yanghui[2][maxn],n,p;
int main()
{ 
    scanf("%d",&p);
    n=1<<p;
    memset(yanghui,0,sizeof(yanghui));
    for(int i=1;i<=n;i++)
    {
        for(int j=n-i;j>=1;j--)
        printf("0 ");
        int k=i%2;
        yanghui[k][i]=1;
        for(int j=1;j<i;j++)
        yanghui[k][j]=yanghui[!k][j]+yanghui[!k][j-1];

        for(int j=1;j<=i;j++)////////只改了这个地方！！！
        if(yanghui[k][j]%2)
        printf("1 ");////////只改了这个地方！！！
        else
        printf("0 ");

        printf("\n");
    }
    return 0; 
}

输入4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Over！

At the end

这个方法我也是偶然发现的

其实它的关键是利用了二进制相加进位的原理（其实就是mod 2可以实现的原因）

上一排的1+1或者0+0得到下一排的0

上一排的0+1或者1+0得到下一排的1

有点像数字金字塔那道DP入门题

炒鸡快速，O(n)的复杂度，几乎就是【加】+【判断】+【输出】就完了

AC提交

写在最后

---------刷题有感----------

---------BS一夏雪---------

如果有不懂，模拟是王道。

O I 深莫测 ， 抽象为核心。

感觉很玄学，领悟靠内化。

刷题不在多，刷透就能赢。

这个是我的博客，欢迎各位神犇拍砖