[PYTHON] AtCoder Beginner Contest 087 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Ich habe 087 nacheinander mit ABC085 gelöst. Ich verbrachte eine Stunde damit, das D-Problem zu lösen, bemerkte aber wahrscheinlich keinen häufigen Fehler. Ich möchte es im Kapitel D Problem erwähnen.

Problem A

Kaufen Sie einfach einen Kuchen und den Rest mit Donuts,

answerA1.py

x,a,b=int(input()),int(input()),int(input())
print(x-a-((x-a)//b)*b)

answerA2.py

s=list(input())
s[3]="8"
print("".join(s))

B-Problem

Da x ein Vielfaches von 50 ist, können Sie es durch 50 teilen und über die Gleichung 10i + 2j + k = x nachdenken (0 <= i, j, k <= n, i + j + k = n). Sie können sich verschiedene Paare von i, j und k vorstellen, also zählen Sie sie hoch und antworten Sie.

answerB.py

a,b,c,x=int(input()),int(input()),int(input()),int(input())
x//=50
ans=0
for i in range(x//10+1):
    k=x-i*10
    for j in range(k//2+1):
        l=k-j*2
        ans+=(0<=i<=a and 0<=j<=b and 0<=l<=c)
print(ans)

C-Problem

In vertikaler Richtung gibt es nur 2 Quadrate. Überlegen Sie sich also, wohin Sie gehen sollen, O (n).

answerC.py

n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
ans=0
for i in range(n):
    ans=max(ans,sum(a[0][:(i+1)])+sum(a[1][i:]))
print(ans)

D Problem

Die ** Positionsbeziehung ** jeder Person ist wichtig. Wenn Sie daher ** Grafik ** verwenden, um die Positionsbeziehung anzuzeigen, können Sie mit der Überlegung gut fortfahren. Erstens ist in diesem Problem ** die Positionsbeziehung von Personen relativ **, so dass ** die Position des Startpunkts auf 0 ** gesetzt wird. Dann sollten Sie in der Reihenfolge von der Person entscheiden, die eine Positionsbeziehung zu dieser Person hat. Zu diesem Zweck bereiten Sie zunächst ein Array vor, in dem die Positionsbeziehung jeder Person zu welcher Person und die Entfernung gespeichert sind. Wenn die Informationen (Li, Ri, Di) durch Eingabe empfangen werden, entspricht das Array Li und Ri Fügen Sie diese Informationen in jedes Element ein. Ausgehend von ** einem oder mehreren Elementen und verbundenen Elementen ** werden dann die anderen Elemente verfolgt, um die Position jeder Person zu bestimmen. Zu diesem Zeitpunkt können die im Array gespeicherten Informationen jedoch inkonsistent sein. In diesem Fall wird Nein ausgegeben. Seien Sie zu diesem Zeitpunkt auch vorsichtig, wenn das Diagramm ** nicht verbunden ** ist. Entscheiden Sie zunächst, welches Element zuerst folgen soll, aber ** Wenn es sich um ein Element handelt, das mit keinem Element verbunden ist, überspringen Sie es, da keine inkonsistenten Informationen möglich sind ** (für das im nächsten Satz vorbereitete Prüfarray Prüfen Sie.) Bereiten Sie außerdem ein Array vor, um festzustellen, ob jedes Element überprüft wurde, und führen Sie die obigen Vorgänge in der Reihenfolge der nicht aktivierten mit BFS ** aus, die nicht mit allen Informationen übereinstimmen. Sie können überprüfen, ob Sie möchten. Als ich es gelöst habe, konnte ich dieses nicht verbundene Element nicht gut bestimmen. Denken Sie daran, dass das Grafikproblem möglicherweise ** nicht verbunden ** ist und ich es von nun an lösen möchte.

✳︎ Es gibt zwei Codes unten, der erste Code ist der Code, der im Moment der Inkonsistenz Nein ausgibt und das Programm beendet und beendet, der zweite Code ist der Code, nachdem alle Elemente und dann jede Information überprüft wurden Ist der Code, der auf Inkonsistenzen prüft (ersterer ist natürlich schneller).

answerD.py

import sys
sys.setrecursionlimit(400000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
check=[True]*n

lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
def bfs(z):
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                sys.exit()
st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)
print("Yes")

answerD2.py

import sys
sys.setrecursionlimit(100000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
check=[True]*n
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break

def bfs(z):
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])

st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)

for i in range(n):
    l=len(lrd[i])
    for j in range(l):
        k=lrd[i][j]
        if x[k[0]]!=x[i]+k[1]:
            print("No")
            sys.exit()
print("Yes")