转载

[转载] $CF171H$ 题解

阅读原文

本题是\(POJ3889\) \(Fractal\) \(Streets\)的弱化版,原题做法见我的博客(密码请私信 \(Peter\) 索取)

首先,这是一道 \(CodeForces\) \(2012\) 年愚人节比赛的 \(H\) 题。愚人节比赛的特点就是题目诡异,一般没有正式的题面,需要通过观察得出问题。

观察题图,容易发现这题是个分形图,通过不断复制、旋转将图形变大。每次复制时,将原图放于左上方,右上方复制一份,左下方顺时针旋转 \(90^\circ\) 后复制一份,右下方逆时针旋转 \(90^\circ\) 后复制一份。

由于 \(n\) 级城市的大小为 \(2^{2n}\)\(n-1\) 级城市的大小为 \(2^{2n-2}\) ,不难想到将 \(n\) 级城市放回 \(n-1\) 级城市寻找位置,通过递归把问题规模不断缩小。

总体思路是找出 \(n\) 级城市中 \(m\) 点的坐标。

设所有点从 \(0\) 开始编号, \(calc(n,m)\) 返回 \(n\) 级城市中 \(m\) 点的坐标。

每次计算 \(calc(n,m)\) 时,先得到 \(calc(n-1,m\) $ mod $ \(2^{2n-2})\) ,即 \(m\) 点在 \(n-1\) 级城市中的坐标。

然后根据 \(m / 2^{2n-2}\) 的结果来判断 \(m\) 点在哪个 \(n-1\) 级城市中。

这个地方我想了好久,中间还断了次电,现在是重写的版本,万一写错了,请马上告诉 \(Peter\) ,感激不尽。

为什么可以这样做呢?因为每一个 \(2^{2n}\) 大小的城市都是由左上 \(2^{2n-2}\) ,右上 \(2^{2n-2}\) ,左下 \(2^{2n-2}\) ,右下 \(2^{2n-2}\) 四座小城市组成的。编号的顺序就是先编完左下 \(\frac{1}{4}\) ,再编左上 \(\frac{1}{4}\) ,然后编右上 \(\frac{1}{4}\) ,最后编右下 \(\frac{1}{4}\)

因此,由平面直角坐标系内的几何变换知识可得(下面这段不清楚的可以私信问 \(Peter\) ,线上讲解,包教包会,不会再学),

\(m / 2^{2n-2}=0\) 时,表示 \(m\) 点在左下 \(n-1\) 级城市中,根据 \(m\) 点在 \(n-1\) 级城市中的坐标 \((x,y)\) 顺时针旋转 \(90^\circ\) 再垂直翻转可得 \(m\) 点在 \(n\) 级城市中的坐标 \((y,x)\)

\(m / 2^{2n-2}=1\) 时,表示 \(m\) 点在左上 \(n-1\) 级城市中,根据 \(m\) 点在 \(n-1\) 级城市中的坐标 \((x,y)\) 向上平移可得 \(m\) 点在 \(n\) 级城市中的坐标 \((x,y+2^{n-1})\)

\(m / 2^{2n-2}=2\) 时,表示 \(m\) 点在右上 \(n-1\) 级城市中,根据 \(m\) 点在 \(n-1\) 级城市中的坐标 \((x,y)\) 向右向上平移可得 \(m\) 点在 \(n\) 级城市中的坐标 \((x+2^{n-1},y+2^{n-1})\)

\(m / 2^{2n-2}=3\) 时,表示 \(m\) 点在右下 \(n-1\) 级城市中,根据 \(m\) 点在 \(n-1\) 级城市中的坐标 \((x,y)\) 顺时针旋转 \(90^\circ\) 再垂直翻转然后水平翻转最后垂直翻转可得 \(m\) 点在 \(n\) 级城市中的坐标 \((2^n-y-1,2^{n-1}-x-1)\)

\(trick\) :对于坐标的计算和转移可以使用如 \(pair<int,int>\) 类型的函数,返回值需要 \(make \_ pair(x,y)\)

细节:递归边界是 \(0\) 级城市,坐标为 \((0,0)\)

那么,输入城市级数 \(a\) ,序号 \(b\) 算出坐标输出就做完咯!如有疑问,评论区见!

代码如下:

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int a,b,ansx,ansy; pair <int,int> calc(int n,int m) { if(n==0) return make_pair(0,0); int len=1<<(n-1),mod=1<<(2*n-2),cas,x,y; pair<int,int> tmp=calc(n-1,m%mod); x=tmp.first; y=tmp.second; cas=m/mod; if(cas==1) return make_pair(x,y+len); if(cas==2) return make_pair(x+len,y+len); if(cas==0) return make_pair(y,x); if(cas==3) return make_pair(len*2-y-1,len-x-1); } int main() { a=read(); b=read(); pair<int,int> ans; ans=calc(a,b); ansx=ans.first; ansy=ans.second; printf("%d %d\n",ansx,ansy); return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11273075.html

正文到此结束
本文目录