[PYTHON] AtCoder Beginner Contest 045 Revue des questions précédentes

Temps requis

Impressions

Le problème D a fonctionné (bien qu'il ait été mal implémenté). Cependant, j'ai fait une erreur dans le cas du coin en raison des problèmes B et C et j'ai émis 3WA, donc je voudrais y réfléchir et l'utiliser la prochaine fois.

Problème A

Trouvez juste la zone.

answerA.py

a=input()
b=input()
h=input()
print((int(a)+int(b))*int(h)//2)

Problème B

Il vous suffit de faire une simulation. Saisissez avec précision le type d'état dans l'instruction while. Ici, considérez qui est le tour et quelle carte alphabet la personne a.

answerB.py

s=[input() for i in range(3)]
l=[len(s[i]) for i in range(3)]
abc=[0,0,0]
now=0
while abc[now]!=l[now]:
    s_sub=s[now][abc[now]]
    abc[now]+=1
    now=(0 if s_sub=="a" else 1 if s_sub=="b" else 2)
print("A" if now==0 else "B" if now==1 else "C")

Problème C

Lorsque la longueur de la chaîne de caractères est l, + peut être entré à 1-1 places, et puisque ** l est suffisamment petit, tous les $ 2 ^ {l-1} $ patterns ** peuvent être considérés. Masu (peu de recherche complète). Pensons donc à l'addition avec l'endroit où + entre. Ici, en regardant les chaînes de caractères des nombres dans l'ordre de l'avant, lorsque + est entre le i-ème caractère et le i + 1-ème caractère, considérez l'ajout du nombre sur le côté gauche et le nombre sur le côté droit, et + est le i-ème caractère. S'il ne rentre pas entre les caractères i + 1, considérez le nombre sur le côté gauche et la somme des nombres sur le côté droit comme une ** chaîne de caractères . Par conséquent, écrivez une recherche un peu complète, regardez entre les nombres dans l'ordre, et si + est entré dans le jth (j = 0 → l-2), la chaîne de nombres (subst) enregistrée à ce moment-là est un entier. En plus de ans_sub (n'oubliez pas de définir le j + 1er nombre sur subst), si + n'est pas entré dans le jth (j = 0 → l-2), ajoutez-le à subst sous forme de chaîne de caractères. , Le code ressemble à ceci: ( peu je me demande s'il faut utiliser (i >> j) & 1``` ou `` (1 << j) & i '' pour déterminer s'il s'agit de 1 dans le code pour une recherche complète. Je veux unifier ... **)

Postscript

Comme je l'ai remarqué plus tard, si vous mettez + entre les deux et divisez à la fin en fonction de +, la quantité de code que vous écrivez diminuera.

answerC.py

s=input()
l=len(s)

ans=0
for i in range(2**(l-1)):
    ans_sub=0
    subst=s[0]
    for j in range(l-1):
        if (i>>j)&1:
            ans_sub+=int(subst)
            subst=s[j+1]
        else:
            subst+=s[j+1]
        if j==l-2:
            ans_sub+=int(subst)
    ans+=ans_sub
if l==1:
    print(int(s))
else:
    print(ans)

Problème D

Au début, j'ai senti que je devais vérifier toutes les cases, mais comme c'est O (HW), je ne peux pas arriver à temps. Ici, si vous faites attention au nombre de carrés à remplir, il est de 10 ^ 5 ou moins, donc si vous vous concentrez sur le ** remplissage **, vous pouvez voir que vous pouvez écrire un programme. Ici, lorsque vous remplissez un certain carré, vous pouvez voir que le carré est inclus dans le plateau de 3 $ \ fois 3 $ centré sur les carrés adjacents. Par conséquent, les carrés adjacents (dont les carrés qui font le plateau de 3 $ \ fois 3 $) sont sauvegardés, et les carrés qui sont inclus dans le plateau de 3 $ \ fois 3 $ centré sur ce carré apparaissent. Vous pouvez le mettre à jour à chaque fois que vous venez. Aussi, ** il est impossible de sauvegarder toutes les coordonnées du centre en termes de calcul spatial **, j'essaye donc de ne sauvegarder que les coordonnées qui apparaissent dans le dictionnaire (tous les carrés qui n'apparaissent pas même une fois sont ( Le nombre de carrés (qui peut être le centre) $ (h-2) \ times (w-2) $ peut être soustrait des coordonnées.)

answerD.py

h,w,n=map(int,input().split())
d=dict()
def change(a,b):
    global h,w,d
    if 1<=a<h-1 and 1<=b<w-1:
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(3):
        for k in range(3):
            change(a+j-1,b+k-1)
ans=[0]*10
ans[0]=(h-2)*(w-2)

for i in d:
    ans[d[i]]+=1
    ans[0]-=1
for i in range(10):
    print(ans[i])