AtCoder ABC171 Ceci est un résumé des problèmes de AtCoder Beginner Contest 171 qui s'est tenu le 2020-06-21 (dim) dans l'ordre du problème A, en tenant compte de la considération. La seconde partie traite du problème de l'ED. Cliquez ici pour la première moitié. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Vous avez une séquence de $ A $ constituée de $ N $ entiers positifs $ A_1, A_2, ⋯, A_N $. Vous continuerez à faire les $ Q $ fois suivants. ・ Dans l'opération $ i $, tous les éléments de valeur $ B_i $ sont remplacés par $ C_i $. Pour tout $ i (1 \ leq i \ leq Q) $, trouvez la somme de tous les éléments de la séquence $ A $ après l'opération $ i $, $ S_i $.
Je pensais que je manquerais de temps si je calculais la somme à chaque fois, j'ai donc décidé de calculer la différence pour chaque opération. La chaîne numérique $ A $ est gérée par dict.
abc171d.py
n = int(input())
a_list = list(map(int, input().split()))
a_dict = {}
total = 0
for a in a_list:
if a in a_dict:
a_dict[a] += 1
else:
a_dict[a] = 1
total += a
q = int(input())
for i in range(q):
b, c = map(int, input().split())
if b in a_dict:
if c in a_dict:
a_dict[c] += a_dict[b]
else:
a_dict[c] = a_dict[b]
total -= a_dict[b] * b
total += a_dict[b] * c
a_dict[b] = 0
print(total)
J'ai pu résoudre le problème D en douceur. Cependant, je n'ai pas pu résoudre le problème suivant.
Énoncé du problème Il y a des chats $ N $ (** even **). Chaque Sunuke-kun est numéroté 1,2 $,…, N $. Chaque Sunuke-kun a un foulard rouge autour du cou, et le foulard a 1 $ de l'entier non négatif qu'il préfère. Sunuke et ses collègues ont récemment appris une opération appelée xor (somme logique exclusive) pour les entiers. Immédiatement, Sunuke-kun et d'autres qui voulaient utiliser ce calcul ont décidé de calculer le xor de l'entier écrit sur l'écharpe de Sunuke-kun autre que lui. On sait que l'entier xor écrit sur l'écharpe des autres Sunuke-kun calculé par Sunuke-kun avec le nombre $ i $ est $ a_i $. Utilisez ces informations pour identifier l'entier écrit sur chaque foulard de Sunuke-kun.
Quant à 4264 personnes, le problème du E a été résolu, et lorsque le D a été résolu, il était à peu près à la 2000e place, mais au final, le classement n'était pas perceptible. Les nombres pairs étaient les points. J'ai également essayé de calculer diverses formules dans mon cahier, mais je n'ai pas pu trouver de formule pour trouver la réponse. Je pense que je peux le résoudre la prochaine fois, alors je voudrais dire que j'ai appris.
abc171e.py
n = int(input())
a_list = list(map(int, input().split()))
y = 0
for a in a_list:
y = y ^ a
for a in a_list:
x = y ^ a
print(x, end=" ")
Je suis également occupé cette semaine, alors j'aimerais l'ajouter même si j'en ai le temps.
Merci d'avoir lu la seconde moitié jusqu'à la fin.
Recommended Posts