- 2021-04-11 18:59
*views 12*- 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

- Java296 blogs
- Python265 blogs
- Vue125 blogs
- c language122 blogs
- algorithm107 blogs
- MySQL96 blogs
- Flow Chart81 blogs
- javascript79 blogs
- more...

Daily Recommendation

views 12

views 5

views 5

views 5

views 4

© ioDraw All rights reserved

**CSS Define variables redis Cache penetration of , Buffer breakdown , Cache avalanche vue Get data from the background UserWarning: Failed to load image Python extension: warn(f“Failed to load image Python extension:SpringBoot Cached @Cacheable Detailed introduction Simply check the network with commands Design of fourth-order Butterworth low-pass filter Redis Cache avalanche , pierce through , breakdown MySQL database Single table data record query vue Real time acquisition time