当前位置: 首页 > news >正文

P5461 赦免战俘

题目描述

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

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

输入格式

一个整数 n n n

输出格式

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

样例输入

3

样例输出

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

问题分析
2n 就是n个2相乘。比如,21 =2,22 =4,25 =32,210 =1024。
2n 可以被一直除以2进行均分,直到只剩1为止。

长度是2n的一维数组,可以被一直均分成两份,直到只剩一个格子为止。
在这里插入图片描述

2n × 2n 的二维数组(矩阵),可以被一直均分成4份,直到只剩一个格子为止。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如何使用代码将矩阵均分成4份呢?
用(x1,y1)表示左上角的格子,(x2,y2)表示右下角的格子,那么(x1,y1)和(x2,y2)就确定了一个唯一 的矩阵。
如果找到了被均分成的4个小矩阵的左上格子和右下格子,那么4个小矩阵也就被确定了。

令 mx = (x1+x2)/2 , my=(y1+y2)/2,就可以得到如下结果:

  • 左上方的1/4矩阵,左上角的格子是(x1,y1),右下角的格子是( mx, my)。
  • 右上方的1/4矩阵,左上角的格子是(x1,my+1),右下角的格子是( mx, y2)。
  • 左下方的1/4矩阵,左上角的格子是(mx+1,
    y1),右下角的格子是( x2, my)。
  • 右下方的1/4矩阵,左上角的格子是(mx+1, my+1),右下角的格子是( x2, y2)。

C++中,通过位运算 1<<n 可以快速计算出 2n的值。
由于 n≤10 ,所以,数组的行列数可以设置为 (1<<10)+5。

作弊者只有被赦免和不被赦免两种状态,定义成bool类型数组就够了。

将矩阵不断均分的过程可以用递归函数实现。递归结束条件是,矩阵只有1×1大小,这个时候就不能继续均分了。
递归步骤如下:
1、计算出mx,my;
2、将左上矩阵中的值改为true。
3、递归处理右上、左下和右下的矩阵

参考代码

#include<bits/stdc++.h>
using namespace std;
const int M=(1<<10)+5;
bool a[M][M]; //a[i][j]=true表示被赦免,否则表示不被赦免
//(x1,y1)-正方形左上角;(x2,y2)-正方形右下角
void dfs(int x1,int y1,int x2,int y2) {//当(x1,y1)和(x2,y2)指向同一个格子时,不能再分。if(x1==x2&&y1==y2) return;//否则,继续将正方形均分成4个更小的正方形//计算左上正方形的左下角方格下标int mx=(x1+x2)/2,my=(y1+y2)/2;  //左上角的赦免for(int i=x1; i<=mx; i++)for(int j=y1; j<=my; j++)a[i][j]=true;//递归处理其他3个小矩阵dfs(x1,my+1,mx,y2); //右上dfs(mx+1,y1,x2,my); //左下 dfs(mx+1,my+1,x2,y2); //右下 
}
int main() {int n;cin>>n;n=1<<n;dfs(1,1,n,n);//按要求输出:0 代表被赦免,1 代表不被赦免。for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++)printf("%d ",!a[i][j]);printf("\n");}return 0;
}

相关文章:

P5461 赦免战俘

题目描述 现有 2 n 2 n ( n ≤ 10 ) 2^n\times 2^n (n\le10) 2n2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵&#xff0c;每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵…...

【工具】转码silk格式为mp3

【工具】转码slk格式为mp3 前提 安装 ffmpeg 【安装】Linux安装ffmpeg_linux安装ffmpeg4.4_我是Superman丶的博客-CSDN博客 GitHub - kn007/silk-v3-decoder: [Skype Silk Codec SDK]Decode silk v3 audio files (like wechat amr, aud files, qq slk files) and convert to o…...

蓝桥杯每日一题2023.10.18

题目描述 特别数的和 - 蓝桥云课 (lanqiao.cn) 题目分析 简单枚举每一个可行的数 #include<bits/stdc.h> using namespace std; int flag, ans; int main() {int n;cin >> n;for(int i 1; i < n; i ){flag 0;int x i;while(x){int y x % 10;if(y 2 || y…...

大数据开发中的秘密武器:探索Hadoop纠删码的奇妙世界

随着大数据技术的发展&#xff0c;HDFS作为Hadoop的核心模块之一得到了广泛的应用。为了系统的可靠性&#xff0c;HDFS通过复制来实现这种机制。但在HDFS中每一份数据都有两个副本&#xff0c;这也使得存储利用率仅为1/3&#xff0c;每TB数据都需要占用3TB的存储空间。因此&…...

华为数通方向HCIP-DataCom H12-831题库(单选题:301-310)

第301题 关于配置防火墙安全区域的安全级别的描述,错误的是 A、同一系统中,两个安全区域不允许配置相同的安全级别 B、只能为自定义的安全区域设定安全级别 C、安全级别一旦设定不允许更改 D、新建的安全区域,系统默认其安全级别为1 答案:D 解析: 新创建的安全区域缺省未…...

Vite 踩坑 —— require is not defined

动态require引入图片报错 require 是属于 Webpack 的方法&#xff0c;而我使用的是 Vite&#xff0c;所以我们需要去寻找 Vite 静态资源处理的方法 所以&#xff0c;我们只需要将代码改写以下形式即可。 ​ template <CarouselItem v-for"(item,index) of carous…...

彻底理解操作系统与内核的区别!

通用底盘技术 Canoo公司有一项核心技术专利&#xff0c;这就是它们的通用电动底盘技术&#xff0c;长得是这个样子&#xff0c;非常像一个滑板&#xff1a; 这个带轮子、有电池、能动的滑板已经包含了一辆车最核心的组件&#xff0c;差的就是一个外壳。这个看起来像滑板的东西…...

微信小程序4

一自定义组件应用 1.介绍 微信小程序自定义组件是指开发者可以自定义组件&#xff0c;将一些常用的 UI 元素封装成一个自定义组件&#xff0c;然后在多个页面中复用该组件&#xff0c;实现代码复用和页面性能优化的效果。 2.自定义组件分为两种类型 组件模板类型&#xff1a;…...

OpenCV14-图像平滑:线性滤波和非线性滤波

OpenCV14-图像平滑&#xff1a;线性滤波和非线性滤波 1.图像滤波2.线性滤波2.1均值滤波2.2方框滤波2.3高斯滤波2.4可分离滤波 3.非线性滤波3.1中值滤波3.2双边滤波 1.图像滤波 图像滤波是指去除图像中不重要的内容&#xff0c;而使关心的内容表现得更加清晰的方法&#xff0c;…...

kafka_2.10启动Kafka broker

要启动 Kafka broker&#xff0c;你需要执行以下步骤&#xff1a; 首先&#xff0c;确保你已经安装了 Kafka。你可以从 Apache Kafka 的官方网站下载 Kafka 的二进制发行版&#xff0c;并按照官方文档中的说明进行安装。 在安装完成后&#xff0c;进入 Kafka 的安装目录。 打…...

【配置环境】SQLite数据库安装和编译以及VS下C++访问SQLite数据库

一&#xff0c;环境 Windows 11 家庭中文版&#xff0c;64 位操作系统, 基于 x64 的处理器SQLite - 3.43.2Microsoft Visual Studio Community 2022 (64 位) - Current 版本 17.5.3 二&#xff0c;SQLite简介 简要介绍 SQLite&#xff08;Structured Query Language for Lite&a…...

Confluence 自定义展示页面

1. 概述 Confluence 作为知识库可通过JS脚本方式&#xff0c;根据登录用户或用户组进行前端页面的自定义 2. 实现方式 Confluence →管理→自定义HTML 嵌入对应JS脚本&#xff0c;示例如下 <script type"text/javascript">jQuery(#footer).html(<div>…...

使用C#的Socket从头实现的带有文件上传和下载功能的HTTP服务器

使用C#和Socket从头实现的带有文件上传和下载功能的HTTP服务器。它支持GET、POST请求方法&#xff0c;并能处理URL参数、请求体以及文件上传和下载。 using System; using System.IO; using System.Net; using System.Net.Sockets; using System.Text;class HttpServer {publi…...

【OSPF Loading、FULL状态与display ospf peer brief命令、OSPF的数据库讲解】

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大二在校生&#xff0c;喜欢编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️ 零基…...

除氟树脂在工业、市政含氟废水处理中的应用

含氟废水的不达标排放对自然环境有很大的危害&#xff0c;氟化物离子可以累积在土壤和水体中&#xff0c;从而对生态系统造成破坏。大量的氟化物离子会对植物生长产生不良影响&#xff0c;并对水生生物造成毒性作用&#xff0c;严重时还可能导致生态灾难。氟化物离子如果没有得…...

模拟地和数字地的区别

模拟地和数字地的主要区别体现在设计目的、处理技术、数据类型和数据精度四个方面。 设计目的&#xff1a;模拟地的主要设计目的是分析时空数据、进行模型和预测&#xff0c;它主要关注动态变化和过程。而数字地的主要设计目的是数据的存储、管理、查询和分析&#xff0c;在地…...

Druid连接池最小连接数设置失效问题

问题发现&#xff1a; 配置 当项目启动后 线程池确实是初始化了5条连接&#xff0c;但是当项目运行一段时间后&#xff0c;5条连接确消失了&#xff0c;只会程序用到得时候&#xff0c;再去初始化连接&#xff0c;这样有点违背了参数设置得意义&#xff0c;后来通过查阅资料发…...

Javascript数据类型和类型转换

Javascript数据类型和类型转换 在JavaScript中&#xff0c;理解数据类型&#xff0c;如何区分它们&#xff0c;以及它们如何被转换是至关重要的。在这篇文章中&#xff0c;我们将探讨这些主题&#xff0c;以帮助巩固你的JavaScript基础。 基础数据类型和引用数据类型 当涉及…...

冲刺十五届蓝桥杯P0005单词分析

文章目录 题目分析代码 题目 单词分析 分析 统计字符串中字母出现的次数&#xff0c;可以采用哈希表&#xff0c;代码采用的是数组来存储字符&#xff0c;将字符-97&#xff0c;得到对应的数组下标&#xff0c;将对应下标的数组&#xff1b;找到数组元素最大的下标&#xff…...

php获取10年内的年份并加入下拉列表

要实现的效果 在html中内嵌php循环将数组中的年份加入下拉列表 <div class="form-group"><label>年份:</label><div class="input-group"><div class="input-group-prepend"><span class="input-group-te…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...