$ POJ~3889~Fractal~Streets $（模拟）
$ solution: $
这是一道淳朴的模拟题，最近发现这种题目总是可以用逼近法，就再来练练手吧。
首先对于每个编号我们可以用逼近法求出它在各个图上是处于左上，右上，左下，右下中的哪一个。
inline void bijin(int i,int v){
if(i==0)return ;
rg x=1<<(i*2-2),y=1;
while(v>x)v-=x,++y;
t[i]=y; bijin(i-1,v);
}
然后我们在用逼近法将它的坐标一步步复原。（中间会涉及旋转操作）
inline void find(int i,int x,int y,int f,su &v){
if(i>n){v.x=x; v.y=y; return ; }
rg l=1<<(i-1);
if(t[i]==1){
rg xx=x,yy=y;
x=l-yy+1;
y=l-xx+1;
}
if(t[i]==4){
rg xx=x,yy=y;
x=yy;
y=xx;
}
if(t[i]==1||t[i]==2)x+=l;
if(t[i]==2||t[i]==3)y+=l;
find(i+1,x,y,t[i],v);
}
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,a,b;
int t[17];
struct su{
int x,y;
}sa,sb;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void bijin(int i,int v){
if(i==0)return ;
rg x=1<<(i*2-2),y=1;
while(v>x)v-=x,++y;
t[i]=y; bijin(i-1,v);
}
inline void find(int i,int x,int y,int f,su &v){
if(i>n){v.x=x; v.y=y; return ; }
rg l=1<<(i-1);
if(t[i]==1){
rg xx=x,yy=y;
x=l-yy+1;
y=l-xx+1;
}
if(t[i]==4){
rg xx=x,yy=y;
x=yy;
y=xx;
}
if(t[i]==1||t[i]==2)x+=l;
if(t[i]==2||t[i]==3)y+=l;
find(i+1,x,y,t[i],v);
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
rg tt=qr(); t[0]=1;
while(tt--){
n=qr(); a=qr(); b=qr();
bijin(n,a); find(1,1,1,1,sa);
bijin(n,b); find(1,1,1,1,sb);
rg x=sa.x-sb.x,y=sa.y-sb.y;
db z=sqrt((db)x*x*100+(db)y*y*100);
rg ans=(int)(z*2)-(int)z;
printf("%d\n",ans);
}
return 0;
}
转载于:https://www.cnblogs.com/812-xiao-wen/p/11248915.html
相关资源：JAVA上百实例源码以及开源项目
