AtCoder Beginner Contest 087 Revue des questions précédentes

Temps requis

Impressions

J'ai résolu 087 successivement avec ABC085. J'ai passé une heure à résoudre le problème D, mais je n'ai probablement pas remarqué d'erreur courante. Je voudrais le mentionner dans le chapitre sur les problèmes D.

Problème A

Achetez juste un gâteau et le reste avec des beignets,

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))

Problème B

Puisque x est un multiple de 50, vous pouvez le diviser par 50 et penser à l'équation 10i + 2j + k = x (0 <= i, j, k <= n, i + j + k = n). Vous pouvez penser à différentes paires de i, j et k, alors comptez-les et répondez.

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)

Problème C

Il n'y a que 2 carrés dans la direction verticale, alors pensez simplement à où descendre, 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)

Problème D

La ** relation de position ** de chaque personne est importante. Par conséquent, si vous utilisez ** Graphique ** pour afficher la relation de position, vous pouvez bien procéder à la considération. Premièrement, dans ce problème, ** la relation de position des personnes est relative **, donc ** la position du point de départ est définie sur 0 **. Ensuite, vous devez décider dans l'ordre de la personne qui a une relation de position avec cette personne. Pour cela, préparez d'abord un tableau qui stocke la relation de position de chaque personne avec quelle personne et la distance, et lorsque les informations (Li, Ri, Di) sont reçues en entrée, le tableau correspondant à Li et Ri Mettez ces informations dans chaque élément. Ensuite, à partir de ** un ou plusieurs éléments et éléments connectés **, les autres éléments sont tracés afin de déterminer la position de chaque personne, mais à ce moment les informations stockées dans le tableau peuvent être incohérentes. Dans ce cas, Non est émis. Aussi, à ce stade, faites attention lorsque le graphique est ** non connecté **. Tout d'abord, décidez du premier élément à suivre, mais ** S'il s'agit d'un élément qui n'est connecté à aucun élément, ignorez-le car il n'y a aucune possibilité d'informations incohérentes ** (Pour le tableau de contrôle préparé dans la phrase suivante Vérifie ça.) En outre, préparez un tableau pour déterminer si chaque élément a été vérifié et effectuez les opérations ci-dessus à l'aide de BFS dans l'ordre à partir de ceux non vérifiés dans le tableau, ce qui contredit toutes les informations. Vous pouvez vérifier si vous le souhaitez. Quand je l'ai résolu, je ne pouvais pas bien juger cet élément déconnecté. Gardez à l'esprit que le problème du graphe peut être ** non connecté **, et j'aimerais le résoudre à partir de maintenant.

✳︎ Il y a deux codes ci-dessous, le premier code est le code qui sort No au moment de l'incohérence et sort pour terminer le programme, et le deuxième code est l'information après vérification de tous les éléments. Est le code qui vérifie s'il y a une incohérence (bien sûr, le premier est plus rapide).

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")