首页 > 其他分享 >P5461 赦免战俘

P5461 赦免战俘

时间:2024-04-07 17:34:31浏览次数:18  
标签:std P5461 nums int 矩阵 战俘 作弊者 赦免

赦免战俘

题目背景

借助反作弊系统,一些在月赛有抄袭作弊行为的选手被抓出来了!

题目描述

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

给出 \(n\),请输出每名作弊者的命运,其中 0 代表被赦免,1 代表不被赦免。

输入格式

一个整数 \(n\)。

输出格式

\(2^n \times 2^n\) 的 01 矩阵,代表每个人是否被赦免。数字之间有一个空格。

样例 #1

样例输入 #1

3

样例输出 #1

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^n\times 2^n (n\le10)\) 的二维数组,将其全部初始化为 1 ,然后将其分为 4 个小部分 。先解决左上角,全部赋值为零,再对余下三个部分进行递归处理。

代码实现


//  
// Created by G3429 on 2024/4/6.  
//  
#include <iostream>  
#include <vector>  
#include <cmath>  
  
void fuc(int l, int r, int u, int d, std::vector<std::vector<int>> &nums) {  
	/* 当数组为一个元素时返回 */
    if (l == r) {  
        return;  
    }  
    for (int i = l; i < (r + l) / 2 + 1; i++) {  
        for (int j = u; j < (d + u) / 2 + 1; j++) {  
            nums[i][j] = 0;  
        }    
    }  
    /* 左上 */
    //    fuc(l, (r + l) / 2, u, (d + u) / 2, nums);  
  
    /* 右上 */    
    fuc((r + l) / 2 + 1, r, u, (d + u) / 2, nums);  
  
    /* 左下 */    
    fuc(l, (r + l) / 2, (d + u) / 2 + 1, d, nums);  
    
    /* 右下 */    
    fuc((r + l) / 2 + 1, r, (d + u) / 2 + 1, d, nums);  
}  
  
int main() {  
    int n;  
    std::cin >> n;  
  
    int x = (int) pow(2, n);  
    std::vector<std::vector<int>> nums(x, std::vector<int>(x, 1));  
  
    fuc(0, x - 1, 0, x - 1, nums);  
    for (auto i: nums) {  
        for (auto j: i) {  
            std::cout << j << ' ';  
        }        
        std::cout << std::endl;  
    }    
    return 0;  
}

找规律

  这道题可以找规律来解决,观看一下图片,会发现两个规律,设 i,j分别代表二维数组的行和列。

  1. 通过位运算,( i | j )+ 1 == (1 << n) 时,元素的值为 1,其余值为 0。
  2. 通过递推,从第二行算起,每一个元素值为其 正上方 加上 右上方 的值 对 2 取模,如果数组用以为数组表示,则为(nums[i] = nums[i] + nums[i + 1])%2。这样表示是因为先输出了nums[i] 的值,再更新其值作为下一行的值。

image

位运算代码实现

  
#include<iostream>  
  
using namespace std;  
int n;  
  
int main() {  
    cin >> n;  
    for (int i = 0; i < (1 << n); i++) {  
        for (int j = 0; j < (1 << n); j++) {  
            /* 三目运算符进行判断输出相应值 */            
            cout << ((i | j) + 1 != (1 << n) ? 0 : 1) << ' ';  
        }        
        cout << endl;  
    }    
    return 0;  
}


递推代码实现


#include <iostream>  
#include <vector>  
  
int main() {  
    int n;  
    std::cin >> n;  
  
    std::vector<int> nums((1 << n) + 1, 0);  
    nums[(1 << n) - 1] = 1;  
  
    for (int j = 0; j < (1 << n); j++) {  
        for (int i = 0; i < (1 << n); i++) {  
            //输出
            std::cout << nums[i] << ' ';  
            //为下一行输出更新值
            nums[i] = (nums[i] + nums[i + 1]) % 2;  
        } 
        //换行       
        std::cout << std::endl;  
    }    
    return 0;  
}

标签:std,P5461,nums,int,矩阵,战俘,作弊者,赦免
From: https://www.cnblogs.com/import-this05/p/18119523

相关文章

  • P5461【黄】-递归
    简单的很,十分钟不到就切掉了,做这道黄题是因为今天写累了不想写代码了,就最后做一道简单的。看来黄题对我而言基本就是“一半能切一半想一会之后能切”,除非题目是思维题 1#include<iostream>2#include<cstring>3#include<string>4#include<cstdio>5#include......
  • P5461 赦免战俘
    1.题目介绍赦免战俘题目背景借助反作弊系统,一些在月赛有抄袭作弊行为的选手被抓出来了!题目描述现有\(2^n\times2^n(n\le10)\)名作弊者站成一个正方形方阵等候kkksc03的发落。kkksc03决定赦免一些作弊者。他将正方形矩阵均分为4个更小的正方形矩阵,每个更小的矩阵的边......