Niuke real problem programming - day16

Compile environment ：c++

1、 Shanzhai glitters

describe ：

After Jin Shanshan died , red A Got the treasure of the king , There are n A weapon , The lengths are different . red A Find out , Take three of these weapons head to tail , Form a triangle , Perform the calling ceremony , You can summon a Shanzhai Jinshan .（ for example , The length of three weapons is 10、15、20, Can summon success . If the length is 10、11、30, The triangle cannot be formed by connecting the head and the tail , Call failed .） red A So he opened a glittering store . He lined up the treasures of the king , Each guest will be randomly selected into an interval [l,r], Guests can choose three weapons in the section to summon （ The guests are very intelligent , If you can find the right weapon , I will never let go ）. After the call , Guests should put the weapons back as they are .m After a guest patronized , red A Afraid of too much glitter, happy too many men , So I found you , I hope you can help him count how many Shanzhai Jinshan were summoned .

Data range ： 1≤n≤10^7 , 1≤m≤10^6   , The length of each weapon meets 1≤val<2^32 

Algorithmic thought ：

Declare array first , Store the length of each weapon entered . We can go until ： For a given three numbers , In ascending order , If the sum of the smallest two numbers is greater than the third number , Then it must form a triangle . Therefore, it is necessary to judge whether a triangle call can be formed in the interval , Then the elements in the interval can be arranged in ascending order , Work in groups of three to judge whether the conditions are met .

To optimize code efficiency . Because the length of each weapon is 2^32 within a country's boundaries , Also known , For a given ascending sequence , If you want to be unable to form a triangle , It can only be arranged like Fibonacci sequence ：1、1、2、3、5..... because 2^32-1=4294967295, In the Fibonacci sequence 47,48 position 2971215073,4807526976 Between . So there are conditions when the interval is greater than 46 There is no need to make complex algorithm judgment , It must form a triangle （ Weapons are different , therefore 1、2 Bit 1 Drop one ）.

The code part implements ：

2、 Phone number separation

describe ：

Following MIUI8 After launching the mobile phone separation function ,MIUI9 Plan to launch a phone number separation function ： First, add... To each number in the phone number 8 Take a place , Then use the corresponding capital letter instead of （"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"）, Then randomly shuffle the letters , The generated string is the corresponding part of the phone number .

Algorithmic thought ：

First, record the number of various letters in the input string , With automatic conversion ascii Code as an index of letters . It is difficult to recover a complete numeric string from a scrambled string , So we can observe the characters unique to each numeric character , First , The five easiest to distinguish are FOUR(U),SIX(X),TWO(W),EIGHT(G),ZERO(Z), You can directly judge how many corresponding numbers there are according to the number of these special letters ; Then exclude all the letters they contain , Then other numbers with repeated letters have special letters , Yes FIVE(F),THREE(T); After excluding the number of letters contained in these numbers , And then there is SEVEN Contains special V,; In the end ONE(O),NINE(I).

Then push back +8 Previous figures , Such as now 4 The number of corresponds to the original phone number 6 The number of . Then store 0-9 The smallest phone number combination can be obtained by sequentially outputting an array of numbers .

The code part implements ：

3、 At the end of 0 The number of

describe ：

Enter a positive integer n, seek n!( That is factorial ) How many at the end 0？ such as : n = 10; n! = 3628800, So the answer is 2

Algorithmic thought ：

0 The last bit of is actually 5 Multiplied by an even number , Then we can decompose n Factorial of all numbers , Find one of them 2 and 5 The number of . And because the number of even numbers is far greater than 5 The number of , So we can directly consider n How many factorials can be decomposed 5 that will do .n/5 It is the closest n The factorial of an integer of contains 5 The number of , such as 20/5=4,20 There is 5,10,15,20 four 5 Multiple . Then continue to recursively call the result , such as 125 The factorial of contains 25,25 Can be decomposed into 2 individual 5... Print the results

The code part implements ：