赦免战俘
题目背景
借助反作弊系统,一些在月赛有抄袭作弊行为的选手被抓出来了!
题目描述
现有 \(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分别代表二维数组的行和列。
- 通过位运算,( i | j )+ 1 == (1 << n) 时,元素的值为 1,其余值为 0。
- 通过递推,从第二行算起,每一个元素值为其 正上方 加上 右上方 的值 对 2 取模,如果数组用以为数组表示,则为(nums[i] = nums[i] + nums[i + 1])%2。这样表示是因为先输出了nums[i] 的值,再更新其值作为下一行的值。
位运算代码实现
#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