python
#Bodenbelag
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)
#Beschleunigen Sie, indem Sie Notizen zum Array machen
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
#Stapel(LIFO)
s = deque([])
s.append(1)
s.append(2)
s.append(3)
print(s.pop(), s)
print(s.pop(), s)
print(s.pop(), s)
#Warteschlange(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 Richter nach Feststellung dieses Zustands
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
Im folgenden Code wird das Ganze jedes Mal sortiert, wenn die Liste aktualisiert wird, sodass der Rechenaufwand zuzunehmen scheint. Gibt es eine Möglichkeit, gut zu sortieren, indem Sie sich nur auf das Ende der Liste konzentrieren?
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())
#Eine Funktion, die den optimalen Wert aus dem i-ten und den nachfolgenden Elementen sowie das Gewicht von j oder weniger berechnet
memo = [[0]*((MW)+1) for k in range(n+1)]
#opt(i,j)Ist nach dem i-th(i+1~)Maximaler Wert bei Auswahl von kleiner oder gleich 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))
Ein Problem, bei dem ich große Probleme hatte. Achten Sie auf den Index der obigen Liste, der die Bedeutung dessen versteht, was opt darstellt! !! !!
n = int(input())
m = int(input())
s = input()
t = input()
#dp[a][b]Ich meine,(a,b)Maximalwert in Kombination von Zeichenfolgen mit einer Länge
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())
Es ist wichtig, eine schrittweise Formel zu formulieren, tatsächlich mit einer kleinen Zahl zu berechnen und mit dem Index Tsuji übereinzustimmen.
Damit beträgt der Berechnungsbetrag 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]ist 0~Bei der Auswahl der Elemente bis zum i-ten, so dass das Gesamtgewicht j oder weniger beträgt
Stellt den Maximalwert dar
'''
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 mit verbessertem Berechnungsbetrag (transformierte Graduierungsformel) (siehe Arimoto S.59) Berechnungsbetrag 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]ist 0~Bei der Auswahl der Elemente bis zum i-ten, so dass das Gesamtgewicht j oder weniger beträgt
Stellt den Maximalwert dar
'''
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())
Es ist notwendig, eine schrittweise Formel unter Berücksichtigung des Rechenaufwands zu formulieren.
n = int(input())
a = list(map(int, input().split()))
m = list(map(int, input().split()))
K = int(input())
#Array-Wiederverwendung
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]Teilt j in i, die Anzahl der Straßen
'''
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)
'''
Es gibt auch eine Methode, um Push und Pop zusammen zu machen (dies ist schneller)
Achten Sie auf die Reihenfolge von Push und 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 = []
#Fügen Sie der Liste Ziele hinzu
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)
Ich habe versucht, den Umfang der Berechnung des im Kapitel der Gier-Methode gelösten Problems mit heapQue zu verbessern
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)
Diese Seite ist leicht zu verstehen
[Diese Seite](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) ist leicht zu verstehen & Ich durfte mich beziehen
#Union Find
#Ich suche die Wurzeln eines Baumes
def find(x,par):
if par[x] == x:
return x
else:
return find(par[x],par)
#Zusammenführen von Mengen, zu denen x und y gehören
def unite(x,y,par,rank):
x = find(x,par)
y = find(y,par)
if x != y:
#Wenn die Menge, zu der x und y gehören, unterschiedlich ist
if rank[x] < rank[y]:
par[x] = y
else:
par[y] = x
if rank[x]==rank[y]:
rank[x] += 1
#Bestimmen, ob x und y zu derselben Menge gehören
def same(x,y,par):
return find(x,par) == find(y,par)
########################################
n = 7
par = [] #Elternteil
rank = [] #Baumtiefe
#Initialisieren
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)Erstellen Sie eine Gruppe von
unite(0,1,par,rank)
unite(0,4,par,rank)
unite(3,5,par,rank)
unite(5,6,par,rank)
#1 und 2,Beurteilung, ob 3 und 5 gleich sind
print(same(1,2,par))
print(same(3,5,par))
#Zusammenführung von A und B.
unite(4,2,par,rank)
#Beurteilung, ob 1 und 2 gleich sind
print(same(1,2,par))
[Ausgabe]Die Kommentare sind ergänzend.
#A(0,1,4) B(2) C(3,5,6)Erstellen Sie eine Gruppe von
#1 und 2,Beurteilung, ob 3 und 5 gleich sind
False
True
#Zusammenführung von A und B.
#Beurteilung, ob 1 und 2 gleich sind
True
Es verwendet die Tiefenprioritätssuche.
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
'''
Möglicherweise ist der betreffende Baum nicht verkettet.
Sie müssen sich also nacheinander jeden Scheitelpunkt ansehen, um festzustellen, ob er bereits gezeichnet ist.
'''
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")
Wir werden es von Zeit zu Zeit aktualisieren.
Recommended Posts