【 Write in the front 】
This time the question is still difficult , Just do it 7 Avenue , Hand it in 6 Avenue , The other half is violence . Just ask for country three
The first two blank filling questions took almost two hours , Directly break the mentality .. Is dubious ！
The solution to this problem only represents personal views and ideas , It's not the standard answer . Welcome everyone to guide and exchange .
All codes are stored in the warehouse ：
Github：https://github.com/AYO-YO/Algorithm/tree/ Blue Bridge Cup _ National Games
Gitee: https://gitee.com/ayo_yo/Algorithm/tree/ Blue Bridge Cup _ National Games
【 Problem description 】
The recurrence formula of Fibonacci sequence is ： F n = F n − 1 + F n − 2 F_n = F_{n-1} + F_{n-2} Fn=Fn−1+Fn−2, among F 1 = F 2 = 1 F_1 = F_2 = 1 F1=F2=1.
Excuse me, , Fibonacci Series No 1 1 1 to 202202011200 202202011200 202202011200 term （ contain ） in , How many items have a bit of 7 7 7.
【 Answer submission 】
This is a question to fill in the blanks , You just need to work out the results and submit them . The result of this question is an integer , Only fill in the whole number when submitting the answer , Fill in the extra content will not be able to score .
【 Thought analysis 】
This problem is an extra large number , Fibonacci is an exponential growth , Direct explosion is definitely not possible .
After two big men @m0_62944359 Corrigendum to , The original method is wrong .
At the same time, the leader of the review area @ Autumn rains wash chicken remind , The single digits of Fibonacci series 60 A for 1 round , direct 1000 The number in +100 The number in is wrong , It will lead to incorrect calculation of part number .
So here is the big man @ Autumn rains wash chicken The right way ：
Fibonacci number series single digits 60 One is a cycle
60 There are... In total 8 individual 7.
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0
therefore , The final result should be ：
202202011200/60
Out[3]: 3370033520.0
_*8
Out[4]: 26960268160.0
【 Refer to the answer 】
26960268160
【 Complete code 】
A.py (Gitee.com)A.py (github.com)
【 Problem description 】
Xiao Lan likes scientific research very much , He recently made an experiment and got a batch of experimental data , That's twomillion positive integers . If as expected , All the experimental data x All should be satisfied 10⁷ ≤ x ≤ 10⁸. But there will be some errors when doing experiments , It will lead to some unexpected data , This error data y The range is 10³
≤ y ≤ 10¹² . Because Xiao Lan is very reliable in doing experiments , So of all his experimental data 99.99% All the above are in line with expectations . All the experimental data of Xiaolan are in primes.txt in , Now he wants to count how many of the twomillion positive integers are prime numbers , Can you tell him ？
【 Answer submission 】
This is a question to fill in the blanks , You just need to work out the results and submit them . The result of this question is an integer , Only fill in the whole number when submitting the answer , Fill in the extra content will not be able to score .
【 Thought analysis 】
This question has 200w Number , Direct violence is definitely not enough . I took a detour at the beginning , Multithreading , Primes are used to judge and optimize . Finally, I found that I thought too much , Before the end of the game 1 Minutes before the number explodes , There is no time to write prime tests for large numbers .. Ideas as follows ：
First look at the data , in 1、3、5、7 ending . Greater than 1000 And it ends with 5 Number of numbers , It must be 5 to be divisible by , So we use the editor regular to replace all the 5 Ending number , At this point, about 150w More than one number ：
\d+?5
Use Ehrlich screening , get 10^8 All prime numbers within , Note here , The use of Ehrlich screening needs to be optimized , Otherwise, it is also a big runner . In my previous blog, I also wrote the optimization method of directly judging prime numbers , except 2、3, All prime numbers lie in 6n about . Therefore, the step length of Ehrlich screening method can be directly pulled to 6, In this way, the speed can be further improved , Then the main factors that affect the speed of Ehrlich screening are 2、3、5, It takes several cycles to sift out the resultant number behind , Therefore, the preprocessing will directly generate the list 2、3、5 Multiple return of 0. Theoretically, the more prime multiples directly return to zero , The faster primes are generated .
Count prime Python Ehrlich screening _AYO_YO The blog of -CSDN Blog
Judge the prime number Python Java C++_AYO_YO The blog of -CSDN Blog
def getprimes(n):
ls = [i if i % 2 != 0 and i % 3 != 0 and i % 5 != 0 else 0 for i in range(n + 1)]
ls[1], ls[2], ls[3], ls[5] = 0, 2, 3, 5
for i in range(6, n + 1, 6):
f = i - 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
continue
f = i + 1
if f != 0:
for j in range(2 * f, n + 1, f):
ls[j] = 0
return filter(lambda x: x != 0, ls)
Ehrlich screening 1 0 8 10^8 108 Prime numbers with thein range of the approximately need 2 About minutes , I'm afraid it's too big to bear . So first 1 0 8 10^8 108 The prime number of , And greater than 1 0 8 10^8 108 Take out the prime number of . Get the results 1 0 8 10^8 108 The prime numbers within are 506733 individual . A large number is about 130 individual .
506733
[542693491967, 142787902577, 452440529173, 663634895869, 71242929179, 999870483413, 441673697183, 895134836909, 59008094959, 812048153483, 153230177243, 5986461211, 825268545161, 85386152959, 305669636917, 176618331487, 627185459239, 517233054923, 347714268719, 75380450897, 652349118967, 746710276723, 887316078643, 55623754253, 726602124691, 63723051253, 11944000489, 14326008041, 995344474081, 127374806651, 101228446879, 782792370337, 7616731547, 672817895497, 309261587441, 993510068537, 898280626321, 691250724803, 436362423451, 135244424501, 873959450791, 404517752423, 803431472291, 890481756773, 299729772337, 993254812121, 939705423281, 928689411767, 950796808643, 925182899009, 867933942403, 177084914339, 374154056921, 195931411013, 636268614181, 845966263637, 669349089677, 279219681547, 116772294307, 458677064359, 414099720659, 553029935971, 225122592047, 523383194647, 291752440213, 29190046721, 756126896941, 400963923179, 807339716593, 666619632839, 792597812483, 157223341237, 515677221383, 869902952023, 277744493561, 279840195947, 12066121523, 659914745389, 796743912131, 973038777059, 856703807231, 66169702601, 987064845247, 916671221021, 884623305749, 504935549881, 232438712231, 701919604183, 542037833447, 521942095081, 726449610001, 840499018589, 492469281101, 757165962919, 437417377471, 903288533789, 254110134101, 265121359891, 776841707227, 854559132599, 325401328397, 675731682791, 730947154187, 280786162939, 670729451441, 48996391291, 286681507897, 847973529401, 166381727761, 568868879153, 56085663143, 417414542761, 666771906149, 857635614683, 188918440631, 490214446741, 82741563491, 411523187461, 304024439243, 912661149107, 556591023551, 934801057481, 828742723319, 814141769183, 528476615281, 560425065263, 224638484077, 610321268093, 655599334577, 624348698849]
It is also quite frightening to directly judge whether these large numbers are prime numbers , So we can judge whether a super large number is a prime number , We have to use another method —— Fermat prime test . This is an algorithm I studied in my final assignment of algorithm class before , Is to use random numbers to randomly remainder large numbers , If you can divide , It's not prime ; Added an optimization , A coprime judgment is added , It greatly improves the efficiency and accuracy of the algorithm .
for p in bigNum:
K = 100 # The number of random number verification , The greater the number , The higher the accuracy . Actually measured K=10 You can get accurate results
k = 0
while k < K: # Here we use while It is used to determine whether the random completion rate is 100%
b = int(random.random() * (p - 1) + 1) # Generate a 1~p-1 Random integer between
factor = math.gcd(b, p) # Calculation b,p Maximum common divisor of
r = runFermatPower(b, p, p) # Calculation b^p mod p
print(f" The first {
k + 1} Take random number for times , random number b={
b}, {
b} and {
p} The greatest common divisor of is {
factor}, r=({
b}^{
p})mod p={
r}", end=', ')
if factor > 1:
print(f" because b={
b} And p={
p} The greatest common divisor of is {
factor}, Not coprime number , so p={
p} As composite ")
break
elif r != b:
print(f" because r={
r},({
b}^{
p}) mod p ={
r}!={
b}, so p={
p} As composite ")
break
else:
print(f" so p={
p} It could be prime ")
k += 1
if k == K:
print(f" after {
K} Second cycle verification , p={
p} It could be prime , n The probability of being a prime number is {
(1 - 1 / (2 ** k)) * 100}%")
Get the final result ：
506753
【 Complete code 】
The code in the course of the competition is step-by-step , Step by step , Then get the result and calculate the next step , This code is the optimized full version of the code , You can get the final result by running it directly .
B.py (Gitee.com)B.py (github.com)
【 Problem description 】
Given n , m n, m n,m, Ask if there are two different numbers x , y x, y x,y bring 1 ≤ x < y ≤ m 1 ≤ x < y ≤ m 1≤x<y≤m And n n nmod x x x= n n nmod y y y.
【 Input format 】
Input contains groups of independent queries .
The first line contains an integer T Indicates the number of groups queried .
Next T T T Each line contains two integers n , m n, m n,m, Separate... With a space , A group of questions .
【 Output format 】
Output T T T That's ok , Each row in turn corresponds to the results of a set of queries . If there is , Output words Yes; If it doesn't exist , Output words No.
【 The sample input 】
3
1 2
5 2
999 99
【 Sample output 】
No
No
Yes
【 Evaluate use case size and conventions 】
about 20 % 20\% 20% The evaluation case of , T ≤ 100 , n , m ≤ 1000 T ≤ 100 ,n, m ≤ 1000 T≤100,n,m≤1000;
about 50 % 50\% 50% The evaluation case of , T ≤ 10000 , n , m ≤ 1 0 5 T ≤ 10000 ,n, m ≤ 10^5 T≤10000,n,m≤105;
For all profiling use cases , 1 ≤ T ≤ 1 0 5 , 1 ≤ n ≤ 1 0 9 , 2 ≤ m ≤ 1 0 9 1 ≤ T ≤ 10^5 ,1 ≤ n ≤ 10^9 ,2 ≤ m ≤ 10^9 1≤T≤105,1≤n≤109,2≤m≤109.
【 Thought analysis 】
There is no clever solution , Direct violence , It's estimated that it's hard to pass the customs .
【 Reference code 】
C.py (Gitee.com)C.py (github.com)
【 Problem description 】
Xiaolan likes to calculate how much memory space the variables defined in her code occupy recently . To simplify the problem , There are only three types of variables ：
int： Integer variables , One int Type variable occupancy 4 Byte Of memory space .
long： Long integer variables , One long Type variable occupancy 8 Byte Of memory space .
String： String variable , The occupied space is related to the string length , Set the string length to L, Then the string occupies L Byte Of memory space , If the string length is 0 Take up 0 Byte Of memory space .
There are only two forms of statements that define variables , The first form is ：
type var1=value1,var2=value2…;
It defines a number of type Type variable var1、var2、…, And use value1、value2… initialization , Use... Between multiple variables , Separate , Statement to ; ending ,type May be int、long or String. for example int a=1,b=5,c=6; The occupied space is 12 Byte;long a=1,b=5; The occupied space is 16 Byte;String s1=””,s2=”hello”,s3=”world”;
The occupied space is 10 Byte.
The second form is ：
type[] arr1=new type[size1],arr2=new type[size2]…;
Defined several type One dimensional array variable of type arr1、arr2…, And the size of the array is size1、size2…, Use... Between multiple variables , separation , Statement to ; ending ,type Can only be int or long. for example int[] a1=new int[10]; The occupied memory space is 40 Byte;long[] a1=new long[10],a2=new long[10]; The occupied memory space is 160 Byte.
Xiaolan is known to have T Statements defining variables , Please help him count how much memory space is used . The result is expressed as ：aGBbMBcKBdB, among a、b、c、d Results for statistics ,GB、MB、KB、B In units of . Give priority to large units ,1GB=1024MB, 1MB=1024KB,1KB=1024B, among B Express Byte. If a、b、c、d Some numbers in are 0, Then it is not necessary to output these numbers and their units . The title ensures that there is only one sentence defining variables in a row , And each statement meets the definition format described in the question stem , All variable names are legal and do not duplicate . The data in the title is very regular , Similar to the example given above , Except that there is a space after the type , And when defining an array new After a space , No extra space will appear .
【 Input format 】
The first line of input contains an integer T T T, Express T T T A statement defined by a variable . Next T T T That's ok , Each line contains a variable definition statement .
【 Output format 】
The output line contains a string , Represents the total size of space occupied by all statements .
【 The sample input 1】
1
long[] nums=new long[131072];
【 Sample output 1】
1MB
【 The sample input 2】
4
int a=0,b=0; long x=0,y=0;
String s1=”hello”,s2=”world”;
long[] arr1=new long[100000],arr2=new long[100000];
【 Sample output 2】
1MB538KB546B
【 Sample explanation 】
Examples 1, The space occupied is 131072 × 8 = 1048576 B 131072 × 8 = 1048576 B 131072×8=1048576B, After conversion, it happens to be 1MB, The other three units GB、KB、B The preceding figures are 0 , So there is no need to output .
Examples 2, The space occupied is 4 × 2 + 8 × 2 + 10 + 8 × 100000 × 2 B 4 × 2 + 8 × 2 + 10 + 8 × 100000 × 2 B 4×2+8×2+10+8×100000×2B, After conversion, it is 1MB538KB546B.
【 Evaluate use case size and conventions 】
For all profiling use cases , 1 ≤ T ≤ 10 1 ≤ T ≤ 10 1≤T≤10, The length of each variable definition statement will not exceed 1000 1000 1000. All variable names will not be longer than 10 10 10, They are all composed of lowercase letters and numbers . For integer variables , Initialized values are decimal integers within their representation range , The initialized value will not be a variable . about String Variable of type , The initialized content length will not exceed 50 50 50, And the content only contains lowercase letters and numbers , The initialized value will not be a variable . For array type variables , The length of the array is an integer , The scope is ： [ 0 , 2 30 ] [0, 2^{30}] [0,230], The length of the array is not a variable . T T T The total memory space occupied by variables defined by statements will not exceed 1 GB, And greater than 0 B.
【 Thought analysis 】
At first glance, this question is quite frightening , It takes up a lot of 3 page , Because my first two blank filling questions take up a lot of time , It's starting to panic , When we get to this question, let's look at it , I think it's cold , This is the second programming problem. Is it so difficult? But I read the problem carefully , It's not hard to find , Just follow the topic , Thanks to the Python It is very convenient to manipulate strings , So I can save a lot of effort for this problem .
Ideas as follows ：
First, you should calculate how much the current expression takes up Byte, And the variable name in the expression 、=、 keyword new These are independent variables , Just ignore it
Get the input single line expression , Use input().split(maxsplit=1) Get the input separated by the first space , It is mainly used to judge the leftmost data type if '[]' in typ
If the type is array , Note that the array only has int and long：
int[] arr = new int[3]; take 3） Multiply by the length of the corresponding variable and add If the type is normal , You need to make an additional judgment String：
String： Direct regularization ”.+?” matching ”, Note that in the sample title, this is a Chinese characters . After all values are matched, the length can be added directly .String： direct .count(',') Calculation , The length of , The ratio of the number of variables , A large number 1, Then multiply by the corresponding length and add .Output the total length in the required format ：
def convertSize(byte):
size = {
'GB': 0, 'MB': 0, 'KB': 0, 'B': 0}
if byte >= 1073741824:
size['GB'] = byte // 1073741824
byte %= 1073741824
if byte >= 1048576:
size['MB'] = byte // 1048576
byte %= 1048576
if byte >= 1024:
size['KB'] = byte // 1024
byte %= 1024
size['B'] = byte
return size
def printSize(l):
size = convertSize(l)
ans = ''
# Normally, you can traverse the dictionary directly , But I'm not sure about the exam environment 3.8 Whether the dictionaries in are in order .3.9 It must be orderly in the future
if size['GB'] > 0:
ans += f'{
size["GB"]}GB'
if size['MB'] > 0:
ans += f'{
size["MB"]}MB'
if size['KB'] > 0:
ans += f'{
size["KB"]}KB'
if size['B'] > 0:
ans += f'{
size["B"]}B'
print(ans)
【 Reference code 】
D.py (Gitee.com)D.py (github.com)
【 Problem description 】
Little blue has a length of n n n Array of A = ( a 1 , a 2 , ⋅ ⋅ ⋅ , a n ) A = (a_1, a_2, · · · , a_n) A=(a1,a2,⋅⋅⋅,an), A subarray of an array is defined as an array consisting of one or more consecutive elements selected from the original array . The greatest common divisor of an array refers to the greatest common divisor of all elements in the array . If you change at most one element in the array , The maximum common divisor of the array is g, So called g For the approximation of this array GCD. An approximation of an array GCD
There may be multiple values .
Concrete , Judge g Whether it is an approximation of a subarray GCD as follows ：
Xiao Lan wants to know , Array A How many have a length greater than or equal to 2 The subarray of satisfies the approximation GCD The value of is g.
【 Input format 】
The first line of input contains two integers n, g, Separate... With a space , Each represents an array A Length and g Value .
The second line contains n It's an integer a 1 , a 2 , ⋅ ⋅ ⋅ , a n a_1, a_2, · · · , a_n a1,a2,⋅⋅⋅,an, Two adjacent integers are separated by a space .
【 Output format 】
The output line contains an array of integers A How many have a length greater than or equal to 2 Approximation of subarray of GCD The value of is g .
【 The sample input 】
5 3
1 3 6 4 10
【 Sample output 】
5
【 Sample explanation 】
The subarray satisfying the condition has 5 individual ：
[ 1 , 3 ] [1, 3] [1,3]： take 1 It is amended as follows 3 after , The greatest common divisor of this subarray is 3 , Meet the conditions .
[ 1 , 3 , 6 ] [1, 3, 6] [1,3,6]： take 1 It is amended as follows 3 after , The greatest common divisor of this subarray is 3 , Meet the conditions .
[ 3 , 6 ] [3, 6] [3,6]： The greatest common divisor of this subarray is 3 , Meet the conditions .
[ 3 , 6 , 4 ] [3, 6, 4] [3,6,4]： take 4 It is amended as follows 3 after , The greatest common divisor of this subarray is 3 , Meet the conditions .
[ 6 , 4 ] [6, 4] [6,4]： take 4 It is amended as follows 3 after , The greatest common divisor of this subarray is 3, Meet the conditions .
【 Evaluate use case size and conventions 】
about 20 % 20\% 20% The evaluation case of , 2 ≤ n ≤ 1 0 2 2 ≤ n ≤ 10^2 2≤n≤102;
about 40 % 40\% 40% The evaluation case of , 2 ≤ n ≤ 1 0 3 2 ≤ n ≤ 10^3 2≤n≤103;
For all profiling use cases , 2 ≤ n ≤ 1 0 5 , 1 ≤ g , a i ≤ 1 0 9 2 ≤ n ≤ 10^5 ,1 ≤ g, a_i ≤ 10^9 2≤n≤105,1≤g,ai≤109.
【 Thought analysis 】
Although the question is gcd, But and gcd It doesn't really matter ...
It is mainly to divide subarray , If there are only at most... In the subarray 1 The number is not g Factor of . Then this subarray satisfies the condition , Because it can be modified at will , There is no need to pay attention to changing the value .
【 Reference code 】
E.py (Gitee.com)E.py (github.com)
【 Problem description 】
Xiao Lan likes it very much owo , He now has some strings , He wants to put these strings together , Make as many as possible appear in the final string owo .
When calculating the quantity , Allow characters to overlap , namely owowo The calculation for the 2 individual ,owowowo The calculation for the 3 individual .
Please figure out how many strings are there in the optimal case owo.
【 Input format 】
The first line of input contains an integer n , Indicates the number of strings owned by Xiaolan . Next n That's ok , Each line contains a string of lowercase letters si .
【 Output format 】
Output n That's ok , Each line contains an integer , Before presentation i String can be obtained in the optimal splicing scheme owo The number of .
【 The sample input 】
3
owo w ow
【 Sample output 】
1
1
2
【 Evaluate use case size and conventions 】
about 10 % 10\% 10% The evaluation case of , n ≤ 10 n ≤ 10 n≤10;
about 40 % 40\% 40% The evaluation case of , n ≤ 300 n ≤ 300 n≤300;
about 60 % 60\% 60% The evaluation case of , n ≤ 5000 n ≤ 5000 n≤5000;
For all profiling use cases , 1 ≤ n ≤ 1 0 6 , 1 ≤ ∣ s i ∣ , ∣ s i ∣ ≤ 1 0 6 1 ≤ n ≤ 10^6 ,1 ≤ |s_i| , |s_i| ≤ 10^6 1≤n≤106,1≤∣si∣,∣si∣≤106, among ∣ s i ∣ |s_i| ∣si∣ Representation string s i s_i si The length of .
【 Thought analysis 】
Although this question is 25 Minute question , But with Python To do it , It's not hard ,, Blind guessing should use a moving gauge , But time is running out , There is no time to push , I chose to do it by direct violence . Violence is all arranged , The time complexity is extremely high . Although the title gives 10s,, But I guess I still can't pass .
owo, This more ingenious method is direct regularization 'owo' matching , But a regular character can only be matched once , But the title requirements o You can use it twice , So directly .replace('o','oo'), Put each oitertools.permutations() Generate full permutations , Recycle looking for maximum owo Most arrays .【 Complete code 】
I.py (Gitee.com)I.py (github.com)
【 Problem description 】
Given a string containing only lowercase letters s, Select an interval for each operation [ l i , r i ] [l_i, r_i] [li,ri] take s All letters in the interval of x i x_i xi Replace all with letters y i y_i yi, Ask after all the operations are finished , What is the resulting string .
【 Input format 】
The first line of input contains a string s . The second line contains an integer m .
Next m That's ok , Each row contains 4 Parameters l i , r i , x i , y i l_i, r_i, x_i, y_i li,ri,xi,yi, Two adjacent parameters are separated by a space , among l i , r i l_i, r_i li,ri Integers , x i , y i x_i, y_i xi,yi It's lowercase .
【 Output format 】
The output line contains a string representing the answer .
【 The sample input 】
abcaaea 4
1 7 c e
3 3 e b
3 6 b e
1 4 a c
【 Sample output 】
cbecaea
【 Evaluate use case size and conventions 】
about 40 % 40\% 40% The evaluation case of , ∣ s ∣ , m ≤ 5000 |s|, m ≤ 5000 ∣s∣,m≤5000;
For all profiling use cases , 1 ≤ ∣ s ∣ , m ≤ 1 0 5 , 1 ≤ l i ≤ r i ≤ ∣ s ∣ , x i ≠ y i 1 ≤ |s|, m ≤ 10^5 ,1 ≤ l_i ≤ r_i ≤ |s| ,x_i \not= y_i 1≤∣s∣,m≤105,1≤li≤ri≤∣s∣,xi=yi, among |s| Representation string s The length of .
【 Thought analysis 】
This question is even simpler than the previous one , I think it needs to be optimized , Look at the time 10s. Just follow the topic .
【 Complete code 】
J.py (Gitee.com)J.py (github.com)
This is the end of what you've done , The remaining three questions have not been worked out , Please give me your advice .
【 Problem description 】
LQ The city's transportation system can be seen as composed of n A node and m A directed graph consisting of directed edges . There is a signal light on each side , Will continue to press green, yellow, red, yellow, green, yellow, red, yellow … The order of the cycle ( It turns green at the beginning )
. When the signal light is green, it is allowed to pass in a positive direction , Reverse traffic is allowed at red lights , No passage is allowed when the light is yellow . The duration of the three colors of the signal lights on each side are independent of each other , The duration of the yellow light is equal to the time taken to complete the path . When you come to one side , It is necessary to observe the signal lamp on the side , If traffic is allowed, you can pass through this side , It is no longer affected by the signal light during the passage ; Otherwise you need to wait , Until passage is allowed .
Please tell me about the slave node s To the node t What is the minimum time required , If s Cannot reach t The output −1.
【 Input format 】
The first line of input contains four integers n , m , s , t n, m, s, t n,m,s,t, Two adjacent integers are separated by a space . Next m That's ok , Each line contains five integers u i , v i , g i , r i , d i u_i, v_i, g_i, r_i, d_i ui,vi,gi,ri,di
, Two adjacent integers are separated by a space , Each represents the starting point of an edge , End , A green light 、 The duration and distance of the red light （ The duration of the yellow light ）.
【 Output format 】
The output line contains an integer representing the slave node s arrive t The shortest time required .
【 The sample input 】
4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1
【 Sample output 】
11
【 Evaluate use case size and conventions 】
about 40% The evaluation case of , n ≤ 500 , 1 ≤ g i , r i , d i ≤ 100 n ≤ 500 ,1 ≤ g_i, r_i, d_i ≤ 100 n≤500,1≤gi,ri,di≤100;
about 70% The evaluation case of , n ≤ 5000 n ≤ 5000 n≤5000;
For all profiling use cases , 1 ≤ n ≤ 100000 , 1 ≤ m ≤ 200000 , 1 ≤ s , t ≤ n , 1 ≤ u i , v i ≤ n , 1 ≤ g i , r i , d i ≤ 1 0 9 1 ≤ n ≤ 100000 ,1 ≤ m ≤ 200000 ,1 ≤ s, t ≤ n ,1 ≤ u_i, v_i ≤ n ,1 ≤ g_i, r_i, d_i ≤ 10^9 1≤n≤100000,1≤m≤200000,1≤s,t≤n,1≤ui,vi≤n,1≤gi,ri,di≤109.
【 Thought analysis 】
emmm, To tell the truth , I didn't understand the questions ..
【 Problem description 】
Xiaolan has recently become fascinated by a product called 《 Lighten up 》 A puzzle game , The game is in a n × n
On a checkerboard , The chessboard is made up of black and white squares , Players place light bulbs on the white grid , Make sure that any two bulbs do not shine on each other , Until the white grid on the whole chessboard is lit （ Each puzzle is a unique solution ）. The bulb only emits light in the horizontal and vertical directions , Illuminate entire rows and columns , Unless its light is blocked by a black grid . On the black grid, there may be
0 To 4 Integer number , It means that there are several bulbs in the four adjacent white grids above, below, left and right ; There may also be no numbers , This means that the bulb can be placed in any of the four adjacent white grids . The goal of the game is to choose the right place to place the light bulb , Make the white grid on the whole chessboard be illuminated .
for example , There is a black grid where the number is 4, This means that there must be 4 A light bulb , Need to be on his 、 Next 、 Left 、 Place one bulb on the right ; If the number in a black box is 2, Its upper, lower, left and right adjacent grids only have 3
The first one is white , Then you need to select two of the three white boxes to place the bulb ; If a black box is not marked with numbers , And its upper, lower, left and right adjacent grids are all white grids , Then you can start from here 4 Choose from any of the white squares 0 to 4 To place the light bulb .
The title guarantees that the data given is legal , There must be a place around the black grid where the corresponding number of bulbs can be placed . And ensure that the solutions of all puzzles are unique .
Now? , Give an initial chessboard situation , Please put the light bulb on it , Make the white grid on the whole chessboard be lit .
【 Input format 】
The first line of input contains an integer n, Indicates the size of the chessboard .
Next n That's ok , Each row contains n Characters , Represents a given chessboard . character . Indicates that the corresponding grid is white , Numeric character 0、1、2、3、4 It represents a black grid with digital identification , Capital X Indicates a black grid without a digital ID .
【 Output format 】
Output n That's ok , Each row contains n Characters , Answer . Capital O Indicates that the corresponding grid contains bulbs , The meaning of other characters is the same as that of input .
【 The sample input 】
5
.....
.2.4.
..4..
.2.X.
.....
【 Sample output 】
...O.
.2O4O
.O4O.
.2OX.
O....
【 Sample explanation 】
The chessboard layout corresponding to the answer is shown in the following figure ：
【 Evaluate use case size and conventions 】
For all profiling use cases , 2 ≤ n ≤ 5 2 \le n \le 5 2≤n≤5, And there are at least 15 15% 15 The grid is black .
【 Thought analysis 】
Deep search ？ Dynamic gauge ？？ Can't ,, But for the time being , Almost write blasting
【 Problem description 】
Xiaolan is going to buy n Items , Each item requires 1 individual .
Xiaolan lives near a total of m A shop , Every shop sells all kinds of goods .
The first i The store will s i s_i si Tianzhidi t i t_i ti Day discount , The discount rate is p i p_i pi, For the original is b The items , The price after discount is ⌊ b ⋅ p j 100 ⌋ \lfloor \frac{b·p_j}{100} \rfloor ⌊100b⋅pj⌋. At other times, you need to buy at the original price .
Xiao Lan is very busy , He can only choose one day to purchase these items . Excuse me, , How much does it cost him at least to buy everything he needs .
The title guarantees that Xiaolan will be able to buy all the items she needs .
【 Input format 】
The first line of input contains two integers n, m, Separate... With a space , It represents the number of items and the number of stores respectively .
Next, include the description of each store in turn . Each store consists of several lines , The first line contains four integers s i , t i , p i , c i s_i, t_i, p_i, c_i si,ti,pi,ci, Two adjacent integers are separated by a space , Indicates the start and end time of the store offer respectively 、 The discount rate and the total number of items in the store . After that c i c_i ci
That's ok , Each line contains two integers a j , b j a_j, b_j aj,bj, Separate... With a space , Respectively represent the No. of the store j The type and price of each item . The type of commodity is determined by 1 to n Number .
【 Output format 】
The output line contains an integer indicating the minimum amount of money that Xiaolan needs to spend .
【 The sample input 】
2 2
1 2 89 1
1 97
3 4 77 1
2 15
【 Sample output 】
101
【 Evaluate use case size and conventions 】
about 40% The evaluation case of , n , m ≤ 500 , s i ≤ t i ≤ 100 , c i ≤ 2000 n, m ≤ 500 ,s_i ≤ t_i ≤ 100 , c_i ≤ 2000 n,m≤500,si≤ti≤100,ci≤2000;
about 70% The evaluation case of , n , m ≤ 5000 , c i ≤ 20000 n, m ≤ 5000 , c_i ≤ 20000 n,m≤5000,ci≤20000;
For all profiling use cases , 1 ≤ n , m ≤ 100000 , 1 ≤ c i ≤ n , c i ≤ 400000 , 1 ≤ s i ≤ t i ≤ 1 0 9 , 1 < p i < 100 , 1 ≤ a j ≤ n , 1 ≤ b j ≤ 1 0 9 1 ≤ n, m ≤ 100000 ,1 ≤ ci ≤ n , ci ≤ 400000 ,1 ≤ s_i ≤ t_i ≤ 10^9 ,1 < p_i < 100 ,1 ≤ a_j ≤ n ,1 ≤ b_j ≤ 10^9 1≤n,m≤100000,1≤ci≤n,ci≤400000,1≤si≤ti≤109,1<pi<100,1≤aj≤n,1≤bj≤109.
【 Thought analysis 】
It's another difficult question to read ,, But blind guessing should be similar to the knapsack problem .
