热门标签 | 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;
}


推荐阅读
  • 具备括号和分数功能的高级四则运算计算器
    本研究基于C语言开发了一款支持括号和分数运算的高级四则运算计算器。该计算器通过模拟手算过程,对每个运算符进行优先级标记,并按优先级从高到低依次执行计算。其中,加减运算的优先级最低,为0。此外,该计算器还支持复杂的分数运算,能够处理包含括号的表达式,提高了计算的准确性和灵活性。 ... [详细]
  • 解题心得:UVA1339(逻辑分析与字符串处理+排序算法)
    解题心得:UVA1339(逻辑分析与字符串处理+排序算法) ... [详细]
  • 题目链接:https://www.luogu.com.cn/problem/P6453在解决 COCI 2008-2009 第四轮 PERIODNI 问题时,我们需要逐行分析。由于一行中的字符若被断开则不再视为同一行,因此每行的最大矩形区域需要单独计算。通过这种方法,可以确保每层都能找到其最大连续子矩形,从而有效解决问题。 ... [详细]
  • 在 Linux 环境下,多线程编程是实现高效并发处理的重要技术。本文通过具体的实战案例,详细分析了多线程编程的关键技术和常见问题。文章首先介绍了多线程的基本概念和创建方法,然后通过实例代码展示了如何使用 pthreads 库进行线程同步和通信。此外,还探讨了多线程程序中的性能优化技巧和调试方法,为开发者提供了宝贵的实践经验。 ... [详细]
  • 在Linux系统中,通过使用`read`和`write`函数可以实现文件的高效复制操作。`open`函数用于打开或创建文件,其返回值为文件描述符,成功时返回一个有效的文件描述符,失败时返回-1。`path`参数指定了要操作的文件路径,而`oflag`参数则定义了文件的打开模式和属性。此外,为了确保数据的完整性和一致性,还需要合理处理文件读取和写入过程中的错误和异常情况。 ... [详细]
  • 本文深入探讨了佩尔方程 \( x^2 - dy^2 = 1 \) 的递推关系式。通过构造特定的矩阵并利用矩阵快速幂的方法,可以高效地计算出该方程的第 k 组解。此外,文章还详细分析了递推关系式的数学背景及其在数论中的应用,为相关研究提供了坚实的理论基础。 ... [详细]
  • Codeforces 605C:Freelancer's Dreams —— 凸包算法解析与题解分析 ... [详细]
  • 题目链接: Caninepoetry问题概述:给定一个仅包含小写字母的字符串,允许将任意位置的字符修改为任意其他小写字母。目标是通过最少次数的修改,使字符串中所有长度大于1的子串均满足特定条件。本文详细分析了该问题,并运用思维与贪心算法,提出了一种高效解决方案。通过对字符串的深入解析,我们探讨了如何在最小化修改次数的同时,确保所有子串符合要求。 ... [详细]
  • 在探讨P1923问题时,我们发现手写的快速排序在最后两个测试用例中出现了超时现象,这在意料之中,因为该题目实际上要求的是时间复杂度为O(n)的算法。进一步研究题解后,发现有选手使用STL中的`nth_element`函数成功通过了所有测试点。本文将详细分析这一现象,并提出相应的优化策略。 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • UVa815问题“洪水来袭!”涉及洪水模拟和应对策略。在解决该问题时,需要通过直接模拟来处理洪水扩散过程,并特别关注临界情况的处理。代码实现中应包括必要的头文件,并使用标准命名空间以简化编程。此外,建议在算法设计中加入对边界条件和特殊情况的详细检查,以确保解决方案的鲁棒性和准确性。 ... [详细]
  • 本文探讨了在硬币找零问题中使用枚举法的具体应用。具体而言,题目要求将一定数额的零钱换成5分、2分和1分的硬币,并且每种硬币至少需要使用一枚。研究旨在找出所有可能的换法组合。输入数据为一行,包含一个在8到100之间的整数,表示待换的零钱数额。通过详细的枚举分析,本文提供了高效的解决方案,并验证了其在实际应用中的可行性和有效性。 ... [详细]
  • 图论入门基础教程
    图论是计算机科学和数学中的重要分支,本教程旨在为初学者提供全面的基础知识。通过实例解析,如“昂贵的聘礼”问题,讲述了一个年轻探险家在印第安部落与酋长女儿的爱情故事,展示了图论在解决实际问题中的应用。教程内容涵盖了图的基本概念、表示方法以及常见算法,适合各类读者学习。 ... [详细]
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • Android中将独立SO库封装进JAR包并实现SO库的加载与调用
    在Android开发中,将独立的SO库封装进JAR包并实现其加载与调用是一个常见的需求。本文详细介绍了如何将SO库嵌入到JAR包中,并确保在外部应用调用该JAR包时能够正确加载和使用这些SO库。通过这种方式,开发者可以更方便地管理和分发包含原生代码的库文件,提高开发效率和代码复用性。文章还探讨了常见的问题及其解决方案,帮助开发者避免在实际应用中遇到的坑。 ... [详细]
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社区 版权所有