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

Temps requis

スクリーンショット 2020-03-31 16.11.31.png

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

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes