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

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

The problem of string left rotation Interview essential ： Data structure time complexity and usage Remove outliers , use python to write matlab Of hampel(X) function BN layer pytorch realization Linux C Three methods of redirecting standard input and output to file [ Thesis reading ]HRNetV1,HRNetV2,HRNetV2p2021 World ranking of Computer Science Major ! This year's ranking reshuffle What certificates can big data test ? use Python and Pygame Implementation of code rain 2020 The 11th National Blue Bridge Cup B group C/C++