- 2022-03-27 14:36
*views 12*- Python
- Algorithm
- Blue Bridge Cup

<>A card

cards = [2021]*10 i = 1 while True: s = str(i) for j in s: cards[int(j)] -= 1

flag= False for j in cards: if j < 0: flag = True break if flag: break i += 1

print(i-1) # 3181

<>B straight line

cnt = 0 dots = [(i, j) for i in range(20) for j in range(21)] # Generate all points lines =

set() for i in range(len(dots)): for j in range(i+1, len(dots)): if dots[j][0]-

dots[i][0] != 0: x1, x2 = dots[i][0], dots[j][0] y1, y2 = dots[i][1], dots[j][1]

k= (y2-y1)/(x2-x1) b = (y1*(x2-x1)-x1*(y2-y1))/(x2-x1) # It won't explode lines.add((k,

b)) print(len(lines)+20) # 40257

<>C Cargo placement

from math import * n = 2021041820210418 cnt = 0 fac = [] for i in range(1, int(

sqrt(n))+1): if n % i == 0: fac.append(i) fac.append(n//i) for i in fac: for j

in fac: for k in fac: if i*j*k == n: cnt += 1 print(cnt) # 2430

<>D route

from math import * n = 2021 vis = [False]*(n+1) dis = [float('inf')]*(n+1)

graph= [[float('inf') for i in range(n+1)] for j in range(n+1)] for i in range(1

, n+1): for j in range(1, n+1): if abs(i-j) > 21: continue graph[i][j] = lcm(i,

j) dis[1] = 0 while True: point = 0 for i in range(1, n+1): if (not vis[i]) and

dis[i] < dis[point]: point = i if point == 0: break vis[point] = True for i in

range(1, n+1): if dis[i] > dis[point]+graph[point][i]: dis[i] = dis[point]+graph

[point][i] print(dis[n]) # 10266837

<>E Loop count

answer ：881012367360

thinking ： Shape pressure dp, can't dp It is suggested to take a look at the bit operation first

First, use an adjacency matrix e To indicate whether there is traffic between two teaching buildings ,e[i][j]=True express i Number and j The number is passable , Otherwise you can't pass . utilize gcd Function to find the greatest common factor of two numbers （ The principle is generalized Euclidean division ）, if it is 1 Representative coprime , That is, it can pass .

Set a two-dimensional array f,f[i][j] Indicates in the state i Xiacong 1 No. to j Number of schemes . Here is the meaning of state ： altogether 21 A teaching building , corresponding 21 Binary bits , Someone is 1 Indicates access to the corresponding teaching building , Otherwise, it is not accessed , Easy to know state i The maximum value is

2 21 − 1 2^{21}-1221−1.

because 1 No. and all other numbers are coprime , therefore 1 The number is connected to everything else . Title requirements from 1 Start on the th, walk through all the teaching buildings, and finally return to 1 number , That is, the state i On all binary bits of 1, The decimal system is 2

21 − 1 2^{21}-1221−1, It may be remembered as a. go back to 1 No. I can get from 2 Number return , Also available from 3 number ,4 number ,……,21 Number return . So this is the final total 20 Cumulative sum of returns ：

∑ j = 2 21 f [ a ] [ j ] \sum_{j=2}^{21}f[a][j] j=2∑21f[a][j]

For a particular state i,21 There are two binary bits 0 have 1. For each of them 1, The representative visits the corresponding teaching building , So from which teaching building did you come to this teaching building ? Nature is from others 1 Corresponding teaching building , The premise is that the two teaching buildings should be connected , This requires the previous adjacency matrix e Yes , The following statement omits the premise of China Unicom for convenience . So when the state transitions ,f[i][j]（j Represents i Someone on 1 Number of the corresponding teaching building ） Add all the others 1 Bitwise f[i][j]（ this j And the one in front j Not the same , It represents others 1 The number of the teaching building corresponding to the binary bit of ）. For a state i, Each binary bit 1 It could be from others 1 Yes, for the past , So we need to traverse the state i Binary all 1, For everyone 1 Carry out the above state transition operations .

The code is as follows , Run a little slower ：

def gcd(x, y): if x % y == 0: return y return gcd(y, x % y) n = 21 m = 1 << n e

= [[False]*n for _ in range(n)] # 1-21 The number of is mapped to 0-20 f = [[0]*n for _ in range(m)]

# f[i][j] Indicates in the state i Xiacong 1 No. to j Number of schemes # Status refers to whether the teaching building of the corresponding bit under the binary system is accessed or not , The status is changed to decimal i for i in range(n):

for j in range(n): if gcd(i+1, j+1) == 1: e[i][j] = True f[1][0] = 1 #

initialization , In state 1 Next from the third 0 From the first teaching building to the second 0 The number of programs for each teaching building is 1 for i in range(1, m): for j in range(n): if (i >>

j) & 1 == 1: # Ensure that the status is accessible j No for k in range(n): if ((i-(1 << j)) >> k) & 1 == 1

and e[k][j]: f[i][j] += f[i-(1 << j)][k] ans = 0 for i in range(1, n): ans += f[

m-1][i] print(ans) # 881012367360

<>F Time display

time = int(input()) time %= 24*60*60*1000 h = time//(60*60*1000) time -= h*60*

60*1000 m = time//(60*1000) time -= m*60*1000 s = time//1000 print(

"{:0>2d}:{:0>2d}:{:0>2d}".format(h, m, s))

<>G Yang Hui triangle

def generate(tri): tmp = [1] for i in range(len(tri)-1): tmp.append(tri[i]+tri[

i+1]) tmp.append(1) return tmp n = int(input()) res = 0 tri = [1] while True: if

nin tri: res += tri.index(n)+1 break res += len(tri) tri = generate(tri) print(

res) # Run timeout ,40 branch

<>H Left brother

There may be the following 3 species ( Only listed here 3 species , Not all ) different “ Left child right brother ” express ：

n = int(input()) tree = [[] for i in range(n+1)] for i in range(2, n+1): tree[

int(input())].append(i) def dfs(i): if len(tree[i]) == 0: return 0 maxn = 0 for

jin tree[i]: maxn = max(maxn, dfs(j)) return len(tree[i])+maxn print(dfs(1)) #

90 branch

<>I Exclusive or sequence

<>J Bracket sequence

Technology

- Java296 blogs
- Python265 blogs
- Vue125 blogs
- C Language122 blogs
- Algorithm108 blogs
- MySQL96 blogs
- Flow Chart84 blogs
- JavaScript79 blogs
- More...

Daily Recommendation

views 397

views 8

©2020-2024 ioDraw All rights reserved