洛谷题单指南-递推与递归-P1228 地毯填补问题

news/发布时间2024/6/17 22:20:18

原题链接:https://www.luogu.com.cn/problem/P1228

题意解读:用4种毯子铺满2^k * 2^k的区域,留出一个公主位置,输出所有毯子拐角的坐标以及哪种毯子,看起来有点无从下手,

可以从k=1,k=2,k=3入手去依次考虑,找到规律,用分治法解决。

解题思路:

1、当k=1时,即2*2的区域,对于任意一个位置是公主,都可以得到唯一一种铺设方案

2、当k=2时,即4*4的区域,对于任意一个位置是公主,如下图:

可以将4*4区域划分成4个2*2的区域

如果每个区域都有一个公主,问题就好解决了,因为右上区域有了公主,可以假设最中间的2*2区域的右上角有公主,先对这个区域进行铺设:

然后,把中间铺设的地毯都当做公主,这样就能保证4个2*2的区域都有了公主:

再分4个区域依次进行处理,问题就变成了k=1时的情况,即可得到上图的结果。

3、同理,当k=3时,即8*8的区域,对于任意位置是公主,如下图:

将8*8区域划分成4个4*4区域

根据公主所在的区域,对中间2*2区域进行铺设

这样,假设中间2*2铺设的毯子都是公主,则4个4*4区域就都有了公主

再依次对4个4*4区域进行处理,问题就变成了k=2时的情况,最终可以变成k=1时的情况,问题得解。

100分代码:

#include <bits/stdc++.h>
using namespace std;int k, x, y;//cover是铺地毯函数,(x1,y1)是左上角的坐标,(x2,y2)是右下角的坐标,(x,y)是公主的的坐标
void cover(int x1, int y1, int x2, int y2, int x, int y)
{if(x2 - x1 == 1) //2 * 2区域时{ //公主在左上角,用毯子1if(x1 == x && y1 == y) cout << x2 << " " << y2 << " " << 1 << endl; //公主在右上角,用毯子2else if(x1 == x && y2 == y) cout << x2 << " " << y1 << " " << 2 << endl;//公主在左下角,用毯子3else if(x2 == x && y1 == y) cout << x1 << " " << y2 << " " << 3 << endl;//公主在右下角,用毯子4else cout << x1 << " " << y1 << " " << 4 << endl;return;}//将2^k * 2^k区域分成4个2^(k-1) * 2^(k-1)的区域//计算公主在哪个区域,把正中间的2*2区域用一个地毯覆盖,这个地毯相当于让4个2^(k-1) * 2^(k-1)的区域都有一个公主//再递归处理int len = x2 - x1 + 1; //len是边长int half = len / 2; //half是边长的一半//中间2 * 2区域每个格子的坐标int xa = x1 + half - 1, ya = y1 + half - 1; //左上int xb = x1 + half - 1, yb = y1 + half; //右上int xc = x1 + half, yc = y1 + half - 1; //左下int xd = x1 + half, yd = y1 + half; //右下//公主在左上区域if(x >= x1 && x <= xa && y >= y1 && y <= ya) {//填补正中间2*2区域cover(xa, ya, xd, yd, xa, ya);//设定左上区域的公主位置xa = x, ya = y;}//公主在右上区域else if(x >= x1 && x <= xb && y >= yb && y <= y2){//填补正中间2*2区域cover(xa, ya, xd, yd, xb, yb);//设定右上区域的公主位置xb = x, yb = y;}//公主在左下区域else if(x >= xc && x <= x2 && y >= y1 && y <= yc){//填补正中间2*2区域cover(xa, ya, xd, yd, xc, yc);//设定左下区域的公主位置xc = x, yc = y;}//公主在右下区域else {//填补正中间2*2区域cover(xa, ya, xd, yd, xd, yd);//设定右下区域的公主位置xd = x, yd = y;}//递归处理4个2^(k-1) * 2^(k-1)的区域cover(x1, y1, x1 + half - 1, y1 + half - 1, xa, ya); //左上cover(x1, y1 + half, x1 + half - 1, y2, xb, yb);  //右上cover(x1 + half, y1, x2, y1 + half - 1, xc, yc);  //左下cover(x1 + half, y1 + half, x2, y2, xd, yd); //右下
}int main()
{cin >> k >> x >> y;cover(1, 1, 1 << k, 1 << k, x, y);return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.jwkm.cn/p/62587230.html

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

如何杜绝员工在工作中的不当行为导致数据泄露?

在数据驱动的现代企业中,内部员工是数据安全防护的重要一环。员工的不当行为可能导致重大的数据泄露,引发严重的商业损失和声誉损害。因此,杜绝员工在工作中的不当行为变得至关重要。这篇文章将解析如何利用华企盾DSC数据防泄密系统,防止和减轻由员工不当行为带来的数据泄露…

IO

IOJava IO 也称为IO流,IO = 流,它的核心就是对文件的操作,对于 字节 、字符类型的输入和输出流。IO是指对数据流的输入和输出,也称为IO流,IO流主要分为两大类,字节流和字符流。字节流可以处理任何类型的数据,如图片,视频等,字符流只能处理字符类型的数据。1.IO流的分类…

全流程点云机器学习(二)使用PaddlePaddle进行PointNet的机器学习训练和评估

前言 这不是高支模项目需要嘛,他们用传统算法切那个横杆竖杆流程复杂耗时很长,所以想能不能用机器学习完成这些工作,所以我就来整这个工作了。 基于上文的数据集切分 ,现在来对切分好的数据来进行正式的训练。 本系列文章所用的核心骨干网络代码主要来自点云处理:实现Poin…

Unity中关于刚体和碰撞器遇到的告警

告警信息: Script error: OnCollisionEnter2DThis message parameter has to be of type: Collision2DThe message will be ignored. 解决: 经查验发现,由于该脚本是粘贴的类似功能脚本,而粘贴前使用的触发器,因此方法为 private void OnTriggerStay2D(Collider2D collis…

Windows bat批处理+PowerShell获取文件日期 和 时分秒

前言全局说明Windows bat批处理+PowerShell获取文件秒一、说明二、分开获取 日期 和 时分秒 获取bat文件自身的日期时间 和 时分秒 1.源码 文件名:get-file-second.bat @echo off chcp 65001>nul echo. echo. set bak_file=get-file-second.bat:: 获取文件修改时间 setloca…

九州云仓-强制退出移动终端

九州云仓-强制退出移动终端 ​​ ​​ ​​ ​​