J'avais un sentiment de refus pour le menteur que le montant du calcul est O (1) (je pense que je comprends la raison), et je n'ai pas utilisé dict obstinément jusqu'à présent, mais au FHC j'ai participé la semaine dernière Problème facile avec dict
Lorsque la plage de valeurs est large et clairsemée
Avoir des éléments sous forme de clé, de valeur
Les éléments peuvent être insérés, supprimés, mis à jour et recherchés avec O (1) [Référence: Wikipedia HashTable](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86% E3% 83% BC% E3% 83% 96% E3% 83% AB)
| Opérations pouvant être effectuées | code | commentaire |
|---|---|---|
| Déclaration | b = {'one': 1, 'two': 2, 'three': 3} | a = dict(key1=value1,key2=value2,..)Et divers autres styles d'écriture |
| Nombre d'éléments | len(d) | |
| Référence de valeur | d[key] | d[key]KeyError se produit lorsque la clé n'existe pas |
| Référence de valeur(Inconnu s'il existe) | d.setdefault(key,default) | Renvoie la valeur de la clé, si elle existe dans le dictionnaire. Sinon, insérez la clé avec la valeur par défaut et renvoyez la valeur par défaut |
| Ajouter un élément | d[key] = value | Idem pour les mises à jour |
| Mise à jour des éléments | d[key] = value | Idem pour l'ajout |
| Supprimer l'élément | del d[key] | Sinon, KeyError |
| Supprimer l'élément(Inconnu s'il existe) | d.pop(key,default) | Sinon, retournez par défaut |
| Rechercher des éléments | key in d | |
| Rechercher des éléments(Quand vous voulez utiliser de la valeur) | d.get(key,default) | Renvoie la valeur correspondant à la clé. Renvoie la valeur par défaut si la clé n'existe pas |
| Supprimer tous les éléments du dictionnaire | clear() | |
| Sortez dans l'ordre inverse de l'insertion | d.popitem() | |
| Annulation de commande | reversed(d) | |
| liste | list(d.items()) | Renvoie sous forme de liste de taples |
| liste(key,valeur seulement) | list(d.keys()) | |
| boucle(key,value) | d.items() | key,la valeur revient sous forme de taple |
| boucle(key,valeur Un seul) | d.keys() or d.values() |
dict.py
>>>dic = dict(a=1,b=2,c=3)
#Même s'il s'agit d'une chaîne de caractères""Écrivez tel quel sans attacher
>>> dic
{'a': 1, 'b': 2, 'c': 3}
#Cependant, attachez-le en vous y référant
>>> dic[a]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> dic["a"]
1
>>> dic.pop("a")
1
>>> dic
{'b': 2, 'c': 3}
#Il est également possible de définir de cette manière d'écrire
>>> dic.clear()
>>> dic
{}
>>> dic = {1:1,2:1,3:2,4:3,5:5}
#la clé peut être une valeur numérique
>>> dic[1]
1
>>> dic[1]=8
>>> dic
{1: 8, 2: 1, 3: 2, 4: 3, 5: 5}
>>> dic.get(1,-1)
8
>>> list(dic.keys())
[1, 2, 3, 4, 5]
>>> list(dic.values())
[8, 1, 2, 3, 5]
>>> list(dic.items())
[(1, 8), (2, 1), (3, 2), (4, 3), (5, 5)]
#Si vous voulez boucler des éléments
>>> for k,v in dic.items():
... print(k,v)
...
1 8
2 1
3 2
4 3
5 5
Comme c'est un gros problème, je vais résoudre le problème FHC introduit au début en utilisant dict. Si vous êtes intéressé par le problème lui-même, veuillez essayer Explication que j'ai écrite.
Cette fois, à l'exception de la déclaration et de l'affectation, j'ai utilisé uniquement la référence de valeur avec get et loop avec items (), mais j'ai pu écrire facilement des dp épars. C'était une différence d'avoir idx dans la dichotomie, alors j'aimerais continuer à l'utiliser à l'avenir.
timer.py
import bisect
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# step1:Asseyez-vous (dans l'ordre trié))Effectuer DP à partir des bords gauche et droit
# dp_l[i] = max(dp_l[j] + h[i],h[i])Arbre menant à la place i(i=j+h[j])Recherche par dict
# dp_r[i] = max(dp_r[j] + h[i],h[i])
# step2:dp_l_Pour toutes les clés i dans dict, dp_r_Découvrez si c'est dans la clé de dict avec dict(p[i]+h[i]Est p[j]-h[j]Devient j i,Équivaut à rechercher j)
# step3:Correspondance à l'étape 2 i,pour j, ans= max(ans,dp_l[i]+dp_r[j])
t = int(input())
for case in range(t):
n = int(input())
p = [0] * n
h = [0] * n
for i in range(n):
p[i], h[i] = map(int, input().split())
p, h = zip(*sorted(zip(p, h)))
#Dans l'ordre croissant avec p, voyez dans l'ordre croissant pour ceux qui sont poussés vers la droite, et dans l'ordre décroissant pour ceux qui sont poussés vers la gauche.
#En regardant de gauche à ce que vous voyez de gauche
#dp a la clé comme pos,la valeur met en longueur
dp_r_dict = {} #Pos se termine par une rangée d'arbres qui tombent à droite(Extrémité droite) La plus longue longueur de la colonne
dp_l_dict = {}
for i in range(n):
# dict[p[i]]S'il y en a, il le renvoie, sinon il retourne 0
#Si p[i]S'il y a quelque chose qui se termine par, vous pouvez le connecter et l'étirer
tmp = dp_l_dict.get(p[i], 0) + h[i]
if dp_l_dict.get(p[i] + h[i], 0) < tmp: #De même
dp_l_dict[p[i] + h[i]] = tmp
r_max = 0
for i in range(n - 1, -1, -1):
tmp = dp_r_dict.get(p[i], 0) + h[i]
if dp_r_dict.get(p[i] - h[i], 0) < tmp:
dp_r_dict[p[i] - h[i]] = tmp
r_max = max(r_max, dp_r_dict[p[i] - h[i]])
# step3:dp_l_Pour dict, dp avec toutes les touches_r_Vérifiez s'il y a une correspondance avec la clé de dict et prenez max
ans = 0
for pos, l_len in dp_l_dict.items():
tmp = l_len + dp_r_dict.get(pos, 0) #Tout peut être face à la droite
ans = max(ans, tmp)
#Considérez tout vers la gauche
ans = max(ans, r_max)
case_str = "Case #" + str(case + 1) + ": " + str(ans)
print(case_str)
Veuillez commenter si vous avez des erreurs ou une meilleure écriture.
Recommended Posts