题解 P5461 【赦免战俘】

· · 题解

发的第一篇题解还在审核中，
缺乏发题解的经验，如有错误或交代不清请各位见谅

谢谢

当时同机房的大佬十分钟就A了这道题，而我A了一个多小时（水平不足）

刚开始看的时候马上就想到了递归和分治（然而我不会）
然后懵逼了半小时

我竟然还想过要打表（傻子）

后来想起了我做过的一道类似的题（当时我那道题全机房最高分，甩大佬们80分）跑题了

接下来说正事

做题的时候不难发现把正方形分成四份后，左下，右上，右下三部分完全相等，而左上部分全是0，可以留到后期处理

做完看题解时没发现一个用字符串的，所以我这里用字符串（ string ）来解

头文件#include<string>里有一个本题特别重要的函数—— insert() 函数（不懂自己去查）

核心思想（方法）：求下一个方阵的情况，逐行逐行的将当前方阵情况插入下方（在下面复制两次），最后再补0

话不多说，看代码：

（30行代码） 

#include<cstdio>
#include<string>                                                      //字符串解法 
#include<iostream>
using namespace std;
long n;
string a[1025];                                                       //记录方阵情况 
long A[15]={1,2,4,8,16,32,64,128,256,512,1024};                       //A[i]为**2的i次方** 
int main(){
    scanf("%ld",&n);
    if(n==0)
    printf("1");                                                  //2^0=1,只有一个人，**无法再分，不赦免** 
    else
    if(n==1)
    printf("0 1\n1 1");                                           //小打表 
    else{
        a[0]="01";                                            //第一行情况 
        a[1]="11";                                            //第二行情况 
        for(long I=2;I<=n;I++){                               //现在是第几个方阵（即求输入I的输出结果）（**分治思想**） 
        for(long i=A[I-1];i<A[I];i++){                        //新增行的行号（是第几行）
            a[i].insert(a[i].length(),a[i-A[I-1]]);       //在新一行尾部插入
            a[i].insert(a[i].length(),a[i-A[I-1]]);           //**插入两次** 
        }
        for(long i=0;i<A[I-1];i++)                            //在头几行最前面插入A[I-1]个0（应该不需要解释了吧） 
        for(long j=0;j<A[I-1];j++)                            //字符串**存储时不带空格，输出才带空格** 
            a[i].insert(0,"0");
        }
        for(long i=0;i<A[n];i++){                                 //输出结果，**加空格**
        for(long j=0;j<A[n];j++)
            printf("%c ",a[i][j]);
            printf("\n");
        }
    }
    return 0;
}

如果你认为有帮助的话请为我点个赞

谢谢