python
#Factorial
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
#Fibonacci
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
#Speed up by memoizing the array
def fib_memo(n):
memo = [0] * (n+1)
def fib_cal(x):
if x <= 1:
memo[x] = x
return x
elif memo[x] != 0:
return memo[x]
else:
memo[x] = fib_cal(x-2) + fib_cal(x-1)
return memo[x]
return fib_cal(n)
print(fib_memo(40))
python
from collections import deque
#stack(LIFO)
s = deque([])
s.append(1)
s.append(2)
s.append(3)
print(s.pop(), s)
print(s.pop(), s)
print(s.pop(), s)
#queue(FIFO)
q = deque([])
q.append(1)
q.append(2)
q.append(3)
print(q.popleft())
print(q.popleft())
print(q.popleft())
n = int(input())
k = int(input())
a = list(map(int, input().split()))
def dfs(i, sum):
#n Judge after determining this state
if i == n:
return sum == k
if dfs( i+1 , sum):
return True
if dfs( i+1, sum+a[i]):
return True
return False
if dfs(0,0):
print("Yes")
else:
print("No")
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
queue = deque([[sy,sx]])
visited[sy][sx] = 0
while queue:
y, x = queue.popleft()
if [y, x] == [gy, gx]:
return visited[y][x]
for j,k in ([1,0], [-1,0], [0,1], [0,-1]):
new_y, new_x = y+j, x+k
if (maze[new_y][new_x] == ".") and (visited[new_y][new_x] == -1):
visited[new_y][new_x] = visited[y][x] + 1
queue.append([new_y, new_x])
if __name__ == "__main__":
R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1
maze = [input() for i in range(R)]
visited = [[-1]*C for j in range(R)]
print(bfs(maze, visited, sy, sx, gy, gx))
Input = list(map(int, input().split()))
c_list = Input[:6]
A = Input[6]
c = [1, 5, 10, 50, 100, 500]
num = 0
for i in range(5):
j = 5 - i
t = min( A // c[j], c_list[j])
A -= t * c[j]
num += t
print(num)
N = int(input())
Start = list(map(int, input().split()))
End = list(map(int, input().split()))
from operator import itemgetter
span = sorted([(Start[i], End[i]) for i in range(N)], key=itemgetter(1))
ans = 0
last = 0
for m in range(N):
if span[m][0] > last:
last = span[m][1]
ans += 1
print(ans)
N = int(input())
S = input()
T = ""
for i in range(N):
S_rev = S[::-1]
if S >= S_rev:
T += S[-1]
S = S[:-1]
else:
T += S[0]
S = S[1:]
print(T)
Saruman's Army
N = int(input())
R = int(input())
X = list(map(int, input().split()))
ans = 0
last_posi = 0
while X[last_posi] + R <= X[-1]:
k = last_posi
while X[k] < X[last_posi] + R:
k += 1
last_posi = k
ans += 1
print(ans)
Fence repair
In the code below, the whole is sorted every time the list is updated, so the amount of calculation seems to increase. Is there a way to sort well by focusing only on the end of the list?
n = int(input())
l = list(map(int, input().split()))
ans = 0
while len(l) > 1:
l.sort(reverse=True)
new_l = l.pop() + l.pop()
ans += new_l
l.append(new_l)
print(ans)
n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())
#A function that calculates the optimum value from the i-th and subsequent items and the weight of j or less
memo = [[0]*((MW)+1) for k in range(n+1)]
#opt(i,j)Is after the i-th(i+1~)Maximum value when selected to be less than or equal to j
def opt(i, j):
if memo[i][j] != 0:
return memo[i][j]
if i == n:
res = 0
elif j < w[i]:
res = opt(i+1, j)
else:
res = max(opt(i+1,j) , opt(i+1,j-w[i]) + v[i])
memo[i][j] = res
return res
print(opt(0,MW))
A problem that I had a lot of trouble getting through. Be careful with the index in the list above, with a good understanding of what opt represents! !! !!
n = int(input())
m = int(input())
s = input()
t = input()
#dp[a][b]I mean,(a,b)Maximum value for a combination of strings of length
dp = [[0]*(m+1) for k in range(n+1)]
def cal_match():
dp[0][0] = dp[0][1] = dp[1][0] = 0
for i in range(0,n):
for j in range(0,m):
if s[i] == t[j]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
return dp[n][m]
print(cal_match())
It is important to formulate a recurrence formula, actually calculate with a small number, and match the index's Tsuji.
With this, the amount of calculation becomes O (n * MW ^ 2).
n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())
'''
dp[i+1][j]is 0~When selecting the items up to the i-th so that the total weight is j or less
Represents the maximum value
'''
dp = [[0] * ((MW+1)) for t in range(n+1)]
for s in range(MW):
dp[0][s] = 0
def opt():
for i in range(0,n):
for j in range(MW+1):
for k in range(0, (j // w[i]) + 1):
dp[i+1][j] = max(dp[i+1][j], dp[i][j - k * w[i]] + k * v[i])
return dp[n][MW]
print(opt())
Version with improved computational complexity (transformed recurrence formula) (see Arimoto P.59) Computational complexity O (n * MW)
n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())
'''
dp[i+1][j]is 0~When selecting the items up to the i-th so that the total weight is j or less
Represents the maximum value
'''
dp = [[0] * ((MW+1)) for t in range(n+1)]
for s in range(MW):
dp[0][s] = 0
def opt():
for i in range(0,n):
for j in range(MW+1):
if (j < w[i]):
dp[i + 1][j] = dp[i][j]
else:
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
return dp[n][MW]
print(opt())
It is necessary to formulate a recurrence formula in consideration of the amount of calculation.
n = int(input())
a = list(map(int, input().split()))
m = list(map(int, input().split()))
K = int(input())
#Array reuse
dp = [-1] * (K+1)
dp[0] = 0
for i in range(n):
for j in range(K+1):
if dp[j] >= 0:
dp[j] = m[i]
elif j < a[i] or dp[j-a[i]] <= 0:
dp[j] = -1
else:
dp[j] = dp[j-a[i]] - 1
if dp[K] >= 0:
print("Yes")
else:
print("No")
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(0,n):
dp[i] = 1
for j in range(0,i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(dp[n-1])
n = int(input())
m = int(input())
M = int(input())
'''
dp[i][j]Divides j into i, the number of streets
'''
dp = [[0] * (n+1) for k in range(m+1)]
dp[0][0] = 1
for i in range(1,m+1):
for j in range(n+1):
if j >= i:
dp[i][j] = (dp[i][j-i] + dp[i-1][j]) % M
else:
dp[i][j] = dp[i-1][j]
print(dp[m][n])
import heapq as hq
a = [5,3,2,1,6,13,4,12,14,9,10]
hq.heapify(a)
print(a)
hq.heappush(a, 7)
print(a)
hq.heappop(a)
print(a)
'''
There is also a method to do push and pop together (this is faster)
Pay attention to the order of push and pop
'''
print(hq.heappushpop(a, 11))
print(a)
print(hq.heapreplace(a,1))
print(a)
Expedition
import heapq as hq
N,L,P = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
pos = 0
tank = P
gas_station = []
#Add goals to the list
A.append(L)
B.append(0)
for i in range(N):
dis = A[i] - pos
while dis > tank:
if(len(gas_station) == 0):
ans = -1
break
L = [k * -1 for k in gas_station]
tank += hq.heappop(L) * (-1)
ans += 1
if ans == -1:
break
pos = A[i]
tank -= dis
hq.heappush(gas_station, B[i])
print(ans)
I tried to improve the computational complexity of the problem solved in the chapter of the greedy algorithm using heapQue.
import heapq as hq
n = int(input())
l = list(map(int, input().split()))
ans = 0
while len(l) > 1:
hq.heapify(l)
new_l = hq.heappop(l) + hq.heappop(l)
ans += new_l
l.append(new_l)
print(ans)
This page is easy to understand
[This page](https://juppy.hatenablog.com/entry/2018/11/08/%E8%9F%BB%E6%9C%AC_python_Union-Find%E6%9C%A8_%E7%AB%B6% E6% 8A% 80% E3% 83% 97% E3% 83% AD% E3% 82% B0% E3% 83% A9% E3% 83% 9F% E3% 83% B3% E3% 82% B0) is easy to understand &I was allowed to reference
#Union Find
#Seeking the roots of a tree
def find(x,par):
if par[x] == x:
return x
else:
return find(par[x],par)
#Merge of sets to which x and y belong
def unite(x,y,par,rank):
x = find(x,par)
y = find(y,par)
if x != y:
#When the set to which x and y belong is different
if rank[x] < rank[y]:
par[x] = y
else:
par[y] = x
if rank[x]==rank[y]:
rank[x] += 1
#Determining if x and y belong to the same set
def same(x,y,par):
return find(x,par) == find(y,par)
########################################
n = 7
par = [] #parent
rank = [] #Tree depth
#Initialization
for i in range(n):
#par[i]:i rank[i]:0
par.append(i)
rank.append(0)
#A(0,1,4) B(2) C(3,5,6)Create a group of
unite(0,1,par,rank)
unite(0,4,par,rank)
unite(3,5,par,rank)
unite(5,6,par,rank)
#1 and 2,Judgment whether 3 and 5 are the same set
print(same(1,2,par))
print(same(3,5,par))
#Merge of A and B
unite(4,2,par,rank)
#Judgment whether 1 and 2 are the same set
print(same(1,2,par))
[output]The comments are supplementary.
#A(0,1,4) B(2) C(3,5,6)Create a group of
#1 and 2,Judgment whether 3 and 5 are the same set
False
True
#Merge of A and B
#Judgment whether 1 and 2 are the same set
True
It uses a depth-first search.
n, w = map(int, input().split())
g = [[] for i in range(n)]
for k in range(w):
x, y = map(int, input().split())
g[x].append(y)
g[y].append(x)
color = [0] * n
def dfs(v, c):
color[v] = c
for j in g[v]:
if color[j] == c:
return False
elif color[j] == 0 and (not dfs(j,-c)):
return False
return True
'''
Perhaps the tree given in question is not concatenated.
So you need to look at each vertex in turn to see if it's already painted.
'''
k = 1
for i in range(n):
if color[i] == 0:
if not dfs(i, 1):
k = -1
if k == 1:
print('Yes')
else:
print("No")
We will update it from time to time.
Recommended Posts