Füllen Sie die JOI-Schwierigkeit 4 mit Python

Einführung

Verwenden Sie Python (PyPy), um Probleme mit JOI-Schwierigkeitsgrad 4 zu lösen. Informationen zu Problemen und Schwierigkeitsgraden finden Sie unter diese Website.

F-Schulroute

** Gedanken ** Lernen Sie anhand der Anzahl der Fälle Ich habe ein solches Diagramm in die Liste implementiert und es gelöst.

a, b = map(int,input().split())
n = int(input())
c = [list(map(int,input().split())) for _ in range(n)]

def solver(s,t,cons):
    m = [[0] * s for _ in range(t)] #Liste oben erklärt
    for i in range(s): #Fest an 1 an der Seitenkante
        for con in cons:
            if con[0] == i + 1 and con[1] == 1: #Verarbeitung, wenn sich am Ende eine Kreuzung im Bau befindet
                break
        else:
            m[0][i] = 1
            continue
        break

    for i in range(t): #Ähnlich vertikal
        for con in cons:
            if con[0] == 1 and con[1] == i + 1:
                break
        else:
            m[i][0] = 1
            continue
        break

    for i in range(1,t):
        for j in range(1,s):
            flag = False
            for con in cons:
                if con[0] == j + 1 and con[1] == i + 1: #Endpunkt
                    flag = True
                    break
            if flag:
                continue
            m[i][j] = m[i][j-1] + m[i-1][j]
    return m[-1][-1] #Die auf dem Ziel angegebene Zahl ist die Antwort
print(solver(a,b,c))

Die Anordnung der Flaggen ist sehr schmutzig

A-Maximale Summe

** Gedanken ** Da es nicht jedes Mal Zeit zum Summieren gibt, wird die kumulative Summe verwendet.

n, k = map(int,input().split())
a = [int(input()) for _ in range(n)]

sums = [0]
for i in range(n):
    sums.append(sums[-1]+a[i])

ans = sums[k]
for i in range(k,n+1):
    ans = max(sums[i]-sums[i-k],ans)
print(ans)

C-Kartenspiel

** Gedanken ** Ich bin nicht gut in spielbezogenen Problemen. Ich habe es simuliert.

n = int(input())
taro = [int(input()) for _ in range(n)]

taro.sort()
hana = []
for i in range(1,2*n+1): #Es gibt keine Vervielfältigung, also hat Hana Karten, die Taro nicht hat
    if i not in taro:
        hana.append(i)

m = taro.pop(0)
for _ in range(2*n):
    for i in range(len(hana)): #Finden Sie heraus, wie viele Karten Sie mindestens spielen können
        if hana[i] > m:
            m = hana.pop(i)
            break
    else:
        m = 0
    for i in range(len(taro)): #Finden Sie heraus, wie viele Karten Sie mindestens spielen können
        if taro[i] > m:
            m = taro.pop(i)
            break
    else:
        m = 0
    if len(hana) == 0 or len(taro) == 0: #Beenden Sie, wenn einer von beiden 0 wird
        break

print(len(hana)) #Letzte Nummer
print(len(taro)) #Letzte Nummer

** Gedanken ** Erstellen Sie eine Liste, in der die Entfernung zwischen Ihnen und $ n $ Freunden (wie viele Freunde Sie durchlaufen) zusammengefasst ist, und zählen Sie die Anzahl der Personen mit 2 oder weniger

n = int(input())
m = int(input())
f = [list(map(int,input().split())) for _ in range(m)]

d = [0] * n
for i in range(m): #Freund(Entfernung 1)Herausfinden
    if f[i][0] == 1:
        d[f[i][1]-1] = 1

for i in range(m): #Ein Freund eines Freundes(Entfernung 2)Herausfinden
    if d[f[i][0]-1] == 1:
        if d[f[i][1]-1] == 0:
            d[f[i][1]-1] = 2 #Freunde von Freunden sind Entfernung 2
    elif d[f[i][1]-1] == 1:
        if d[f[i][0]-1] == 0:
            d[f[i][0]-1] = 2 #Freunde von Freunden sind Entfernung 2

ans = d.count(1) + d.count(2) - 1

print(max(0,ans))

C-Tile

** Gedanken ** Berechnen Sie die nächste Kante von links, rechts, oben und unten und teilen Sie sie durch 3, um sie zu verarbeiten. Die Farben werden in der Reihenfolge vom nächsten Rand aus gemalt, daher müssen die Gehäuse für jede Zelle getrennt werden.

n = int(input())
k = int(input())
ab = [list(map(int,input().split())) for _ in range(k)]

for i in range(k):
    x1 = ab[i][0]-1
    x2 = n - ab[i][0]
    y1 = ab[i][1]-1
    y2 = n - ab[i][1]
    m = min(x1,x2,y1,y2) % 3
    if m == 0:
        print(1)
    if m == 1:
        print(2)
    if m == 2:
        print(3)

C-Signboard

** Gedanken ** Es ist mühsam, alle möglichen Kombinationen durch Zählen der Zielzeichen zu zählen. Bestimmen Sie also zuerst die Entfernung und simulieren Sie.

n = int(input())
s = input()
plate = [input() for _ in range(n)]

ans = 0
for i in range(n):
    p = plate[i]
    start =[]
    check = False

    for k in range(len(p)):
        if p[k] == s[0]: #Finden Sie den Ausgangspunkt heraus
            start.append(k)

    for k in range(1,len(p)+1): #Abstand zwischen Buchstaben
        if check:
            break
        for j in start: #Wählen Sie den ersten Buchstaben, den Sie zuvor nachgeschlagen haben
            flag = 0
            c = 0 #Gleiche Distanzgröße durch Erhöhen von c ausdrücken
            while j + k * c < len(p) and c < len(s): #j(Erster Charakter)Entfernung vom c-ten Zeichen
                if p[j+k*c] != s[c]:
                    break
                else:
                    c += 1
                    flag += 1
            if flag == len(s): #Wenn Sie das gewünschte Zeichen erstellen können, verwenden Sie ans+1
                ans += 1
                check = True
                break

print(ans)

Flagge ist schmutzig

C - Super Metropolis

** Gedanken ** Ich habe den Anfangswert als (1,1) falsch verstanden. Der Anfangswert ist (x1, y1). Es gibt eine Route, die nur diagonal verläuft, wenn Sie nach Nordosten oder Südwesten fahren. Daher müssen Fälle getrennt werden, da dies normalerweise die kürzeste Route des Gitters ist. Getrennt für Dämonen ()

Nur bei vertikaler oder horizontaler Bewegung beträgt die Differenz zwischen den beiden Koordinaten 0, nehmen Sie also max. ――Wenn Sie nach Nordosten fahren, können Sie dies durch Berechnen herausfinden, aber Sie können sehen, dass Sie das Maximum der Differenz zwischen den einzelnen Koordinaten nehmen sollten. Dies ist auch im Südwesten so
In anderen Fällen kann die diagonale Straße nicht verwendet werden, daher wird die Summe der absoluten Werte der Differenzen zwischen den Koordinaten genommen.

w, h, n = map(int,input().split())
spots = [list(map(int,input().split())) for _ in range(n)]

def search_route(s,g):
    if s[0] == g[0] or s[1] == g[1]: #Nur vertikale oder horizontale Bewegung
        return max(abs(g[1] - s[1]), abs(g[0] - s[0]))

    elif s[0] < g[0] and s[1] < g[1]: #Gehe nach Nordosten
        return max(g[0] - s[0], g[1] - s[1])

    elif s[0] > g[0] and s[1] > g[1]: #Gehe nach Südwesten
        return max(s[0] - g[0], s[1] - g[1])

    else: #anders als das
        return abs(s[0] - g[0]) + abs(s[1] - g[1])

ans = 0
for i in range(n-1):
    ans += search_route(spots[i],spots[i+1])
print(ans)

A --Poster

** Gedanken ** Betrachten wir jeden Fall, indem wir den Vorgang des Drehens des Posters korrigieren. Die Drehung beträgt $ 0 °, 90 °, 180 °, 270 ° $. Jetzt müssen Sie nur noch die Quadrate zählen, deren Farbe sich vom gewünschten Poster unterscheidet.

Ich ändere die Eingabe abhängig von meiner Stimmung, aber die normale Eingabe ist in Ordnung

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np #Der Drehvorgang verwendet numpy

n = int(readline())
s = np.array([list(readline().rstrip().decode()) for _ in range(n)])
t = [readline().rstrip().decode() for _ in range(n)]

ans = float('inf')
for i in range(4):
    check = np.rot90(s,i) #Drehung
    c = min(4-i,i)
    for j in range(n):
        for k in range(n):
            if check[j][k] != t[j][k]:
                c += 1
    ans = min(ans,c)
print(ans)

Zusammenfassung

Ich habe viel schmutzigen Code, also werde ich ihn reparieren und schließlich in C ++ schreiben. Ich bin der Meinung, dass Schwierigkeitsgrad 4 jetzt der richtige für mich ist, aber ich werde mich weiterhin der weiteren Verbesserung widmen. Wir sehen uns ~