POJ3889 Fractal Streets

发表于 更新于 分类于 阅读次数：

Fractal Streets 一道标准的搜索题，然而和poj（g++？）的蜜汁bug（printf）斗争了一小时……. 顺便吐槽下，本题描述图片n=2，房子7和8画反了….. 观察可以知道，从n-1变成n时：

  • 左上顺时针旋转90°再水平翻转
  • 右上形状不变
  • 右下形状不变
  • 左下逆时针旋转90°，再水平翻转

房子编号按照上面列举的顺序，于是可以分为四块处理 先递归求出n-1时房子的位置，然后判断在哪一块，旋转即可 为了方便（偷懒），把题目输入的两个房号都-1 搜索部分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void f(long long n, long long t, long long &a, long long &b) {
    if (n == 0) { a = b = 0; return; }
    // edge是二分之一边长，size是四分之一面积
    long long edge = 1 << (n - 1), size = 1 << (2 * n - 2);
    f(n - 1, t % size, a, b);
    long long block = t / size;
    if (block == 0)
        long long tmp = a, a = b, b = tmp;
    else if (block == 1)
        b += edge;
    else if (block == 2)
        a += edge, b += edge;
    else
        long long tmp = a, a = 2 * edge - b - 1, b = edge - tmp - 1;
}

踩到的几个坑：

  • 本题数据范围万恶，采用long long
  • 输出应该用printf(“%.0f”,ans);保证精度
  • 不要写printf(“%.0lf”,ans);，因为这个TLE了很久….poj首页有写原因