坐标变换（转换）

坐标变换（转换） 坐标变换 1. 概述

• 这类题目一般使用递归解决，原问题转化为若干个子问题，根据子问题的解可以求出原问题的解。

• 当问题牵涉到下标时，就需要使用坐标变化，有时候需要将原问题的坐标转化到子问题中，有时候需要将子问题的坐标转化为原问题的坐标。

• 一般来说，如果题目让求解的就是坐标的话，需要根据子问题的坐标求解出原问题的坐标，例如：AcWing 98. 分形之城；如果求解的不是坐标的话，需要将原问题的坐标转化成子问题的坐标，例如：AcWing 631. Googol字符串。

• 根据坐标的维度可以分为多种类型，这里讲解两种类型：

  • （1）一维坐标变换：AcWing 631. Googol字符串；

  • （2）二维坐标变换：AcWing 98. 分形之城。

2. 例题 AcWing 631. Googol字符串

问题描述

• 问题链接：AcWing 631. Googol字符串

分析

• 因为k最大为 1 0 18 10^{18} 1018，因此 S 63 S_{63} S63​ 就一定包含答案了。这里每一段的长度为 2 n − 1 2^n-1 2n−1。

• 直接递推不容易求解，因此使用递归求解，f(63, k)表示求解 S 63 S_{63} S63​ 中第k个字符（k从0开始）。

• 考虑如何求解 f(n, k)。 S n S_n Sn​可以分为三部分，如下图：

• 如果k出现在第一段，则f(n, k) = f(n-1, k)；

• 如果k出现在第二段，则f(n, k) = 0；

• 如果k出现在第三段，设 l e n = 2 n − 1 − 1 len = 2^{n-1}-1 len=2n−1−1，则这个字符在第三段是第 k − l e n − 1 k - len - 1 k−len−1，是第三段中倒数第 l e n + 1 − ( k − l e n − 1 ) len + 1 - (k - len - 1) len+1−(k−len−1)个字符，因为要取反，因此有f(n, k) = 1 - f(n-1, len + 1 - (k - len - 1))。

代码

• C++

#include 

using namespace std;

typedef long long LL;

int f(int n, LL k) {
    
    LL len = (1ll << n - 1) - 1;
    if (k <= len) return f(n - 1, k);  // 第一段
    if (k == len + 1) return 0;  // 第二段
    return 1 - f(n - 1, len + 1 - (k - len - 1));  // 第三段
}

int main() {
    
    int T;
    cin >> T;
    
    for (int C = 1; C <= T; C++) {
        
        LL k;
        cin >> k;
        
        printf("Case #%d: %dn", C, f(63, k));
    }
    
    return 0;
}

AcWing 98. 分形之城

问题描述

• 问题链接：AcWing 98. 分形之城

分析

• 等级为n的图形一共有 2 2 n 2^{2n} 22n个，编号从1到 2 2 n 2^{2n} 22n，为了处理方便，这里让标号都减去1，变为从0到 2 2 n − 1 2^{2n}-1 22n−1。

• 考虑等级n与等级n-1之间的关系，如下图：

• 每一个n-1级的图形有 b l o c k = 2 2 n − 2 block=2^{2n-2} block=22n−2个街区，给定一个编号为a的街区，如何确定其在上图中（红色编号）哪个部分呢？答案是在a/block这个部分，然后问题就变为了求一个n-1级的子问题。使用get(n, a)表示求解一个n级编号为a（编号从0开始）的街区的坐标（坐标从(0, 0)开始）。

• 下面需要考虑的就是编号以及坐标变换。

• 编号a转化到n-1级子问题后，编号变为了a%block。

• 坐标变换：当前问题是get(n, a)，子问题为get(n-1, a%block)，假设子问题返回的坐标为(x, y)，现在要求解原问题的坐标。根据a在上图中四个不同的位置，转换公式不同。分为四种情况：

子问题坐标为(x, y)，转化到原问题的坐标
0:( y, x )
1:( x, y+2^(n-1) )
2:( x+2^(n-1), y+2^(n-1) )
3:( 2^(n-1)+2^(n-1)-1-y, 2^(n-1)-1-x )

代码

• C++

#include 
#include 
#include 

typedef long long LL;

struct Point {
    LL x, y;
};

Point get(int n, LL a) {
    if (n == 0) return {0, 0};
    LL block = 1ll << 2 * n - 2, len = 1ll << n - 1;
    auto p = get(n - 1, a % block);
    LL x = p.x, y = p.y;
    
    int z = a / block;
    if (z == 0) return {y, x};
    if (z == 1) return {x, y + len};
    if (z == 2) return {x + len, y + len};
    return {len * 2 - 1 - y, len - 1 - x};
}

int main() {
    
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        LL a, b;
        scanf("%d%lld%lld", &n, &a, &b);
        auto pa = get(n, a - 1);
        auto pb = get(n, b - 1);
        double dx = pa.x - pb.x, dy = pa.y - pb.y;
        printf("%.0lfn", sqrt(dx * dx + dy * dy) * 10);
    }
    
    return 0;
}