python
#Sol
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)
#Accélérez en prenant des notes sur le tableau
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
#empiler(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 Jugez après avoir déterminé cet état
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
Dans le code ci-dessous, le tout est trié à chaque fois que la liste est mise à jour, donc la quantité de calcul semble augmenter. Existe-t-il un moyen de bien trier en se concentrant uniquement sur la fin de la liste?
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())
#Une fonction qui calcule la valeur optimale à partir du i-ème élément et des éléments suivants et le poids de j ou moins
memo = [[0]*((MW)+1) for k in range(n+1)]
#opt(i,j)Est après le i-ème(i+1~)Valeur maximale lorsqu'elle est sélectionnée pour être inférieure ou égale à 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))
Un problème que j'ai eu beaucoup de mal à résoudre. Attention à l'index de la liste ci-dessus qui comprend la signification de ce que représente opt! !! !!
n = int(input())
m = int(input())
s = input()
t = input()
#dp[a][b]Je veux dire,(a,b)Valeur maximale en combinaison de chaînes de caractères de longueur
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())
Il est important de formuler une formule graduelle, de calculer en fait avec un petit nombre et de faire correspondre l'indice Tsuji.
Avec cela, la quantité de calcul sera 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]vaut 0~Lors de la sélection des articles jusqu'au i-ème afin que le poids total soit j ou moins
Représente la valeur maximale
'''
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 avec montant de calcul amélioré (formule progressive transformée) (voir Arimoto P.59) Montant de calcul 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]vaut 0~Lors de la sélection des articles jusqu'au i-ème afin que le poids total soit j ou moins
Représente la valeur maximale
'''
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())
Il est nécessaire de formuler une formule progressive en tenant compte du montant du calcul.
n = int(input())
a = list(map(int, input().split()))
m = list(map(int, input().split()))
K = int(input())
#Réutilisation des baies
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]Divise j en i, le nombre de rues
'''
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)
'''
Il existe également une méthode pour pousser et pop ensemble (c'est plus rapide)
Faites attention à l'ordre de push et 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 = []
#Ajouter des objectifs à la liste
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)
J'ai essayé d'améliorer la quantité de calcul du problème résolu dans le chapitre de la méthode gourmande utilisant 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)
Cette page est facile à comprendre
[Cette 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) est facile à comprendre & J'ai été autorisé à référencer
#Union Find
#À la recherche des racines d'un arbre
def find(x,par):
if par[x] == x:
return x
else:
return find(par[x],par)
#Fusion d'ensembles auxquels appartiennent x et y
def unite(x,y,par,rank):
x = find(x,par)
y = find(y,par)
if x != y:
#Quand l'ensemble auquel appartiennent x et y est différent
if rank[x] < rank[y]:
par[x] = y
else:
par[y] = x
if rank[x]==rank[y]:
rank[x] += 1
#Déterminer si x et y appartiennent au même ensemble
def same(x,y,par):
return find(x,par) == find(y,par)
########################################
n = 7
par = [] #parent
rank = [] #Profondeur de l'arbre
#Initialisation
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)Créer un groupe de
unite(0,1,par,rank)
unite(0,4,par,rank)
unite(3,5,par,rank)
unite(5,6,par,rank)
#1 et 2,Juger si 3 et 5 sont le même ensemble
print(same(1,2,par))
print(same(3,5,par))
#Fusion de A et B
unite(4,2,par,rank)
#Juger si 1 et 2 sont le même ensemble
print(same(1,2,par))
[production]Les commentaires sont complémentaires.
#A(0,1,4) B(2) C(3,5,6)Créer un groupe de
#1 et 2,Juger si 3 et 5 sont le même ensemble
False
True
#Fusion de A et B
#Juger si 1 et 2 sont le même ensemble
True
Il utilise la recherche de priorité de profondeur.
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
'''
Peut-être que l'arbre donné en question n'est pas concaténé.
Vous devez donc regarder chaque sommet tour à tour pour voir s'il est déjà peint.
'''
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")
Nous le mettrons à jour de temps en temps.
Recommended Posts