赦免战俘

朱雀 2022-12-12 02:19 68阅读 0赞

### 题目描述 ###

现有 2n×2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。  
给出 n，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

#### 输入格式 ####

一个整数 n。

#### 输出格式 ####

2n×2n 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。

##### 输入输出样例 #####

输入

输出

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

//找规律+模拟
    //每一个数字是上方数字与右上方数字之和模2
    //可以直接异或 
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int n;
    int a[1234][1234];
    int main()
    { 
        scanf("%d",&n);
        n=(1<<n);
        a[0][n+1]=1;
        for(int i=1;i<=n;++i)
        { 
      	for(int j=1;j<=n;++j)
      	{ 
                a[i][j]=a[i-1][j]^a[i-1][j+1];
                printf("%d ",a[i][j]);
      	}
      	printf("\n");
        }
        return 0;
    }

或

//位运算：f(i,j)=((i|j)!=((1<<n)-1)?0:1);
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int main()
    { 
        scanf("%d",&n);
        for(int i=0;i<(1<<n);i++)
        { 
      	for(int j=0;j<(1<<n);j++)
      	{ 
                printf("%d ",(i|j)!=((1<<n)-1)?0:1);
      	}
      	printf("\n");
        }
        return 0;
    }

或

//分治+递归
    #include<bits/stdc++.h>
    using namespace std;
    int n,p=1,a[1050][1050];
    void di(int x,int l,int q) //x为正方形边长，l,q分别为递归正方形的横纵坐标 
    { 
        if(x==2)
        { 
      	a[l][q]=0;
      	return;
        } 
        for(int i=l;i<=l+x/2-1;i++)
        { 
      	for(int j=q;j<=q+x/2-1;j++)
      	{ 
                a[i][j]=0;
            }
        }
        di(x/2,l+x/2,q);
        di(x/2,l+x/2,q+x/2);
        di(x/2,l,q+x/2);
    } 
    int main()
    { 
        cin>>n;
        p=pow(2,n);
        for(int i=1;i<=p;i++)
        { 
      	for(int j=1;j<=p;j++)
      	{ 
                a[i][j]=1;
      	}
        }
        di(p,1,1);
        for(int i=1; i<=p; i++)
        { 
      	for(int j=1; j<=p-1; j++)//避免输出行尾空格
         	{ 
                cout<<a[i][j]<<" ";
      	}
      	cout<<a[i][p]<<endl; 
        }
        return 0;
    }

或

//打表 
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int a[12][1025][1025];
    int main()
    { 
        a[1][1][1]=0;
        a[1][1][2]=1;
        a[1][2][1]=1;
        a[1][2][2]=1;
        for(int k=2;k<=10;k++)
        { 
      	int q=pow(2,k);
      	for(int i=1;i<=q/2;i++)
      	{ 
                for(int j=1;j<=q/2;j++)
                { 
        		a[k][i][j]=0;
                }
      	}
      	for(int i=1;i<=q/2;i++)
     	{ 
                for(int j=q/2+1;j<=q;j++)
                { 
        		a[k][i][j]=a[k-1][i][j-q/2];
                }
      	}
      	for(int i=q/2+1;i<=q;i++)
      	{ 
                for(int j=1;j<=q;j++)
                { 
         		if(j%(q/2))
         		{  
                        a[k][i][j]=a[k-1][i-q/2][j%(q/2)];
        		} 
        		else a[k][i][j]=a[k-1][i-q/2][q/2];
       	    }
      	}
        }
        int n;
        scanf("%d",&n);
        int p=pow(2,n);
        for(int i=1;i<=p;i++)
        { 
      	for(int j=1;j<=p;j++)
      	{ 
                printf("%d ",a[n][i][j]);
      	}
      	printf("\n");
        }
        return 0;
    }

或

赦免战俘

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关赦免战俘

相关【洛谷入门6】函数与结构体 P5461 赦免战俘