The exam was hard ...... First of all, write down the title of the meeting , No, I will write again
【 Problem description 】
The recurrence formula of Fibonacci sequence is ：Fn = Fn-1＋ Fn-2, among F1= F2 = 1.
Excuse me, , Fibonacci Series No 1 to 202202011200 term ( contain ) in , How many items have a bit of 7.
【 Parsing and code 】
The number of operations on this problem is about 1e11, and Python The number of operations that can be performed per second is about 8e7, Violent words may take more than ten minutes
Solving Fibonacci series , The more traditional method is recursion , But recursion can easily explode , So suggest for Cycle solution
It's easy to find a loop , answer ：26960268160
num = 202202011200
f1 = f2 = 1
# Bit list
cycle = [1, 1]
for i in range(3, num):
# Fibonacci progression
f1, f2 = f2, f1 + f2
# Find a bit
f2 %= 10
cycle.append(f2)
# Find loop
if cycle[-2:] == cycle[:2]: break
# Remove the last two
cycle = cycle[:-2]
print(cycle)
# The length of the loop
cycle_len = len(cycle)
count_7 = cycle.count(7)
# num Just to be 60 to be divisible by
print(num % cycle_len)
result = num // cycle_len * count_7
# 26960268160
print(result)【 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 
. But there will be some errors when doing experiments , It will lead to some unexpected data , This error data y The range is 
. 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 ?
【 Parsing and code 】
In fact, finding out how many numbers in a file are prime numbers is just a matter of fact , Because the number is not big , It can be solved by trial division
When a given number n When , If n Is the sum , that n Must be [2, 
] Divide by an integer in , So we can write the prime function
Use open Function read txt file , Judge the number of each line , And output progress information
answer ：342693
from math import isqrt
def try_divide(n):
''' Trial division '''
if n <= 3: return n in [2, 3]
bound = isqrt(n)
for i in range(2, bound + 1):
if n % i == 0: return False
return True
cnt = 0
with open('primes.txt') as f:
lines = list(f.readlines())
for cur, i in enumerate(lines):
# Remove line breaks
i = int(i.strip())
if try_divide(i): cnt += 1
# Output progress
print(f'\r{(cur + 1) / len(lines) * 100:.2f} %', end='')
print()
# 342693
print(cnt)【 Problem description 】
Given n,m, Ask if there are two different numbers x,y bring 1 ≤ x < y ≤ m And n mod x = n mod y
【 Input format 】
Input contains groups of independent queries .
The first line contains an integer T Indicates the number of groups queried .
Next T Each line contains two integers n,m, Separate... With a space , A group of questions .
【 Output format 】
Output 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
【 Examples 】
Input Output3
1 2
5 2
999 99
【 Evaluate use case size and conventions 】
20%
50%
100%
【 Parsing and code 】
【 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, Express T A statement defined by a variable . Next 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
【 Examples 】
Input Output 1【 Evaluate use case size and conventions 】
For all profiling use cases ,1 ≤ T ≤ 10, The length of each variable definition statement will not exceed 1000. All variable names will not be longer than 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, 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], The length of the array is not a variable .T The total memory space occupied by variables defined by statements will not exceed 1 GB, And greater than 0 B.
【 Parsing and code 】
The idea is violence , Use re Regular expressions for string matching , Calculate the total memory space ：
import re
space = {'int': 4, 'long': 8}
byte = 0
for _ in range(int(input())):
sentence = input().rstrip(';').split()
type_ = sentence.pop(0)
# If it's an array
if type_[-2:] == '[]':
type_ = type_[:-2]
# Take out the statement block for statistics
for token in sentence:
find = re.search(r'\[[0-9]+]', token)
if find:
find = int(find.group()[1:-1])
byte += space[type_] * find
# If it's a normal variable
else:
sentence = sentence[0].split(',')
# The character type depends on the length of the string
if type_ == 'String':
for token in sentence:
find = re.search(r'=.*', token)
if find:
find = find.group()
# Remove the double quotation marks 、 Equal sign
# The length is bytes
byte += len(find[2: -1])
else:
# sentence There are as many variables as you can
byte += len(sentence) * space[type_]Use a dictionary to record the value corresponding to each unit , Write the total memory space after conversion , Use for Cyclic output
BASE = 2 ** 10
result = {unit: 0 for unit in ('GB', 'MB', 'KB', 'B')}
# Calculation GB
result['GB'] = byte // BASE ** 3
byte -= BASE ** 3 * result['GB']
# Calculation MB
result['MB'] = byte // BASE ** 2
byte -= BASE ** 2 * result['MB']
# Calculation KB
result['KB'] = byte // BASE
byte -= BASE * result['KB']
# Record B
result['B'] = byte
final = ''
for unit in result:
value = result[unit]
if value:
final += f'{value}{unit}'
print(final)【 Problem description 】
Little blue has a length of n Array of 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 ：
1. If the greatest common divisor of this subarray is g, It means that g Is its approximation GCD.
2. After modifying an element in this subarray （ You can change it to any value you want ）, The maximum common divisor of the subarray is g, It means that g Is an approximation of this subarray GCD.
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 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
【 Examples 】
Input Output explain 5 3【 Evaluate use case size and conventions 】
20%
40%
100%
【 Parsing and code 】
The law of approximate common divisor is as follows ：
Enumerate the left boundary of an interval , The number on the left boundary is taken as the initial maximum common divisor last_gcd：
Then enumerate the right boundary of the interval ：
from math import gcd
length, g = map(int, input().split())
array = list(map(int, input().split()))
cnt = 0
# Enumerate the left boundary
for left in range(length):
# Current greatest common divisor
last_gcd = array[left]
if last_gcd % g == 0:
is_change = False
else:
last_gcd = g
is_change = True
# Enumerate right borders
for right in range(left + 1, length):
cur_gcd = gcd(last_gcd, array[right])
# If at present gcd Can be g to be divisible by , Change any number to g Can then
if cur_gcd % g == 0:
cnt += 1
elif not is_change:
# Only modify the number in the current position to g
cur_gcd = gcd(last_gcd, g)
is_change = True
if cur_gcd == g:
cnt += 1
else:
break
last_gcd = cur_gcd
print(cnt)【 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, Two adjacent integers are separated by a space .
Next m That's ok , Each line contains five integers 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
【 Examples 】
Input Output 4 4 1 4【 Evaluate use case size and conventions 】
40%
70%
100%
【 Parsing and code 】
【 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
【 Examples 】
Input Output explain 5
【 Evaluate use case size and conventions 】
100%2 ≤ n ≤ 5 , And there are at least 15% The grid is black【 Parsing and code 】
【 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 si Tianzhidi ti Day discount , The discount rate is pi, For the original is b The items , The price after discount is 
. 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 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 ci That's ok , Each line contains two integers 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
【 Examples 】
Input Output2 2
1 2 89 1
1 97
3 4 77 1
2 15
【 Evaluate use case size and conventions 】
40%
70%
100%
【 Parsing and code 】
【 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
【 Examples 】
Input Output 31
1
2
【 Evaluate use case size and conventions 】
10%n ≤ 1040%n ≤ 30060%n ≤ 5000100%
【 Parsing and code 】
【 Problem description 】
Given a string containing only lowercase letters s, Select an interval for each operation [li,ri] take s All letters in the interval of xi Replace all with letters 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 li,ri, xi, yi, Two adjacent parameters are separated by a space , among li,ri Integers ,xi, yi It's lowercase .
【 Output format 】
The output line contains a string representing the answer
【 Examples 】
Input Output abcaaea【 Evaluate use case size and conventions 】
40%
100%
【 Parsing and code 】
This question is so simple that I don't understand it in the final section —— also 25 branch , I haven't set aside time for this question , It was too late to do it when I saw it
Because the string cannot be modified in place , So use the slice expression to cut it into three segments , Character replacement of the middle segment , Then perform the splicing operation
string = input()
for _ in range(int(input())):
l, r, old, new = input().split()
l, r = map(lambda i: int(i) - 1, [l, r])
l_part, mid_part, r_part = string[:l], string[l: r + 1], string[r + 1:]
string = ''.join([l_part, mid_part.replace(old, new), r_part])
print(string)
