Welcher Artikel?

Ich habe versucht, die Algorithmen aufzulisten, die bei Wettkampfprofis verwendet werden können.

* Von Zeit zu Zeit aktualisiert

Primzahlurteil (Sieben von Elatostines)

https://atcoder.jp/contests/abc084/tasks/abc084_d


from itertools import accumulate
import math
m = 10**5

L = [x for x in range(2,m+1)]

#Extrahieren Sie Primzahlen mit einem Eratostenes-Sieb
for y in range(2, int(math.sqrt(m)+1)):
    L = [z for z in L if(z == y or z % y != 0)]

#N+1/Extrahieren Sie, was 2 auch eine Primzahl ist
P = []
for w in L:
    if (w+1)/2 in L:
        P.append(w)

#Erstellt für die kumulative Summe
G = [0] * (m+1)
for i in P:
    G[i+1] = 1

#Kumulative Summe
Q = list(accumulate(G))



n = int(input())
for _ in range(n):
    s, t = map(int, input().split())
    print(Q[t+1]-Q[s])




'''
Die folgenden Primzahlen sind langsam.
Verwenden Sie das Eratostenes-Sieb wie oben

def isPrime(n):

    if n == 1:
        return False
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)+1), 2):
        if n % i == 0:
            return False
    return True

'''

Bitdynamische Planungsmethode (Patrouillenverkäuferproblem)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

v, e = map(int, input().split())

inf = 10**7
edges = [[inf]*v for _ in range(v)]

for i in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

#Dp sind die minimalen Kosten in S, wenn die Reihenfolge unter der Bedingung optimiert wird, dass v die letzte für die Teilmenge S der gesamten Menge ist.
dp = [[inf]*v for _ in range(2**v)]
dp[0][0] = 0

#Set (Binärzahl, die angibt, ob besucht oder nicht)
for x in range(2**v):
    #Zuletzt besuchter Knoten
    for y in range(v):
        #Andere Knoten als die zuletzt besuchten
        for z in range(v):
            #1.Ob Sie bereits 2 besucht haben.Ist es nicht der zuletzt besuchte Knoten 3?.Sind y und z überhaupt verbunden?
            if ((x >> y) & 1) and y != z and edges[z][y] < 10**6:
                dp[x][y] = min(dp[x][y], dp[x^(1<<y)][z]+edges[z][y])

if dp[-1][0] > 10**6:
    print(-1)
else:
    print(dp[-1][0])

Problem der kürzesten Route (Bellmanford-Methode)

Ich habe auf [hier] verwiesen (https://qiita.com/takayg1/items/92fb138683ac72b47d86). Auch die Erklärung zu Bellman Ford war im Artikel hier leicht zu verstehen.


#v:Peak e:Seite
v, e = map(int, input().split())
#Liste zum Speichern von Kanten (weder benachbarte Matrix noch benachbarte Liste)
edges = []

for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append([s, t, w])
    # edges.append([t, s, w])

#Weniger als,Bellmanford
def bellman_ford(start,goal,edges,v):
    #Entfernungsinitialisierung
    distance = [float("inf")] * v
    distance[start] = 0
    
    for i in range(v):
        #Ob die Entfernung aktualisiert wurde
        updated = False
        for s, t, w in edges:
            if distance[t] > distance[s] + w:
                distance[t] = distance[s] + w
                updated = True
        #Der Nachweis, dass die kürzeste Route gefunden wird, wenn die Entfernung nicht mehr aktualisiert wird
        if not updated:
            break
        #Selbst wenn es v-mal aktualisiert wird, endet die Aktualisierung der kürzesten Route nicht → Es liegt eine negative Schließung vor
        if i == v - 1:
            return -1
    return distance[goal]

for i in range(v):
    print(bellman_ford(0, i, edges, v))