当前位置:网站首页>Niuke real problem programming - day16
Niuke real problem programming - day16
2022-07-07 14:53:00 【weixin_ forty-five million seven hundred and fifty thousand fou】
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 :
边栏推荐
- Read PG in data warehouse in one article_ stat
- Differences between cookies and sessions
- PLC:自动纠正数据集噪声,来洗洗数据集吧 | ICLR 2021 Spotlight
- AWS learning notes (III)
- JSON parsing instance (QT including source code)
- Internal sort - insert sort
- 2022pagc Golden Sail award | rongyun won the "outstanding product technology service provider of the year"
- Data Lake (IX): Iceberg features and data types
- PyTorch模型训练实战技巧,突破速度瓶颈
- MicTR01 Tester 振弦采集模块开发套件使用说明
猜你喜欢
拜拜了,大厂!今天我就要去厂里
Promoted to P8 successfully in the first half of the year, and bought a villa!
[Yugong series] go teaching course 005 variables in July 2022
Introduction and use of Kitti dataset
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条...
JSON parsing instance (QT including source code)
asp. Netnba information management system VS development SQLSERVER database web structure c programming computer web page source code project detailed design
大厂做开源的五大痛点
Novel Slot Detection: A Benchmark for Discovering Unknown Slot Types in the Dialogue System
Beginner JSP
随机推荐
昇腾体验官第五期随手记I
Novel Slot Detection: A Benchmark for Discovering Unknown Slot Types in the Dialogue System
[Yugong series] go teaching course 005 variables in July 2022
IDA pro逆向工具寻找socket server的IP和port
#yyds干货盘点# 解决名企真题:交叉线
Because the employee set the password to "123456", amd stolen 450gb data?
缓冲区溢出保护
C# 6.0 语言规范获批
Bill Gates posted his resume 48 years ago: "it's not as good-looking as yours."
数据湖(九):Iceberg特点详述和数据类型
CTFshow,信息搜集:web1
Delete a whole page in word
Infinite innovation in cloud "vision" | the 2022 Alibaba cloud live summit was officially launched
AWS学习笔记(三)
How does the database perform dynamic custom sorting?
[server data recovery] a case of RAID data recovery of a brand StorageWorks server
EMQX 5.0 发布:单集群支持 1 亿 MQTT 连接的开源物联网消息服务器
Mmkv use and principle
Mlgo: Google AI releases industrial compiler optimized machine learning framework
Read PG in data warehouse in one article_ stat