- 2021-04-11 18:59
*views 10*- Blue Bridge Cup
- algorithm

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

- Python180 blogs
- Java171 blogs
- Vue92 blogs
- Flow Chart80 blogs
- algorithm54 blogs
- C++51 blogs
- javascript48 blogs
- MySQL46 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

Java project ： CET-4 and CET-6 online examination information website （java+ssm+mysql+maven）【iOS】 How to give UICollectionView add to headerView14:00 interview ,14:08 Just came out , The question is too much ...jquery Detailed explanation of method properties Shopping in Ali 8 In, he sorted out his study notes , Helped 10 A friend got it offer How to solve the synchronization delay problem of database read-write separation ? Predicting future stock trend with deep learning algorithm centos Which version works well _CentOS VS Ubuntu, Who is better Linux edition ? be based on LSTM Detailed explanation of stock forecasting algorithm In Ali 10 year Java My cousin came back from vacation , After chatting, I realized everything