Problème ABC D
D pratique du problème
Politique
La recherche de nombres premiers est $ O {(\ sqrt {N})} $
Lors de la recherche d'une fraction (décomposition factorielle), $ O {(\ sqrt {N})} $
La mise en oeuvre
Recherche par nombre premier pour i dans la plage (int (math.sqrt (N)) +1)
L'engagement maximum est la division mutuelle euclidienne ʻA, B = B, A% B`
N'oubliez pas d'ajouter la valeur indivise à la fraction lors de l'affacturage
import math
A, B = [int(item) for item in input().split()]
def gdc(A, B):
if B == 0:
return A
else:
return gdc(B, A % B)
def chk_pn(num):
flag = True
if num <= 3:
pass
else:
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
flag = False
break
return flag
def mk_factor(num):
max_divisor = int(math.sqrt(num))+1
divisor = 2
factor_list = [1]
while divisor <= max_divisor:
if num % divisor == 0:
factor_list.append(divisor)
num /= divisor
else:
divisor += 1
factor_list.append(num) #N'oubliez pas d'inclure le nombre restant dans la fraction
return factor_list
GDC = gdc(A, B)
pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]
# print(pn_factor)
print(len(set(pn_factor)))
heapq.heapify (list)heapq.heappop (tas) pour extraire la valeur minimale avec l'élément négatif.heapq.heappush (tas, article)
import heapq as hp
N, M = [int(item) for item in input().split()]
price_list = sorted([-1 * int(item) for item in input().split()])
total_m = 0
def discount(price_list, ticket_num):
total_ticket =0
hp.heapify(price_list)
while total_ticket < ticket_num:
temp = hp.heappop(price_list)
hp.heappush(price_list, -1* (-1*temp//2))
total_ticket += 1
return price_list
res = discount(price_list, M)
print(res)
print(-1 * sum(res))
Politique
Groupes de groupes qui font face à la même direction
Les personnes regroupées sont heureuses
Tournez la personne la plus à gauche vers la gauche. (Si vous tournez vers la droite, il sera complètement inversé)
La personne à l'extrême gauche est malheureuse
Lorsqu'il est compressé, LRLR ... est une liste alternative, donc le nombre de fois que R peut être inversé * 2 est le nombre d'augmentations heureuses.
Cependant, notez que le nombre de lignes consécutives lorsque tous les R sont inversés en L lorsque l'extrémité droite est L et R s'écartera de 1.
La mise en oeuvre
Compter le nombre de personnes heureuses après avoir compressé la liste peut être arrêté par calcul numérique en divisant le nombre d'éléments en nombres pairs ou impairs et le nombre d'opérations pouvant être effectuées sans avoir à créer une liste inversée. C'est plus rapide car vous n'avez pas à retourner la liste.
def compress(arr):
"""La personne qui s'est comprimée et a disparu est heureuse"""
cnt_h = 0
new_arr = []
comp_arr = ['L']
#Dans un premier temps, définissez le début sur L. Cette rotation est interdite
if arr[0] == 'R':
for item in arr:
if item == 'L':
new_arr.append('R')
else:
new_arr.append('L')
prev_item = item
else:
new_arr = arr
#Compter les opérations de compression et les bribes compressées
for i in range(1, N):
if new_arr[i - 1] == new_arr[i]:
cnt_h += 1
else:
comp_arr.append(new_arr[i])
return [comp_arr, cnt_h]
def execute(arr, cnt_h, K):
#Nombre d'opérations nécessaires pour inverser toutes les limites
max_rotation = len(arr)//2
#Il se termine lorsque tout devient L ou que le nombre d'inversions atteint K
if max_rotation <= K:
cnt_h += len(arr) - 1
else:
cnt_h += 2*K
return cnt_h
N = int(input())
print((N-1)*N //2 )
.pop () et .append ()form collections import deque pour accélérer le traitement de la pile. C'est plus rapide pour mettre et sortir de la pointe et de l'arrière.N, Q = [int(item) for item in input().split()]
tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]
val_list = [0 for _ in range(N)]
linked_node_list = [[] for _ in range(N)]
#Créer une relation de lien pour les graphiques non dirigés (y compris les connexions en amont)
for a, b in tree_list:
a, b = int(a)-1, int(b) -1
linked_node_list[a].append(b) #Ajouter un enfant
linked_node_list[b].append(a) #Ajouter un parent
for index, val in query_list_int:
val_list[index-1] += val
stack = [0] #Générer une pile contenant la valeur du nœud racine et stocker la cible à patrouiller
parent = [0] * (N+1) #Stocke une pile qui stocke les nœuds visités
#Si vous utilisez une fonction récursive, vous serez bloqué dans la limite de mémoire, alors exécutez-la séquentiellement avec while
#Utilisez LIFO dans la pile. Puisqu'il devient un LIFO, vous pouvez rechercher de la profondeur tout en regardant le plus jeune.
#Souvenez-vous du nœud parent et essayez de jouer
#Si vous le définissez avec un graphe orienté, vous n'avez pas besoin de jouer le parent
while True:
#Patrouiller dans l'ordre depuis la route
v=stack.pop()
for child in linked_node_list[v]:
if child != parent[v]:
parent[child] = v #Stocker les nœuds visités
stack.append(child) #Stocker le nœud de destination de connexion de ce nœud v dans la pile
val_list[child] += val_list[v] #Somme cumulée
if not stack:
#La patrouille se termine lorsque la pile est épuisée
break
print(*val_list)
from collections import deque
N, Q = [int(item) for item in input().split()]
tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]
class Node:
def __init__(self, val):
self.val = val
self.child_list = []
self.cnt = 0
class my_tree:
def __init__(self, tree_list):
self.node_list = []
for i in range(N):
self.node_list.append(Node(i+1))
for a, b in tree_list:
a, b = int(a), int(b)
child_node = self.node_list[b-1]
parent_node = self.node_list[a-1]
self.node_list[a-1].child_list.append(child_node)
self.node_list[b-1].child_list.append(parent_node)
def adding(self, query_list):
for a, data in query_list:
a, data = int(a), int(data)
self.node_list[a-1].cnt += data
stack = deque([self.node_list[0]])
parent_node_list = [self.node_list[0]]*(N + 1)
while True:
v = stack.pop()
for child in v.child_list:
if child != parent_node_list[v.val -1]:
child.cnt += v.cnt
parent_node_list[child.val -1] = v
stack.append(child)
if not stack:
break
ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])
sum être calculé dans l'instruction for, vous faites en fait une double boucle sans le savoir. Polnarev.
N = int(input())
A_list = [int(item) for item in input().split()]
all_sum = sum(A_list)
F_sum_list = [A_list[0]]
for j in range(1,N):
F_sum_list.append(F_sum_list[-1] + A_list[j])
delta_list = [abs(all_sum - 2* i) for i in F_sum_list]
print(min(delta_list))
A, B, X = [int(item) for item in input().split()]
res_list = []
left = 1 -1
right = 10 ** 9 + 1
is_search = True
while is_search:
N = (left + right)//2
res = A * N + B * len(str(N))
if res > X:
right = N
elif res <= X:
res_list.append(N)
left = N
if right - left <= 1:
is_search = False
if res_list == []:
print(0)
else:
print(max(res_list))
import math
A, B, X = [int(item) for item in input().split()]
res = 0
res_list = []
delta = 10**9 // 4
N= 10**9 // 2
is_search = True
while is_search:
res = A * N + B * len(str(N))
if res > X:
N = N -delta
elif res <= X:
res_list.append(N)
N = N + delta
if delta <= 0:
break
delta = delta // 2
new_res_list = []
for i in range(N - 1000, N + 1000):
res = A * i + B * len(str(i))
if res <= X:
new_res_list.append(i)
if new_res_list == [] or max(new_res_list) <1:
print(0)
else:
if 1<= max(new_res_list) < 10**9:
print(max(new_res_list))
else:
print(10**9)
Recommended Posts