POJ3889 Fractal Streets
Fractal Streets 一道标准的搜索题,然而和poj(g++?)的蜜汁bug(printf)斗争了一小时……. 顺便吐槽下,本题描述图片n=2,房子7和8画反了….. 观察可以知道,从n-1变成n时:
- 左上顺时针旋转90°再水平翻转
- 右上形状不变
- 右下形状不变
- 左下逆时针旋转90°,再水平翻转
房子编号按照上面列举的顺序,于是可以分为四块处理 先递归求出n-1时房子的位置,然后判断在哪一块,旋转即可 为了方便(偷懒),把题目输入的两个房号都-1 搜索部分代码如下:
1 | void f(long long n, long long t, long long &a, long long &b) { |
踩到的几个坑:
- 本题数据范围万恶,采用long long
- 输出应该用printf(“%.0f”,ans);保证精度
- 不要写printf(“%.0lf”,ans);,因为这个TLE了很久….poj首页有写原因