AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 98. 分形之城    原题链接    困难

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-20 08:13:42 ,  所有人可见 ,  阅读 7311


33


9

题目描述

城市的规划在城市建设中是个大问题。

不幸的是,很多城市在开始建设的时候并没有很好的规划,城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案,如下图所示:

city.png

当城区规模扩大之后,Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围,提升城市的等级。

对于任意等级的城市,我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂,Fractal 规划部门的人员还是想知道,如果城市发展到了等级 N,编号为 A 和 B 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离,每个街区都是边长为 10 米的正方形。

输入格式
第一行输入正整数n,表示测试数据的数目。

以下n行,输入n组测试数据,每组一行。

每组数据包括三个整数 N,A,B, 表示城市等级以及两个街区的编号,整数之间用空格隔开。

输出格式
一共输出n行数据,每行对应一组测试数据的输出结果,结果四舍五入到整数。

数据范围
$ 1≤N≤31 $
$ 1≤A,B≤2^{2N} $
$ 1≤n≤1000 $
输入样例:

3 
1 1 2 
2 16 1 
3 4 33 

输出样例:

10 
30 
50 

递归+分治+数学坐标系公式+找规律
  1. 递归+分治好理解,因为这个题目中最显著的特点就是,不断地重复旋转复制,也就是$N$级城市,可以由$4$个$N-1$级城市构造,因此我们每次可以不断地分形$N-1$级,将问题范围不断地缩小即可
  2. 这道题目的数学坐标公式,其实一共有两个,一个是高中的数学函数,旋转,这是一个难点,其实可以通过找规律,求解,第二公式则是欧几里得距离公式。$ \sqrt{(x_1-x_2)^2 - (y_1-y_2)^2} $
  3. 最难的就是如何旋转这个正方形 找规律。

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

  1. 左上角:我们可以发现,左上角的$N-1$级矩阵其实就是等级为$N-1$,也就是上一个矩阵,顺时针旋转$90°$,那么既然如此的话,我们就可以综合yxc老师上课所讲的公式(补充:也就是旋转矩阵,属于大学的线性代数内容),得出转移后的矩阵中的一点坐标从$(x,y)$变为$(y,x)$
  2. 左下角:同左上角,它则是逆时针旋转$90°$而且还要水平翻转,也即是沿着$X$轴对称,原本逆时针后为$(y,-x)$,然后要对称,$x$坐标不变,$y$坐标取反,所以坐标为$(-y,-x)$ 也就是所谓的$(2 \times len-1 -y,len-1-x)$ 最难理解的坐标,具体可以画图理解
  3. 右上角和右下角:通过$N=2$级图发现,其实和$N=1$是一样的,并没有旋转,只是平移,则右上角坐标为$(x,y+len)$,右下角坐标为$(x+len,y+len)$
  4. 总的来说以上四种转移,都可以通过画图理解
  5. 还有本题数据毒瘤,四舍五入最好是double类型,而且整数类型一定要是long long,否则容易WA!
易错点:公式使用,double型浮点数精度问题,输出格式化问题,还有@墨辛大佬指出的问题。

C++ 代码

以下为ACwingAc代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
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;
}
//以下为POJ&Acwing Ac代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
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;
    scanf("%d",&t);
    while(t--)
    {
        ll n,a,b;
        scanf("%lld%lld%lld",&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(double(dx*dx+dy*dy))*10);
        printf("%0.lf\n",ans);
    }
    return 0;
}

56 评论


用户头像
Oublie_le   2022-10-23 11:00         踩      回复

%0.lf和%.0lf是不是一样的啊,奇数.5进位,偶数.5不进位不会产生误差吗?


用户头像
Cspecialnq.   2021-05-15 07:58         踩      回复

欧几里得距离公式是sqrt(x^2+y^2)
题解第2点大佬是打错了嘛


用户头像
eeach   2020-02-26 12:29         踩      回复

能问一下,这个解法大佬的坐标系是怎么建立的吗?

用户头像
慢慢来oooo   2024-03-03 19:49         踩      回复

x 轴是竖直向下为正方向,y 轴是水平向右为正方向


用户头像
zmj2008   2019-11-02 18:50         踩      回复

为什么错了???

用户头像
Roxy   2022-08-05 09:54         踩      回复

查阅了一下,printf("%d %d\n",a,b);
a,b入栈时是64位数,而printf是以32位数解析"%d"格式的,即printf("%d %d\n",a,b);只解析了a的低32位和高32位。

用户头像
Roxy   2022-08-05 09:54         踩      回复

也就是没有读干净。所以建议用cin

用户头像
啦啦啦啦_5   2022-10-10 21:10    回复了 Roxy 的评论         踩      回复

%lld就行了

用户头像
啦啦啦啦_5   2022-10-10 21:10    回复了 啦啦啦啦_5 的评论         踩      回复

cin太慢,容易逝


用户头像
zmj2008   2019-11-02 18:50         踩      回复
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>

pll celc(ll n,ll m){
    if(n==0) return make_pair(0,0);
    ll len=1ll<<(n-1);
    ll cnt=1ll<<(2*n-2);
    pll pos=celc(n-1,m%cnt);
    ll x=pos.first,y=pos.second,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);
    if(z==3) return make_pair(2*len-y-1,len-x-1);
}

int main(){
    ll t;
    scanf("%d",&t);
    while(t--){
        ll n,a,b;
        scanf("%d %d %d",&n,&a,&b);
        pll A=celc(n,a-1);
        pll B=celc(n,b-1);
        double x=A.first-B.first;
        double y=A.second-B.second;
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}
用户头像
Roxy   2022-08-05 09:51         踩      回复

$t$ 你读入的是int,但你定义的是ll,所以要么改成int t,要么读入lld.我调你的代码很久才发现是$t$有问题,对于这个结果我也很震惊,有无大佬解释一下?

用户头像
Roxy   2022-08-05 09:55    回复了 Roxy 的评论         踩      回复

查阅了一下,printf("%d %d\n",a,b);
a,b入栈时是64位数,而printf是以32位数解析"%d"格式的,即printf("%d %d\n",a,b);只解析了a的低32位和高32位。


用户头像
STRUGGLING   2019-08-28 09:53         踩      回复

大佬,左下角那个坐标为什么还要水平翻转啊?水平翻转之后反而还错位了

用户头像
开朗未来   2019-09-02 14:35         踩      回复

左下角入口在右边啊,所以要翻转

用户头像
STRUGGLING   2019-09-03 23:25    回复了 开朗未来 的评论         踩      回复

哦哦,原来是这样啊,太感谢了,我懂啦~


用户头像
Tisen   2019-08-06 10:37         踩      回复

POJ wa了怎么破大佬,在线脑壳疼

用户头像
秦淮岸灯火阑珊   2019-08-06 16:06         踩      回复

发一下地址让我康康.
其实我也脑壳疼.(逃

用户头像
Tisen   2019-08-07 15:59    回复了 秦淮岸灯火阑珊 的评论         踩      回复

http://poj.org/problem?id=3889

用户头像
秦淮岸灯火阑珊   2019-08-07 16:45    回复了 Tisen 的评论         踩      回复

我晚上康康。

用户头像
畅恩   2020-02-13 18:01    回复了 秦淮岸灯火阑珊 的评论         踩      回复

解决了吗?

用户头像
畅恩   2020-02-13 18:49         踩      回复

输出格式换成.0f就能过
原因是:
在c++99里面,sqrt返回值类型是float
所以%lf输出就错了.
——yxc


用户头像
吕德华   2019-07-08 20:59         踩      回复

大佬,为什么z==1时是y+len,不应该是x+len吗

用户头像
nodeee   2020-07-28 16:42         踩      回复

同问

用户头像
嗯呐_1   2021-07-30 10:03    回复了 nodeee 的评论         踩      回复

我看半天看明白了,y+len与x+len其实都是可以的这与你选取的坐标系是有关的,楼主的坐标向右为y,向下为x。相应的,如果z==1时,(x+len,y),那么z==3时,(len-1-y,2*len-1-x)


用户头像
ReScale   2019-06-12 10:03         踩      回复

左上角是先顺时针旋转90°,再y轴对称,算出来是(-y, -x)。
左下角是先逆时针旋转90度,再y轴对称,算出来是(y,x)
我难道理解错了吗。

用户头像
秦淮岸灯火阑珊   2019-06-14 18:24         踩      回复

是不是算错了啊.可以发一下推导过程吗?

用户头像
ReScale   2019-06-15 09:37    回复了 秦淮岸灯火阑珊 的评论         踩      回复

(x,y)–顺时针90°–>(y,-x)–y轴对称–>(-y,-x)
(2,1)—>(1,-2)—>(-1,-2)

用户头像
ReScale   2019-06-15 09:39    回复了 秦淮岸灯火阑珊 的评论         踩      回复

你上面的左小角写成了X轴对称。
逆时针90°的话,不应该是(x,y)—>(-y,x)吗。

用户头像
归于虚无   2019-07-21 11:03    回复了 ReScale 的评论      1    踩      回复

你的”y轴对称“和这里的y轴是两个概念。。。
这里的坐标采用的是数组的形式。。。


用户头像
robot_1   2019-06-02 04:13         踩      回复

旋转矩阵不明白qaq

用户头像
秦淮岸灯火阑珊   2019-06-14 18:25         踩      回复

这个y总有视频.


用户头像
robot_1   2019-06-02 03:44         踩      回复

大佬,ake_pair(2*len-1-y,len-1-x);这个还是有点不懂…

用户头像
秦淮岸灯火阑珊   2019-06-02 07:52         踩      回复

yxc老师好像有视频,详细解说了四十分钟,你可以康康.如果还是不清楚,我就发一个图片理解吧.

用户头像
robot_1   2019-06-02 14:01         踩      回复

老师用的矩阵乘法..那个不会…麻烦您了

用户头像
秦淮岸灯火阑珊   2019-06-14 18:26    回复了 robot_1 的评论         踩      回复

这道题目似乎只能通过矩阵乘法推导过去.

用户头像
吕德华   2019-07-08 20:06    回复了 robot_1 的评论         踩      回复

这个线性代数里面的知识


用户头像
简单的人生   2019-04-16 09:00         踩      回复

为什么左下角的情况就是加 2*len-1 和 len-1 而 其他就是直接加len

用户头像
秦淮岸灯火阑珊   2019-04-16 19:13         踩      回复

是的,其他直接处理,但是左下角它是多次转换了,你可以看yxc老师的视频.


用户头像
十七   2019-03-08 17:25         踩      回复

ll len=1LL<<(n-1),cnt=1LL<<(2*n-2);
PLL pos=calc(n-1,m%cnt);

这个 我需要解释 · ~ ·

用户头像
秦淮岸灯火阑珊   2019-03-08 19:11         踩      回复

1ll是强制longlong

用户头像
秦淮岸灯火阑珊   2019-03-08 19:12    回复了 秦淮岸灯火阑珊 的评论         踩      回复

calc内是继续分治,cnt记录这个城市群有多少个座城市

用户头像
十七   2019-03-08 20:36    回复了 秦淮岸灯火阑珊 的评论         踩      回复

多谢大佬 突然顿悟

用户头像
秦淮岸灯火阑珊   2019-03-08 21:45    回复了 十七 的评论         踩      回复

= ̄ω ̄=


用户头像
墨辛   2019-02-26 00:02         踩      回复

ORZ下大佬,但是好像过不了poj 3889的数据

用户头像
秦淮岸灯火阑珊   2019-02-26 06:26         踩      回复

TLE吗?

用户头像
秦淮岸灯火阑珊   2019-02-26 06:30         踩      回复

是不是CE啊?我使用的bits库

用户头像
秦淮岸灯火阑珊   2019-02-26 06:35         踩      回复

刚刚发现是sqrt里面类型的锅,马上上传POJ可AC的代码

用户头像
秦淮岸灯火阑珊   2019-02-26 06:36         踩      回复

谢谢指出问题.

用户头像
墨辛   2019-02-26 11:23    回复了 秦淮岸灯火阑珊 的评论         踩      回复

ORZ,大佬强呀

用户头像
墨辛   2019-02-26 11:49    回复了 秦淮岸灯火阑珊 的评论         踩      回复

仿佛不是里面类型的锅,仿佛是因为编译器的问题,输出用%.0f就可以过了

用户头像
秦淮岸灯火阑珊   2019-02-26 19:05    回复了 墨辛 的评论         踩      回复

是编译器,Acwing编译器版本高一些,POJ太老了.

用户头像
刚撸有点虚   2019-04-09 13:10         踩      回复

ORZ


用户头像
Yida915   2019-01-31 14:11         踩      回复

感谢题解,全靠大佬带~

用户头像
秦淮岸灯火阑珊   2019-01-31 15:59         踩      回复

客气了,我的题解其实挺普通的,主要是您悟性高.


用户头像
wasd003   2019-01-20 09:15         踩      回复

讲解清晰,厉害厉害。

用户头像
秦淮岸灯火阑珊   2019-01-20 10:18         踩      回复

过誉了


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息