- 2022-06-09 16:49
*views 5*- algorithm
- Blue Bridge Cup
- Python

<>A beautiful 2

answer ：563

res = 0 for i in range(1, 2021): if '2' in str(i): res += 1 print(res) # 563

<>B Composite number

Simulation is enough

answer ：1713

def check(n): for i in range(2, n): if n % i == 0: return True return False res

= 0 for i in range(1, 2021): if check(i): res += 1 print(res) # 1713

<>C Factorial divisor

thinking ： Need a little math

Any positive integer n Can be expressed as the product of several primes ： n = p 1 a 1 ∗ p 2 a 2 ∗ . . ∗ p k a k n=p_{1}

^{a_{1}}*p_{2} ^{a_{2}}*...*p_{k} ^{a_{k}}n=p1a1∗p2a2∗...∗pkak

about number individual number = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ . . ∗ ( a k + 1 )

Approximate number =(a_{1}+1)*(a_{2}+1)*...*(a_{k}+1) Approximate number =(a1+1)∗(a2+1)∗...∗(ak+1)

answer ：39001250856960000

from math import * def isPrime(n): for i in range(2, floor(sqrt(n))+1): if n %

i== 0: return False return True fac = {} n = 100 for i in range(2, n+1): tmp =

i num= 2 while tmp > 1: while tmp % num == 0: fac[num] = fac.get(num, 0) + 1 tmp

//= num num += 1 while not isPrime(num): num += 1 res = 1 for key, value in list

(fac.items()): res *= value+1 print(res) # 39001250856960000

<>D Essential ascending sequence

thinking ： dynamic programming , Similar to the classical longest non descending subsequence , structure dp Array representation in i Number of subsequences ending with characters , For each character in the string , Traverse all characters before it , If the current character is larger than the previous one , Meet incremental requirements , Plus the previous quantity ; If less than , Ignore ; If equal to , Because the current one is longer than the previous one , So the current one contains the previous one , To subtract the number of previous duplicates .

answer ：3616159

s =

"tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl"

dp= [1]*len(s) # dp[i] Indicates that the i Number of subsequences ending with characters for i in range(1, len(s)): for j in

range(i): if s[i] > s[j]: dp[i] += dp[j] if s[i] == s[j]: dp[i] -= dp[j] #

Subtract the part that repeats the previous part print(sum(dp)) # 3616159

<>E paper serpent

thinking ： Deep search , No fixed starting point , So search every square as a starting point , Note that the next search will restore the status of the previous starting point .

answer ：552

def dfs(x, y, current): global res if current > 16: res += 1 return for i in

range(4): tx, ty = x+dx[i], y+dy[i] if 0 <= tx < 4 and 0 <= ty < 4 and graph[tx]

[ty] == 0: graph[tx][ty] = current dfs(tx, ty, current+1) graph[tx][ty] = 0 res

= 0 graph = [[0]*4 for _ in range(4)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] for

iin range(4): for j in range(4): graph[i][j] = 1 dfs(i, j, 2) graph[i][j] = 0

print(res) # 552

<>F Tian Gan Di Zhi

【 Problem description 】

Ancient China used the heavenly stems and earthly branches to record the current year .

There are ten Heavenly Stems , Respectively ： nail （jiǎ）, B （yǐ）, C （bǐng）, Ding （dīng）, Amyl

（wù）, Oneself （jǐ）, Geng （gēng）, Symplectic （xīn）, Union （rén）, Kui （guǐ）.

There are twelve Earthly Branches in all , Respectively ： son （zǐ）, ugly （chǒu）, Yin （yín）, Mao （mǎo）, Chen （chén）, Already （sì）, Noon （wǔ）, not （wèi）, Shen （shēn）, Unitary （yǒu）, Xu （xū）, Hai （hài）.

Connect the heavenly stems and Earthly Branches , It forms a year of heavenly stems and Earthly Branches , for example ： Jia Zi .2020 Year is the year of gengzi .

Every year , Both heavenly stems and earthly branches will move to the next one . for example 2021 Year is Xin Chou year .

Every pass 60 year , Tianganhui cycle 6 round , Dizhihui cycle 5 round , So the heavenly stems and Earthly Branches record every year 60 Once a year . for example 1900 year ,1960 year ,2020 Years are all gengzi years .

Given a year , Please output the tiangan dizhi year of this year .

【 Input format 】

The input line contains a positive integer , Indicates the year of A.D .

【 Output format 】

Output a Pinyin , Indicates the year of tiangan dizhi , Both heavenly stems and earthly branches are represented in small Pinyin （ Does not indicate tone ）, Do not add any extra characters between .

【 sample input 】

2020

【 sample output 】

gengzi

【 Scale and agreement of evaluation cases 】

For all profiling cases , The year of A.D. entered is not more than 9999 Positive integer of .

thinking ：

There is a calculation method about the heavenly stems and Earthly Branches ：

（ particular year - 3）%10 To Heavenly Stems ： as 1894-3=1891 ,1891 divide 10 The remainder is 1 Is a ;

（ particular year - 3）%12 Epididymal branch ： as 1894-3=1891 ,1891 divide 12 The remainder is 7 It is noon , Namely 1894 Year is the year of Jiawu .

be careful ： If subscript from 0 You have to subtract from the beginning 4

But most people don't know this calculation method , What should I do ? In the title 2020 Year is the year of gengzi , take 2020 Mold once 60 obtain 40, So A.D 40 Year is also the year of gengzi , Take this as the starting point and walk through it according to the law to get a mold 60 Mapping table after , The code is as follows ：

year = int(input()) tiangan = ['jia', 'yi', 'bing', 'ding', 'wu', 'ji', 'geng',

'xin', 'ren', 'gui'] dizhi = ['zi', 'chou', 'yin', 'mao', 'chen', 'si', 'wu',

'wei', 'shen', 'you', 'xu', 'hai'] table = ['']*60 table[40] = tiangan[6]+dizhi[

0] # Ad 40 Year is the year of gengzi , Build table based on this , And the subscripts of Geng and Zi are 6 and 0 i, j = 7, 1 cnt = 41 while cnt != 40: table

[cnt] = tiangan[i]+dizhi[j] i = (i+1) % 10 j = (j+1) % 12 cnt = (cnt+1) % 60

print(table[year % 60]) # 100%

<>G Duplicate string

【 Problem description 】

If a string S Can be exactly repeated by a string K Times get , We call it S yes K Repeated string . for example “abcabcabc” Can be seen as “abc” repeat 3

Times get , therefore “abcabcabc” yes 3 Repeated string .

Same reason “aaaaaa” since 2 Repeated string , again 3 Repeated strings and 6 Repeated string .

Now give a string S, Please calculate the minimum number of characters to be modified , Can make S Become one K Secondary string ?

【 Input format 】

The first line of input contains an integer K.

The second line contains a string containing only lowercase letters S.

【 Output format 】

Output an integer to represent the answer . If S Cannot be modified to K Repeated string , output 1.

【 sample input 】

2

aabbaa

【 sample output 】

2

【 Scale and agreement of evaluation cases 】

For all profiling cases ,1 ≤ K ≤ 100000, 1 ≤ |S | ≤ 100000. among |S | express S of

length .

thinking ： Split string into k paragraph , Assume each paragraph m Characters , We count the number of occurrences of each character in the same position of each segment , Every paragraph is counted , Each location （0 ~

m-1） Take the character with the most occurrences as the character to be changed , Just change the character of the corresponding position of each paragraph into this character , Because this character appears most at this position , Other characters can be changed to this character to ensure the minimum number of times , If it becomes another character , Then the characters with the most occurrences will change a lot , Not the optimal solution . Accumulate each position （0

~ m-1） Up conversion times is the answer .

k = int(input()) s = input() if k > len(s): print(-1) else: res = 0 length =

len(s)//k for i in range(length): dic = {} for j in range(k): word = s[j*length+

i] dic[word] = dic.get(word, 0)+1 d = list(dic.items()) d.sort(key=lambda x: x[1

], reverse=True) res += k-d[0][1] print(res) # 100%

<>H answering question

【 Problem description 】

have n Students asked the teacher to answer questions at the same time . Each student estimated in advance the time for answering questions .

The teacher can arrange the order of answering questions , Students should enter the teacher's office in turn to answer questions .

The process of a student answering questions is as follows ：

First enter the Office , No i Students' needs si Time in milliseconds .

Then the students ask questions and the teacher answers them , No i Students' needs ai Time in milliseconds .

After Q & A , Students are very happy , Will send a message in the course group , The time required can be ignored .

Finally, the students packed up and left the Office , need ei Time in milliseconds . General needs 10 second ,

20 Seconds or 30 second , Namely ei Value is 10000,20000 or 30000.

After a classmate left the Office , Then the next student can enter the Office .

Answer questions from 0 Time to start . The teacher wants to arrange the order of answering questions reasonably , Make the students in the course group

The sum of message sending moments inside is the smallest

【 Input format 】

The first line of input contains an integer n, Indicates the number of students .

next n that 's ok , Describe each student's time . Of which No i Line contains three integers si, ai, ei, meaning

Meaning as above .

【 Output format 】

Output an integer , Indicates the minimum sum of the moments when students send messages in the course group .

【 sample input 】

3

10000 10000 10000

20000 50000 20000

30000 20000 30000

【 sample output 】

280000

【 Example description 】

according to 1, 3, 2 Sequential Q & A , The time of sending messages is 20000, 80000, 180000.

【 Scale and agreement of evaluation cases 】

about 30% Evaluation case for ,1 ≤ n ≤ 20.

about 60% Evaluation case for ,1 ≤ n ≤ 200.

For all profiling cases ,1 ≤ n ≤ 1000,1 ≤ si ≤ 60000,1 ≤ ai ≤ 1000000, ei ∈ {10000, 20000,

30000}, Namely ei By all means 10000,20000,30000 one of .

thinking ： Use the greedy idea to simply sort

if a stay b front , be a The time required is a of si+a of ei,b The time required is sum(a)+b of si+b of ei

if b stay a front , Same reason , Just compare the two . Although there are several items that will be asked out when they are poor , Equivalent to sum(a) and sum(b) compare , But it's easier to understand .

The code is as follows ：

from functools import cmp_to_key def cmp(a, b): ta = a[0]+a[1]+sum(a)+b[0]+b[1]

# a stay b front , Total time for two tb = b[0]+b[1]+sum(b)+a[0]+a[1] # b stay a front , Total time for two return ta-tb n =

int(input()) time = [] for _ in range(n): time.append(list(map(int, input().

split()))) time.sort(key=cmp_to_key(cmp)) res = 0 clock = 0 for s, a, e in time:

clock+= s+a res += clock clock += e print(res) # 100%

<>I supply

【 Problem description 】

Xiao Lan is a helicopter pilot , He is responsible for the n

Villages delivering supplies . Every month , He has to go to every village at least once , Can be more than once , Deliver the materials needed by the village . Every village happens to have a heliport , The distance between each two villages is exactly the straight-line distance between the villages .

Due to the limited fuel tank size of the helicopter , The distance of Xiaolan's single flight cannot exceed

D. Every heliport has a gas station , Can fill up the helicopter . Every month , Xiaolan starts from the headquarters , Return to the headquarters after delivering materials to each village . If convenient , Xiaolan can also pass through the headquarters to refuel .

Headquartered at 1 Village of . Excuse me? , To complete a month's task , How long will Xiaolan fly at least ?

【 Input format 】

The first line of input contains two integers n, D, Number of villages and distance of a single flight .

next n Line describes the location of the village , Of which No i Line two integers x i , y i x_{i},y_{i} xi,yi, Indicates that the number is i of

Coordinates of the village . village i And villages j The distance between is ( x i − x j ) 2 + ( y i − y j ) 2

\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}(xi−xj)2+(yi−yj)2 .

【 Output format 】

Output one line , Contains a real number , Round to keep exact 2 Decimal places , Indicates the answer .

【 sample input 】

4 10

1 1

5 5

1 5

5 1

【 sample output 】

16.00

【 Example description 】

The four villages form a square shape .

【 sample input 】

4 6

1 1

4 5

8 5

11 1

【 sample output 】

28.00

【 Example description 】

The replenishment sequence is 1 → 2 → 3 → 4 → 3 → 2 → 1.

【 Scale and agreement of evaluation cases 】

For all profiling cases ,1 ≤ n ≤ 20, 1 ≤ xi, yi ≤ 104, 1 ≤ D ≤ 105.

thinking ：Floyd+ Pleomorphic pressure dp

In the Blue Bridge Cup practice system ,python Version can only be 80%（ overtime ）,c++ The same idea can be passed

from math import * def getDistance(x, y): return sqrt(pow(location[x][0]-

location[y][0], 2)+pow(location[x][1]-location[y][1], 2)) n, d = map(int, input(

).split()) location = [tuple(map(int, input().split())) for _ in range(n)] w = [

[float('inf')]*n for _ in range(n)] # w[i][j] express i Village and j The shortest distance between villages No # Adjacency Matrix Building for i

in range(n): for j in range(n): dis = getDistance(i, j) if dis <= d: w[i][j] =

dis# Floyd algorithm for k in range(n): for i in range(n): for j in range(n): w[i][j] =

min(w[i][j], w[i][k]+w[k][j]) # dp[i][j] Indicates in status i lower , from 0 No. village to j The shortest record of Village No dp = [[float(

'inf')]*n for _ in range(1 << n)] dp[1][0] = 0 for i in range(1, 1 << n): # Enumeration status

for j in range(n): # Enumerate villages if i >> j & 1 == 1: # If j No. village status is 1 for k in range(n): if

(i-(1 << j)) >> k & 1: # If except j The status of the remaining villages on the 1st is 1 dp[i][j] = min(dp[i][j], dp[i - (1 <<

j)][k]+w[k][j]) res = float('inf') for i in range(n): #

Enumerate the last village from which to return to the starting point , The last village visited res = min(res, dp[(1 << n)-1][i]+w[i][0]) print(

'{:.2f}'.format(res)) # 80%

<>J Blue jump

【 Problem description 】

Xiao Lan made a robot , Named blue jump , Because the robot basically walks

By jumping .

Blue jump can jump , You can also turn around . The distance of each step of blue jump must be an integer , You can skip no more than k Length of . Because the balance of blue jump is not well designed , If two consecutive times

It's all jumping , And both jumps are at least p, Then blue jump will fall , This is what Xiao Lan doesn't want to see .

Xiao Lan has received a special task , In a L

Show blue jump on stage . Xiao Lan wants to control LAN Tiao to walk from the left to the right of the stage , Then turn around , Then go from right to left , Then turn around , Then go from left to right , Then turn around , Then go from right to left , Then turn around , So back and forth . To make the viewer not too boring , Xiaolan decides to let lantiao walk in different ways each time . Xiao Lan records the distance of each step of blue jump , Line up in order , Obviously, the number of this column does not exceed

k And and yes L. This way, a list of numbers will come out . If the length of two columns is different , Or there is a different position value in the two columns , It's a different plan .

I would like to ask LAN Tiao if he doesn't fall down , How many different ways to go from one side of the stage to the other .

【 Input format 】

The input line contains three integers k, p, L.

【 Output format 】

Output an integer , Indicates the answer . The answer may be big , Please output the answer divided by 20201114 Remainder of .

【 sample input 】

3 2 5

【 sample output 】

9

【 Example description 】

Blue jump has the following 9 Seed jumping method ：

1+1+1+1+1

1+1+1+2

1+1+2+1

1+2+1+1

2+1+1+1

2+1+2

1+1+3

1+3+1

3+1+1

【 sample input 】

5 3 10

【 sample output 】

397

【 Scale and agreement of evaluation cases 】

about 30% Evaluation case for ,1 ≤ p ≤ k ≤ 50,1 ≤ L ≤ 1000.

about 60% Evaluation case for ,1 ≤ p ≤ k ≤ 50,1 ≤ L ≤ 109.

about 80% Evaluation case for ,1 ≤ p ≤ k ≤ 200,1 ≤ L ≤ 1018.

For all profiling cases ,1 ≤ p ≤ k ≤ 1000,1 ≤ L ≤ 1018.

Technology

Daily Recommendation

views 5

views 3

©2019-2020 Toolsou All rights reserved,

Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms （java code ） use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?