热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

98.分形之城

原题链接:98.分形之城解题思路递归+分治+数学坐标系公式+找规律递归+分治好理解,因为这个题目中最显著的特点就是,不断地重复旋转复制,也就是N级城市,可以由4个N−1级城市构造,

原题链接:98. 分形之城




解题思路

递归+分治+数学坐标系公式+找规律

递归+分治好理解,因为这个题目中最显著的特点就是,不断地重复旋转复制,也就是N级城市,可以由4个N−1级城市构造,因此我们每次可以不断地分形N−1级,将问题范围不断地缩小即可

这道题目的数学坐标公式,其实一共有两个,一个是高中的数学函数,旋转,这是一个难点,其实可以通过找规律,求解,第二公式则是欧几里得距离公式。√(x1−x2)2−(y1−y2)2

最难的就是如何旋转这个正方形 找规律

总的来说这道题目数学知识较多,考察画图能力,解法自然,数据毒瘤,相信可以给你的NOIP一个有利的一脚。

1.左上角:我们可以发现,左上角的N−1级矩阵其实就是等级为N−1,也就是上一个矩阵,顺时针旋转90°,那么既然如此的话,我们就可以综合yxc老师上课所讲的公式(补充:也就是旋转矩阵,属于大学的线性代数内容),得出转移后的矩阵中的一点坐标从(x,y)变为(y,x)

2.左下角:同左上角,它则是逆时针旋转90°而且还要水平翻转,也即是沿着X轴对称,原本逆时针后为(y,−x),然后要对称,x坐标不变,y坐标取反,所以坐标为(−y,−x) 也就是所谓的(2×len−1−y,len−1−x) 最难理解的坐标,具体可以画图理解

3.右上角和右下角:通过N=2级图发现,其实和N=1是一样的,并没有旋转,只是平移,则右上角坐标为(x,y+len),右下角坐标为(x+len,y+len)

总的来说以上四种转移,都可以通过画图理解

4.还有本题数据毒瘤,四舍五入最好是double类型,而且整数类型一定要是long long,否则容易WA!

5.易错点:公式使用,double型浮点数精度问题,输出格式化问题。


样例代码

#include
using namespace std;
#define ll long long
#define PLL pair
PLL calc(ll n,ll m)
{
if (n==0)
return make_pair(0,0);
ll len=1LL<<(n-1),cnt=1LL<<(2*n-2);
PLL pos=calc(n-1,m%cnt);
ll x=pos.first,y=pos.second;
ll z=m/cnt;
if (z==0)
return make_pair(y,x);
if (z==1)
return make_pair(x,y+len);
if (z==2)
return make_pair(x+len,y+len);
return make_pair(2*len-1-y,len-1-x);
}
int main()
{
//ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll n,a,b;
cin>>n>>a>>b;
PLL x=calc(n,a-1);
PLL y=calc(n,b-1);
ll dx=x.first-y.first,dy=x.second-y.second;
double ans=(sqrt(dx*dx+dy*dy)*10);
printf("%0.lf\n",ans);
}
return 0;
}


推荐阅读
  • 洛谷 P4009 汽车加油行驶问题 解析
    探讨了经典算法题目——汽车加油行驶问题,通过网络流和费用流的视角,深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题,并提供详细的代码实现。 ... [详细]
  • 本文基于Java官方文档进行了适当修改,旨在介绍如何实现一个能够同时处理多个客户端请求的服务端程序。在前文中,我们探讨了单客户端访问的服务端实现,而本篇将深入讲解多客户端环境下的服务端设计与实现。 ... [详细]
  • 视觉Transformer综述
    本文综述了视觉Transformer在计算机视觉领域的应用,从原始Transformer出发,详细介绍了其在图像分类、目标检测和图像分割等任务中的最新进展。文章不仅涵盖了基础的Transformer架构,还深入探讨了各类增强版Transformer模型的设计思路和技术细节。 ... [详细]
  • 想把一组chara[4096]的数组拷贝到shortb[6][256]中,尝试过用循环移位的方式,还用中间变量shortc[2048]的方式。得出的结论:1.移位方式效率最低2. ... [详细]
  • 本文探讨了使用普通生成函数和指数生成函数解决组合与排列问题的方法,特别是在处理特定路径计数问题时的应用。文章通过详细分析和代码实现,展示了如何高效地计算在给定条件下不相邻相同元素的排列数量。 ... [详细]
  • OpenCV中的霍夫圆检测技术解析
    本文详细介绍了如何使用OpenCV库中的HoughCircles函数实现霍夫圆检测,并提供了具体的代码示例及参数解释。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • hlg_oj_1116_选美大赛这题是最长子序列,然后再求出路径就可以了。开始写的比较乱,用数组什么的,后来用了指针就好办了。现在把代码贴 ... [详细]
  • 本文详细介绍了Linux系统中信号量的相关函数,包括sem_init、sem_wait、sem_post和sem_destroy,解释了它们的功能和使用方法,并提供了示例代码。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本文将深入探讨C语言中的位操作符——按位与(&)、按位或(|)和按位异或(^),通过具体示例解释这些操作符如何在位级别上对数据进行操作。 ... [详细]
  • 本文详细介绍了在Windows系统中如何配置Nginx以实现高效的缓存加速功能,包括关键的配置文件设置和示例代码。 ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 本问题涉及在给定的无向图中寻找一个至少包含三个节点的环,该环上的节点不重复,并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]
author-avatar
手机用户2602891927
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有