ABC D Problem
Ein Problem, um das D-Problem zu üben
Richtlinie
Die Suche nach Primzahlen ist $ O {(\ sqrt {N})} $
Beim Finden eines Bruchs (Faktorzerlegung) auch $ O {(\ sqrt {N})} $
Implementierung
Primzahlsuche nach i im Bereich (int (math.sqrt (N)) +1)
Maximales Engagement ist die euklidische gegenseitige Teilung "A, B = B, A% B"
Denken Sie daran, den ungeteilten Wert beim Faktorisieren zum Bruch hinzuzufügen
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) #Vergessen Sie nicht, die verbleibende Zahl in den Bruch aufzunehmen
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.heappop (heap), um den Minimalwert mit dem negativen Element zu extrahieren.
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))
Richtlinie
Gruppen gruppieren, die in die gleiche Richtung weisen
Menschen, die zusammen gruppiert sind, sind glücklich
Drehen Sie die Person ganz links nach links. (Wenn Sie nach rechts abbiegen, wird es vollständig umgekehrt)
Die Person ganz links ist unglücklich
Wenn komprimiert, ist LRLR ... eine alternierende Liste, so dass die Häufigkeit, mit der R invertiert werden kann, * 2 die Anzahl der glücklichen Erhöhungen ist.
Beachten Sie jedoch, dass die Anzahl aufeinanderfolgender Zeilen, wenn alle Rs in L invertiert sind, wenn das rechte Ende L ist und R um 1 abweicht.
Implementierung
Das Zählen der Anzahl glücklicher Personen nach dem Komprimieren der Liste kann durch numerische Berechnung gestoppt werden, indem die Anzahl der Elemente in gerade oder ungerade Zahlen und die Anzahl der Operationen geteilt wird, die ausgeführt werden können, ohne dass eine invertierte Liste erstellt werden muss. Es ist schneller, weil Sie die Liste nicht umblättern müssen.
def compress(arr):
"""Die Person, die komprimiert und verschwunden ist, ist glücklich"""
cnt_h = 0
new_arr = []
comp_arr = ['L']
#Setzen Sie zuerst den Anfang auf L. Diese Drehung ist nicht möglich
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
#Zählen Sie Komprimierungsvorgänge und komprimierte Abfälle
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):
#Anzahl der Operationen, die erforderlich sind, um alle Grenzen umzukehren
max_rotation = len(arr)//2
#Es endet, wenn alle zu L werden oder die Anzahl der Inversionen K erreicht
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 )
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)]
#Erstellen Sie eine Verknüpfungsbeziehung für ungerichtete Diagramme (einschließlich Upstream-Verbindungen).
for a, b in tree_list:
a, b = int(a)-1, int(b) -1
linked_node_list[a].append(b) #Kind hinzufügen
linked_node_list[b].append(a) #Eltern hinzufügen
for index, val in query_list_int:
val_list[index-1] += val
stack = [0] #Generieren Sie einen Stapel mit dem Wert des Stammknotens und speichern Sie das zu überwachende Ziel
parent = [0] * (N+1) #Speichert einen Stapel, in dem besuchte Knoten gespeichert sind
#Wenn Sie eine rekursive Funktion verwenden, bleiben Sie im Speicherlimit stecken. Führen Sie sie daher nacheinander mit while aus
#Verwenden Sie LIFO im Stapel. Da es sich um ein LIFO handelt, können Sie nach Tiefe suchen, während Sie die jüngste Person betrachten.
#Erinnere dich an den übergeordneten Knoten und versuche zu spielen
#Wenn Sie es mit einem gerichteten Diagramm definieren, müssen Sie das übergeordnete Element nicht spielen
while True:
#Patrouille in der Reihenfolge von der Route
v=stack.pop()
for child in linked_node_list[v]:
if child != parent[v]:
parent[child] = v #Speichern Sie die besuchten Knoten
stack.append(child) #Speichern Sie den Verbindungszielknoten dieses Knotens v im Stapel
val_list[child] += val_list[v] #Kumulative Summe
if not stack:
#Die Patrouille endet, wenn der Stapel aufgebraucht ist
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])
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