Remplissez la difficulté JOI 4 avec Python

introduction

Utilisez Python (PyPy) pour résoudre les problèmes JOI Difficulty 4. Veuillez consulter ce site pour les problèmes et les niveaux de difficulté.

Route F-School

** Pensées ** Apprenez par le nombre de cas J'ai implémenté un diagramme comme celui-ci dans la liste et je l'ai résolu.

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 expliquée ci-dessus
    for i in range(s): #Fixé à 1 sur le bord latéral
        for con in cons:
            if con[0] == i + 1 and con[1] == 1: #Traitement lorsqu'il y a une intersection en construction à la fin
                break
        else:
            m[0][i] = 1
            continue
        break

    for i in range(t): #De même verticalement
        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: #Point final
                    flag = True
                    break
            if flag:
                continue
            m[i][j] = m[i][j-1] + m[i-1][j]
    return m[-1][-1] #Le nombre inscrit sur l'objectif est la réponse
print(solver(a,b,c))

La disposition des drapeaux est très sale

Somme maximum A

** Pensées ** Puisqu'il n'y a pas de temps à additionner à chaque fois, la somme cumulée est utilisée.

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)

Jeu de cartes C

** Pensées ** Je ne suis pas doué pour les problèmes liés au jeu. Je l'ai simulé.

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

taro.sort()
hana = []
for i in range(1,2*n+1): #Il n'y a pas de duplication, donc hana a des cartes que taro n'a pas
    if i not in taro:
        hana.append(i)

m = taro.pop(0)
for _ in range(2*n):
    for i in range(len(hana)): #Découvrez le nombre minimum de cartes que vous pouvez jouer
        if hana[i] > m:
            m = hana.pop(i)
            break
    else:
        m = 0
    for i in range(len(taro)): #Découvrez le nombre minimum de cartes que vous pouvez jouer
        if taro[i] > m:
            m = taro.pop(i)
            break
    else:
        m = 0
    if len(hana) == 0 or len(taro) == 0: #Terminer lorsque l'un ou l'autre devient 0
        break

print(len(hana)) #Dernier numéro
print(len(taro)) #Dernier numéro

C-Party

** Pensées ** Créez une liste qui résume la distance entre vous et $ n $ amis (combien d'amis vous traversez) et comptez le nombre de personnes de 2 ou moins

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

d = [0] * n
for i in range(m): #ami(Distance 1)Découvrir
    if f[i][0] == 1:
        d[f[i][1]-1] = 1

for i in range(m): #Un ami d'un ami(Distance 2)Découvrir
    if d[f[i][0]-1] == 1:
        if d[f[i][1]-1] == 0:
            d[f[i][1]-1] = 2 #Les amis d'amis sont à distance 2
    elif d[f[i][1]-1] == 1:
        if d[f[i][0]-1] == 0:
            d[f[i][0]-1] = 2 #Les amis d'amis sont à distance 2

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

print(max(0,ans))

C-Tile

** Pensées ** Calculez la distance la plus proche des bords gauche, droit, supérieur et inférieur, et divisez-la par 3 pour la traiter. Les couleurs sont peintes dans l'ordre à partir du bord le plus proche, il est donc nécessaire de séparer les cas pour chaque cellule.

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

** Pensées ** Il est difficile de compter toutes les combinaisons possibles en comptant les caractères cibles, alors déterminez d'abord la distance et simulez.

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]: #Découvrez le point de départ
            start.append(k)

    for k in range(1,len(p)+1): #Distance entre les lettres
        if check:
            break
        for j in start: #Choisissez la première lettre que vous avez recherchée plus tôt
            flag = 0
            c = 0 #Exprimer la même taille de distance en augmentant c
            while j + k * c < len(p) and c < len(s): #j(Premier personnage)Distance du caractère cième
                if p[j+k*c] != s[c]:
                    break
                else:
                    c += 1
                    flag += 1
            if flag == len(s): #Si vous pouvez créer le caractère souhaité, utilisez ans+1
                ans += 1
                check = True
                break

print(ans)

le drapeau est sale

C --Super Metropolis

** Pensées ** J'ai mal lu la valeur initiale comme (1,1). La valeur initiale est (x1, y1). Il y a un itinéraire qui va en diagonale uniquement en allant au nord-est ou au sud-ouest, il est donc nécessaire de séparer les cas, sinon c'est généralement l'itinéraire le plus court de la grille. Séparé pour les démons ()

• En cas de mouvement vertical ou horizontal uniquement, la différence entre les deux coordonnées sera de 0, donc prenez max. ――Lorsque vous vous dirigez vers le nord-est, vous pouvez le savoir en calculant, mais vous pouvez voir que vous devez prendre le maximum de la différence entre chaque coordonnée. C'est la même chose dans le sud-ouest
• Dans d'autres cas, la route diagonale ne peut pas être utilisée, donc la somme des valeurs absolues des différences entre les coordonnées est prise.

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]: #Mouvement vertical ou horizontal uniquement
        return max(abs(g[1] - s[1]), abs(g[0] - s[0]))

    elif s[0] < g[0] and s[1] < g[1]: #Allez au nord-est
        return max(g[0] - s[0], g[1] - s[1])

    elif s[0] > g[0] and s[1] > g[1]: #Allez au sud-ouest
        return max(s[0] - g[0], s[1] - g[1])

    else: #autre que ça
        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)

Affiche A

** Pensées ** Considérons chaque cas en fixant l'opération de rotation de l'affiche. La rotation est de 0 °, 90 °, 180 °, 270 ° $. Il ne vous reste plus qu'à compter les carrés de couleur différente de celle de l'affiche souhaitée.

Je change l'entrée en fonction de mon humeur, mais l'entrée normale est correcte

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 #L'opération de rotation utilise 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) #rotation
    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)

Résumé

J'ai beaucoup de code sale, donc je vais le réparer et éventuellement l'écrire en C ++. Je pense que le niveau de difficulté 4 est mon niveau actuel, mais je continuerai à travailler dur pour l'améliorer. A bientôt ~