I wrote this question for more than an hour , It's still too much food , Both examples have been passed , Third order piano took two random points , The distance is right, too , If a big guy finds my problem , Welcome to correct
Here is my idea
<> thinking
Totality is to find out the distance between two points and the origin , Then subtract
So how to ask specifically , It can be found that , When k > 1 k > 1 k>1 When I was young , The piano curve can be decomposed into two parts 3 × 3 3 × 3 3×3 Of k − 1 k
- 1k−1 Second order piano curve block
So let's say it's the second time k i k_i ki rank , So we can figure out how many times we've gone through k i − 1 k_i - 1 ki−1 The step moves to the current coordinate k
i − 1 k_i - 1ki−1 Step block
Just figure out how many blocks you've gone through , So, because the distance in each block is zero ( k i − 1 ) ( k i − 1 ) (k_i - 1)(k_i - 1) (ki−1)(k
i−1) individual , You can find out how many blocks have passed before the current block
And then recursion k i − 1 k_i - 1 ki−1 In the case of step
until k = = 1 k == 1 k==1 Time , It is classified as the distance from the first order piano curve to the starting point
Because the first order piano curve is based on the in and out direction and the matrix direction , There are four different situations , After analysis, we can actually write a coordinate change , It can be solved by transforming them into a certain case
<> code
#include <iostream> #include <cmath> using namespace std; typedef long long LL;
int k; int x1, y1; int x2, y2; // First order piano distance function int get_k1(int x,int y) { int dis =
0; if(x == 0) dis = y; if(x == 1) dis = 3 + (2 - y); if(x == 2) dis = 6 + y;
return dis; } // Identify the first few k block int get_block(int x, int y, int &d) { int sum = 0;
if(x == 0 && y == 0) { d = 0; sum = 0; } if(x == 0 && y == 1) { d = 1; sum = 1;
} if(x == 0 && y == 2) { d = 0; sum = 2; } if(x == 1 && y == 2){ d = 2; sum = 3;
} if(x == 1 && y == 1) { d = 3; sum = 4; } if(x == 1 && y == 0) { d = 2; sum = 5
; } if(x == 2 && y == 0) { d = 0; sum = 6; } if(x == 2 && y == 1) { d = 1; sum =
7; } if(x == 2 && y == 2) { d = 0; sum = 8; } return sum; } // coordinate transformation . d
It's used to determine which situation , Refer to the title chart for detailed values void trans(LL &x, LL &y,int d) { if(d == 0) return; if(d ==
1) { x = 2 - x; return; } if(d == 2) { y = 2 - y; return; } if(d == 3) { x = 2 -
x; y = 2 - y; return; } } // Recursive solution LL get(LL x, LL y, int k,int d) { LL sum = 0;
if(k == 1) { trans(x,y,d); sum += get_k1(x,y); return sum; } LL sub = pow(3,k -
1); int tx = x / sub, ty = y / sub; int blocks = get_block(tx,ty,d); sum =
blocks* sub * sub; sum += get(x % sub,y % sub,k - 1,d); return sum; } int main()
{ cin >> k; cin >> x1 >> y1; cin >> x2 >> y2; get(x1,y1,k,0); cout << abs(get(x1
,y1,k,0) - get(x2,y2,k,0)) << endl; return 0; } /* 2 3 4 0 0 */
Technology