Funciones y Módulos Esenciales para Competencias de Algoritmos (Python)

Entrada y Salida

import sys
sys.setrecursionlimit(10**7)  # Establecer límite de recursión, predeterminado 1000
# Permite convertir enteros grandes a cadenas, evitando errores con números grandes
input = sys.stdin.readline # Optimizar lectura de grandes volúmenes de datos
n,m=map(int,input().split()) # Formato de entrada, usar comprensiones para listas y diccionarios
datos_preguntas = [list(map(int, input().split())) for _ in range(n)]

# Al imprimir grandes volúmenes de datos, almacenar en lista y luego join
# sys.stdout.write(str(respuesta) + '\n')
# Para salidos con datos > 10^6, usar salida por lotes
print(" ".join(map(str, datos_preguntas)))
print(*datos_preguntas, sep=" ")

Bucles For

estudiantes = ['Ana', 'Luis', 'Marta']
puntuaciones = [90, 80, 85]
for estudiante, puntuacion in zip(estudiantes, puntuaciones):
    print(estudiante, puntuacion)
matriz = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
matriz_transpuesta = [list(fila) for fila in zip(*matriz)]
print(matriz_transpuesta)

Cadenas F

f"{ nombre_variable [=] [: [relleno][alineamiento][signo][anchura][separador][.precisión][#][tipo] ] }"

=: Imprime automáticamente el nombre de la variable o literal antes de = y su valor después, útil para depuración
carácter_relleno: Especifica un único carácter para rellenar (requiere uso con símbolo_alineamiento)
alineamiento: < (izquierda), ^ (centro), > (derecha)
signo: Solo para números, especifica prefijo para positivos (+, -, espacio)
anchura: Anchura mínima de salida, rellena con carácter_relleno (predeterminado espacio)
separador: Solo puede ser "," (miles) o "_"
.precisión: Especifica decimales para tipo f o caracteres para tipo s
#: Muestra prefijos 0b, 0o, 0x o fuerza punto decimal (incluso sin decimales)
tipo: d, f, e, E, %, s, b, o, x, etc.

numero = 12345.6789
print(f"Siguiendo estrictamente el orden: relleno(*) alineamiento(^) prefijo(#) anchura(20) separador(,) precisión(.2) tipo(f)\n{numero:*^#20,.2f}")

# Conversiones de base
num = 10
print(f"{num:b}")  # Binario: 1010
print(f"{num:o}")  # Octal: 12
print(f"{num:x}")  # Hexadecimal (minúsculas): a
print(f"{num:X}")  # Hexadecimal (mayúsculas): A
# Notación con prefijo (#)
print(f"{num:#b}")  # Binario: 0b1010
print(f"{num:#o}")  # Octal: 0o12
print(f"{num:#x}")  # Hexadecimal (minúsculas): 0xa
print(f"{num:#X}")  # Hexadecimal (mayúsculas): 0XA
# Usar función int(x,base) para conversiones
# x: Cadena o número a convertir
# base: Base (2-36), predeterminado 10
print(f"{int('1010', 2):o}")  # Binario a octal: 12
print(f"{int('12', 8):x}")  # Octal a hexadecimal: a

Métodos Integrados sin Importar

Estos métodos están en el módulo builtins, puedes ver todas las funciones integradas, constantes y excepciones con:
import builtins
dir(builtins)
help(builtins)

print(f"{abs(-10)=}")  # abs() puede reemplazar completamente a math.fabs()
print(all([1 > 0, 1 > 0, 1 > 0]))  # True
print(any([1 > 0, 0 > 0, 0 > 0]))  # True
print(complejo(3, 4))  # Salida:(3+4j)
print(divmod(10, 3))  # 10/3=3···1 Salida:(3,1)
print(f"{eval('5 * 10')=}")  # Ejecuta código en cadena
print(f"{len([1, 2, 3])=}")  # Salida:len([1, 2, 3])=3
print(max(1, 2, 3))  # Salida:3
print(min(1, 2, 3))  # Salida:1
print(potencia(2, 3))  # # pow() puede reemplazar completamente a math.pow()
print(potencia(2, 3, 5))  # Potenciación rápida, no usar 2**3%5 Salida:3
print(*rango(10, 0, -1))  # Salida:10 9 8 7 6 5 4 3 2 1
# Redondeo bancario (redondeo al par más cercano), para redondeo normal usar math.floor(x + 0.5)
print(redondeo(2.5))  # Salida:2
print(redondeo(3.5))  # Salida:4
print(redondeo(2.3456, 2))  # Salida:2.35
# Acepta objetos iterables, devuelve una lista ordenada; a diferencia de list.sort(), list.sort() ordena en la lista original
print(ordenado((3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5), clave=None, inverso=False))
print(sum([1, 2, 3, 4]))  # Salida:10
# zip() empaqueta elementos correspondientes de múltiples iterables en tuplas
# devuelve un objeto iterable
print(list(zip([1, 2, 3], ["a", "b", "c"])))  # Salida:[(1, 'a'), (2, 'b'), (3, 'c')]
print(*list(zip([1, 2, 3], ["a", "b", "c"])))  # Salida:(1, 'a') (2, 'b') (3, 'c')
# Combina un iterable en una secuencia indexada, mostrando datos e índices
# devuelve un objeto enumerado, que es iterable
# sintaxis: enumerate(iterable, inicio = 0), inicio especifica el valor inicial del índice
for indice, (elemento1, elemento2) in enumerate(zip([1, 2], ["a", "b"]), inicio=0):
print(indice, elemento1, elemento2)
# Salida:
# 0 1 a
# 1 2 b
# reversed(iterable) devuelve un iterador inverso
print(list(reversa([1, 2, 3])))  # Salida:[3, 2, 1]

Métodos Comunes de Cadenas

Las cadenas son objetos inmutables, por lo que operaciones de "añadir, eliminar, modificar, buscar"本质上 hacen "concatenación" y crean un nuevo objeto

Añadir > Se puede usar + para concatenar cadenas, pero f-strings pueden reemplazar + en todos los casos y son un poco más rápidos; para procesamiento por lotes de listas, join es más eficiente que f-strings

cadena1 = '123'
cadena2 = 'abc'
cadena1 = "".join([cadena1, cadena2])
print(cadena1)  # Salida: 123abc

Eliminar``` print("123 abc".reemplazar("3 a", "")) # Salida:12bc print('123 abc'[2:5]) # Salida:3 a

strip(): Elimina caracteres especificados al inicio y final, predeterminados espacios en blanco

print(' a b c '.strip()) # Salida:a b c

Solo inicio

print(' a b c '.lstrip()) # Salida:a b c

Solo final

print(' a b c '.rstrip()) # Salida: a b c

- Modificar```
print('abc abc'.reemplazar('a', 'A'))  # Salida:Abc Abc
# Reemplaza caracteres según una tabla de conversión (creada con maketrans())
tabla_trans = str.maketrans("abc", "***")
print(tabla_trans)  # {97: 42, 98: 42, 99: 42}
print('abc123'.traducir(tabla_trans))  # Salida:***123

Buscar```

Busca primera aparición de subcadena.

Si encuentra, devuelve índice inicial; si no, devuelve -1

find() busca desde la izquierda, rfind() desde la derecha

print('abc abc'.buscar('a')) # Salida:0 print('abc abc'.rfind('abc')) # Salida:4

index(),rindex corresponden a find(),rfind(),

la diferencia es que si no encuentra, los primeros lanzan ValueError, los segundos devuelven -1

print('abc abc'.index('abc')) # Salida:0 print('abc abc'.rindex('abc')) # Salida:4

- Otros```
print(len("abc"))  # Salida:3
print("abc abc".contar("abc"))  # Salida:2
# ord() devuelve punto Unicode de carácter, conchr correspondiente
print(ord("A"))  # Salida:65
print(caracter(65))  # Salida:A
# split() divide desde la izquierda, rsplit() desde la derecha
print("a,b,c".split(","))  # Salida:['a', 'b', 'c']
print("a,b,c".rsplit(","))  # Salida:['a', 'b', 'c']
print("ABC".minusculas())  # Salida:abc
print("abc".mayusculas())  # Salida:ABC
print("abc ABC".intercambiar_mayus())  # Intercambia mayúsculas y minúsculas Salida:ABC abc
print("abc abc".titulo())  # Primera letra de cada palabra en mayúscula Salida:Abc Abc
print("aBC ABC".capitalizar())  # Primera letra en mayúscula, resto en minúscula Salida:Abc abc
print("abc abc".comienza_con("abc"))  # Comienza con subcadena Salida:True
print("abc abc".termina_con("abc"))  # Termina con subcadena Salida:True
print("abc".es_alpha())  # Todos caracteres alfabéticos Salida:True
print("123".es_digito())  # Todos caracteres numéricos Salida:True
print("Abc".es_mayus())  # Todos caracteres mayúsculas Salida:False
print("Abc".es_minus())  # Todos caracteres minúsculas Salida:False
print("Abc".es_titulo())  # Primera letra mayúscula Salida:True
print(" \t\n\r ".es_espacio())  # Todos caracteres espacios en blanco Salida:True

Métodos Comunes de Listas

Añadir

lista = [1, 2]
lista.agregar(3)  # Añade elemento al final
lista.extender((4, 5, 6))  # Añade elementos de iterable al final
lista.insertar(1, 7)  # Inserta elemento en índice 1
print(lista)  # Salida:[1, 7, 2, 3, 4, 5, 6]

Eliminar

lista = [1, 2, 3, 2]
lista.eliminar(2)  # Elimina primera coincidencia, lanza error si no existe
print(lista)  # Salida:[1, 3, 2]
print(lista.sacar(1))  # Elimina y devuelve elemento en índice 2 Salida:3
print(lista)  # Salida:[1, 2]

Modificar

mi_lista = [1, 2, 3]
mi_lista[1] = 4
print(mi_lista)  # Salida:[1, 4, 3]
mi_lista[1:3] = [2, 3]
print(mi_lista)  # Salida:[1, 2, 3]

Buscar

# index() devuelve índice de primera coincidencia.
# Si no existe, lanza error.
print([1, 2, 3, 2].index(2))  # Salida:1

Otros

lista = [3, 1, 4, 1, 5, 9]
print(lista.contar(1))  # Cuenta apariciones de elemento
lista.ordenar(
    clave=None, inverso=False
)  # Ordena elementos, predeterminado orden ascendente
print(lista)  # Salida:[1, 1, 3, 4, 5, 9]
lista.invertir()  # Invierte orden de elementos
print(lista)  # Salida:[9, 5, 4, 3, 1, 1]

nombres = ["Smith, John", "Doe, Jane", "Johnson, Adam"]
nombres.ordenar(clave=lambda item: item.split(", ")[1])
print(nombres)

estudiantes = [
    {"nombre": "Ana", "nota": 85},
    {"nombre": "Luis", "nota": 90},
    {"nombre": "Marta", "nota": 80},
]
estudiantes.ordenar(clambda=lambda estudiante: estudiante["nota"])
print(estudiantes)
"""
Salida:[{'nombre': 'Marta', 'nota': 80}, {'nombre': 
'Ana', 'nota': 85}, {'nombre': 'Luis', 'nota': 90}]
"""

Métodos Comunes de Diccionarios

dict: ordenado, claves únicas, valores repetibles, mutables

Añadir``` mi_dic1 = {'a': 1, 'b': 2} mi_dic2 = {'b': 3, 'c': 4} mi_dic1.actualizar(mi_dic2) # Actualiza un diccionario con otro print(mi_dic1) # Salida:{'a': 1, 'b': 3, 'c': 4}

- Eliminar```
mi_dic = {"a": 1, "b": 2, "c": 3}
valor = mi_dic.sacar("a")  # Elimina par clave-valor y devuelve valor
print(mi_dic)  # Salida:{'b': 2, 'c': 3}
print(valor)  # Salida:1
try:
    valor2 = mi_dic.sacar("d")  # Lanza KeyError si no existe
except KeyError:
    print("Clave no existe")  # Salida:Clave no existe
valor3 = mi_dic.sacar("e", 0)  # Especificar valor predeterminado si no existe
print(valor3)  # Salida:0
mi_dic = {"a": 1, "b": 2, "c": 3}
item = mi_dic.sacar_item()  # Elimina y devuelve último par clave-valor (LIFO)
print(mi_dic)  # Salida:{'a': 1, 'b': 2}
print(item)  # Salida:('c', 3)
mi_dic.limpiar()  # Elimina todos los pares clave-valor
print(mi_dic)  # Salida:{}

Modificar```

setdefault() establece par clave-valor, si no existe lo añade

dic1 = {"a": 1, "b": 2} print(dic1.setdefault("c")) # Salida:None print(dic1) # Salida:{'a': 1, 'b': 2, 'c': None} print(dic1.setdefault("d", 4)) # Salida:4 print(dic1) # Salida:{'a': 1, 'b': 2, 'c': None, 'd': 4}

- Buscar```
dic1 = {'a': 1, 'b': 2}
# get() obtiene valor, si no existe devuelve predeterminado
print(dic1.get('c'))  # Salida:None
print(dic1.get('c', 3))  # Salida:3
print(dic1)  # Salida:{'a': 1, 'b': 2}

Otros``` dic1 = {"a": 1, "b": 2, "c": 3}

keys() devuelve vista iterable de claves

print(dic1.keys()) # Salida:dict_keys(['a', 'b', 'c'])

values() devuelve vista iterable de valores

print(dic1.values()) # Salida:dict_values([1, 2, 3])

items() devuelve vista iterable de tuplas (clave, valor)

print(dic1.items()) # Salida:dict_items([('a', 1), ('b', 2), ('c', 3)]) for clave in dic1.keys(): print(clave)

Salida:

a

b

c

for valor in dic1.values(): print(valor)

Salida:

1

2

3

for item in dic1.items(): print(item)

Salida:

('a', 1)

('b', 2)

('c', 3)

for clave, valor in dic1.items(): print(clave, valor)

Salida:

a 1

b 2

c 3

Métodos Comunes de Conjuntos
------

> set: desordenado, elementos únicos, mutables

- Añadir

conjunto1 = {1, 2, 3} conjunto1.agregar(4) # Añade elemento al conjnuto print(conjunto1) # {1, 2, 3, 4} conjunto1.actualizar([5, 6 ,7]) # Añade elementos de iterable al conjunto print(conjunto1) # {1, 2, 3, 4, 5, 6, 7}

- Eliminar

conjunto1 = {1, 2, 3}

Elimina elemento especificado, lanza error si no existe

print(conjunto1.eliminar(3)) # Salida:None

Elimina elemento especificado, no lanza error si no existe

print(conjunto1.descartar(3)) # Salida:None

- Modificar

> No hay métodos directos, se puede eliminar y añadir
- Buscar

print(2 in {1, 2, 3}) # Salida:True

- Otros

print({1, 2, 3} & {3, 4, 5}) # Intersección Salida:{3} print({1, 2, 3} | {3, 4, 5}) # Unión Salida:{1, 2, 3, 4, 5} print({1, 2, 3} - {3, 4, 5}) # Diferencia Salida:{1, 2} print({1, 2, 3} ^ {3, 4, 5}) # Diferencia simétrica Salida:{1, 2, 4, 5} print({1, 2, 3} <= ({1, 2, 3})) # Es subconjunto Salida:True print({1, 2, 3} < ({1, 2, 3, 4})) # Es subconjunto propio Salida:True

Métodos Comunes de Tuplas
------

> tuple: ordenado, elementos repetibles, inmutables

> Como las tuplas son inmutables, no tienen métodos para añadir, eliminar o modificar

- Buscar```
print((2, 1, 2).index(2))  # index() devuelve índice de primera coincidencia Salida:0

Otros``` print((2, 1, 2).contar(2)) # count() cuenta apariciones de elemento Salida:2

Clase `deque`

- Añadir

from collections import deque

mi_deque = deque([1, 2, 3], maxlen=5) # Crea deque con longitud máxima 5 mi_deque.insertar(1, 4) # Inserta elemento en índice 1 print(mi_deque) # Salida:deque([1, 4, 2, 3], maxlen=5) mi_deque.agregar(5) # Añade elemento al final print(mi_deque) # Salida:deque([1, 4, 2, 3, 5], maxlen=5) mi_deque.agregar_izquierda(6) # Añade elemento al inicio print(mi_deque) # Salida:deque([6, 1, 4, 2, 3], maxlen=5) mi_deque.extender([7, 8]) # Añade elementos de iterable al final print(mi_deque) # Salida:deque([4, 2, 3, 7, 8], maxlen=5) mi_deque.extender_izquierda([9, 10]) # Añade elementos de iterable al inicio en orden inverso print(mi_deque) # Salida:deque([10, 9, 4, 2, 3], maxlen=5)

- Eliminar

from collections import deque

mi_deque = deque([1, 2, 3, 1, 2, 3]) # Crea deque ultimo_elemento = mi_deque.sacar_derecha() # Elimina y devuelve elemento del final print(ultimo_elemento) # Salida:3 print(mi_deque) # Salida:deque([1, 2, 3, 1, 2]) primer_elemento = mi_deque.sacar_izquierda() # Elimina y devuelve elemento del inicio print(primer_elemento) # Salida:1 print(mi_deque) # Salida:deque([2, 3, 1, 2]) mi_deque.eliminar(2) # Elimina primera coincidencia del elemento print(mi_deque) # Salida:deque([3, 1, 2])

- Modificar

from collections import deque

mi_deque = deque([1, 2, 3]) # Acceder a elementos por índice mi_deque[0] = 4 print(mi_deque) # Salida:deque([4, 2, 3])

Usar pop()+insertar()/agregar() y pop_izquierda()+insertar()/agregar_izquierda() también modifica

- Buscar

from collections import deque

mi_deque = deque([1, 2, 3]) # Acceder a elementos por índice print(mi_deque.index(2)) # Salida:1

- Otros

from collections import deque

mi_deque = deque([1, 2, 3]) print(len(mi_deque)) # Salida:3 mi_deque.limpiar() # Elimina todos los elementos print(len(mi_deque)) # Salida:0

mi_deque = deque([1, 2, 3, 4, 5]) mi_deque.rotar(1) # Rota elementos, positivo a derecha, negativo a izquierda print(mi_deque) # Salida:deque([5, 1, 2, 3, 4]) mi_deque.rotar(-2) print(mi_deque) # Salida:deque([2, 3, 4, 5, 1])

mi_deque1 = deque([1, 2, 3, 1, 2, 3]) mi_deque2 = mi_deque1.copiar() print(mi_deque2) # Salida:deque([1, 2, 3, 1, 2, 3]) print(mi_deque2.contar(1)) # Cuenta apariciones de elemento Salida:2 mi_deque2.invertir() # Invierte orden de elementos print(mi_deque2) # Salida:deque([3, 2, 1, 3, 2, 1])

Módulos y Funciones Esenciales
----------

import bisect import copy import functools import heapq import itertools import math import sys from collections import Counter, defaultdict, deque from datetime import datetime

Orden de importancia:

Esenciales: sys (entrada/salida rápida), collections.deque (BFS, colas, pilas, ventana deslizante)

Frecuentes: collections.defaultdict (grafos, conteo, agrupación), heapq (Top K, Dijkstra, colas prioritarias), collections.Counter (frecuencia, conteo), itertools (permutaciones, combinaciones, producto cartesiano), math (mcd, sqrt, ceil, floor)

Moderados: bisect (búsqueda binaria, inserción en lista ordenada), functools (optimización recursiva, ordenación personalizada), copy (copia profunda)

Menos frecuentes: datetime (cálculo de fechas), funciones especiales de math (comb, perm), operaciones avanzadas de itertools (suma prefija, agrupación)

Módulo math
----

import math

Devuelve el menor entero >= x

print(math.techo(4.1)) # Salida:5

Devuelve el mayor entero <= x

print(math.piso(4.9)) # Salida:4

Devuelve raíz cuadrada de x. x debe ser >= 0,否则ValueError

print(math.raiz(9)) # Salida:3.0

Devuelve e^x

print(math.exp(1)) # 2.718281828459045

Devuelve logaritmo de x en base base, si no se especifica base, usa e

print(math.log(10)) # 2.302585092994046 print(math.log(100, 10)) # 2.0

Devuelve seno, coseno y tangente de x (en radianes)

print(math.sin(math.pi / 2)) # 1.0 print(math.cos(0)) # 1.0 print(math.tan(math.pi / 4)) # 0.9999999999999999

Devuelve arcoseno, arcocoseno y arcotangente de x (resultados en radianes)

print(math.asin(1)) # 1.5707963267948966 print(math.acos(0)) # 1.5707963267948966 print(math.atan(1)) # 0.7853981633974483

Convierte radianes a grados

print(math.grados(math.pi / 2)) # 90.0

Convierte grados a radianes

print(math.radianes(90)) # Salida:1.5707963267948966

Devuelve n!

print(math.factorial(5)) # Salida:120

Devuelve mcd de a y b

print(math.mcd(12, 18, 3)) # Salida:3

Devuelve número de combinaciones de n elementos tomados de k en k

print(math.comb(5, 3)) # Salida:10

Calcula distancia euclidiana entre dos puntos de misma dimensión

print(math.distancia((1, 2), (4, 6))) # Salida:5.0 print(math.modulo(10, 2)) # Salida:0.0

Módulo heapq
-----

> heapq usa listas Python comunes internamente, type() devuelve list, a diferencia de deque

import heapq

Crear heap método 1: desde heap vacío

heap = []

Crear heap método 2: desde lista existente (recomendado, O(n))

monticulo = [4, 3, 2, 1] heapq.heapify(monticulo) # Convierte lista en heap in-place, método 1 no necesita heapify print("Montículo inicial:", monticulo) # [1, 3, 2, 4] (no necesariamente ordenado, pero cumple propiedad de heap)

Insertar en heap

heapq.heappush(monticulo, 6) heapq.heappush(monticulo, 5) print("Después de insertar:", monticulo) # [1, 3, 2, 4, 6, 5] (no necesariamente ordenado, pero cumple propiedad de heap)

Ver mínimo sin eliminar

min_val = monticulo[0] print("Valor mínimo:", min_val) # 1

Tamaño del heap

tamaño = len(monticulo) print("Tamaño del heap:", tamaño) # 6

Verificar si está vacío

esta_vacio = len(monticulo) == 0 print("¿Está vacío?:", esta_vacio) # False

Eliminar del heap (extrae mínimo)

min_val = heapq.heappop(monticulo) print("Extraído:", min_val) # 1 print("Después de extraer:", monticulo) # [2, 3, 5, 4, 6]

heapreplace = pop + push (más eficiente)

min_viejo = heapq.heapreplace(monticulo, 7) print("Extraído:", min_viejo) # 2 print("Heap:", monticulo) # [3, 4, 5, 7, 6]

heappushpop = push + pop (más eficiente)

nuevo_min = heapq.heappushpop(monticulo, 0) print("Insertar 0 y extraer:", nuevo_min) # 0 print("Heap:", monticulo) # [3, 4, 5, 7, 6]

mayores_3 = heapq.nlargest(3, monticulo) menores_3 = heapq.nsmallest(3, monticulo) print("3 elementos más grandes:", mayores_3) # [7, 6, 5] print("3 elementos más pequeños:", menores_3) # [3, 4, 5]

Parámetro key especifica clave de comparación

estudiantes = [ {"nombre": "Ana", "puntuacion": 85}, {"nombre": "Luis", "puntuacion": 92}, {"nombre": "Marta", "puntuacion": 78}, {"nombre": "David", "puntuacion": 90}, } mejores_2 = heapq.nlargest(2, estudiantes, key=lambda s: s["puntuacion"]) print(mejores_2)

Salida:[{'nombre': 'Luis', 'puntuacion': 92}, {'nombre': 'David', 'puntuacion': 90}]

Módulo itertools
---------

import itertools

lista1 = [1, 2, 3] lista2 = ["a", "b", "c"]

Devuelve todas las permutaciones de elementos del iterable

Si se especifica r, devuelve permutaciones de longitud r

print(f"{'itertools.permutations':=^80}") for i in itertools.permutations(lista1, r=3): print(i, end=" ")

Salida: (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

print(f"\n\n{'itertools.combinaciones':=^80}")

Combinaciones normales (ej: elegir 2 de 3 para competir) ===========================================================

print(list(itertools.combinaciones(lista1, 2))) # Salida: [(1, 2), (1, 3), (2, 3)]

print(f"\n{'itertools.combinaciones_con_repeticion':=^80}")

Combinaciones con repetición (ej: comprar 2 frutas, puede ser 2 manzanas) ============================================================================

print(list(itertools.combinaciones_con_repeticion(lista1, 2)))

Salida: [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

print(f"\n\n{'itertools.producto':=^80}")

Sin repeat, calcula producto cartesiano de múltiples iterables

Con repeat, calcula producto cartesimo del iterable consigo mismo repeat veces

for i in itertools.producto(lista1, lista2): print(i, end=" ")

Salida: (1, 'a') (1, 'b') (1, 'c') (2, 'a') (2, 'b') (2, 'c') (3, 'a') (3, 'b') (3, 'c')

print(f"\n\n{'itertools.producto':=^80}")

Con repeat, calcula producto cartesimo del iterable consigo mismo repeat veces

for i in itertools.producto(lista1, repeat=2): print(i, end=" ")

Salida: (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)

print(f"\n\n{'itertools.cadena':=^80}")

Conecta múltiples iterables en un único iterador

for i in itertools.cadena(lista1, lista2): print(i, end=" ")

Salida: 1 2 3 a b c

print(f"\n\n{'itertools.acumular':=^80}") result = itertools.acumular(lista1, lambda x, y: x * y) # Predeterminado es suma print(list(result)) # Salida:[1, 2, 6]

print(f"\n{'itertools.agrupar':=^80}") for char, group in itertools.agrupar("AAAABBBCDAA"): # group también es un iterador, necesita convertirse en lista para ver longitud print(f"{char}: {len(list(group))}", end=" ")

Salida: A: 4 B: 3 C: 2 D: 1 A: 2

Nota: solo agrupa elementos continuos. Los últimos AA se agrupan por separado.

print(f"\n\n{'itertools.contar':=^80}")

Crea un iterador infinito que comienza en start con paso step

for i in itertools.contar(1, 2): # contar(inicio=0, paso=1) if i > 10: break print(i, end=" ")

Salida:1 3 5 7 9

print(f"\n\n{'itertools.ciclo':=^80}")

Realiza un bucle infinito sobre un iterable

contador = 0 for i in itertools.ciclo("ABC"): # ciclo(iterable) if contador > 5: break print(i, end=" ") contador += 1

Salida:A B C A B C

print(f"\n\n{'itertools.repetir':=^80}")

Repite objeto specified veces (sin especificar, repite infinitamente)

for i in itertools.repetir("Hola", 3): print(i, end=" ")

Salida:Hola Hola Hola

Módulo functools
---------

> lru_cache

from functools import lru_cache

@lru_cache(None) # Añadir esta línea hace que el problema sea estable def dfs(estado): if condicion_final: return 0 # ... varias llamadas recursivas return resultado


> Al usar cmp_to_key con sort: cmp_to_key solo recibe una función de comparación de dos parámetros

> cmp_to_key() es específica para problemas de número más grande
>
> Descripción del problema: Dado un conjunto de enteros positivos, concatenar adyacentes para formar el número más grande

from functools import cmp_to_key

def comparar(a, b): if a + b > b + a: return -1 # a va antes que b (descendente) elif a + b < b + a: return 1 # b va antes que a else: return 0

nums = [3, 30, 34, 5, 9] strs = [str(x) for x in nums] strs.sort(key=cmp_to_key(comparar)) resultado = "".join(strs).lstrip("0") or "0" print(resultado) # "9534330"

Módulo bisect
------

import bisect

Esencial: usar bisect para buscar "predecesor" y "sucesor" =============================================================

arr = [10, 20, 20, 30, 30] x = 20 print(f"Primera posición >= {x}: {bisect.bisect_left(arr, x)}") # 1 print(f"Primera posición > {x}: {bisect.bisect_right(arr, x)}") # 3

Uso avanzado: búsqueda en tabla/evaluación de rangos =======================================================

def calificacion(puntuacion): puntos_corte = [60, 70, 80, 90] calificaciones = "EDCBA" # bisect devuelve posición de inserción, que corresponde al índice de calificaciones i = bisect.bisect_right(puntos_corte, puntuacion) return calificaciones[i]

print([calificacion(s) for s in [55, 60, 75, 89, 95]]) # Salida: ['E', 'D', 'C', 'B', 'A']

Módulo collections
-----------

### Clase Counter

from collections import Counter

lista1 = [3, 2, 1, 2, 1, 1]

Counter es un contenedor para contar objetos hashables

contador_obj = Counter(lista1)
print(contador_obj) # Salida:Counter({1: 3, 2: 2, 3: 1}) print(contador_obj[1]) # Counter es subclase de dict, se puede acceder con índice Salida:3

most_common() devuelve lista de tuplas ordenadas por frecuencia descendente

print(contador_obj.most_common()) # Salida:[(1, 3), (2, 2), (3, 1)]

Devuelve los n elementos más comunes con sus conteos

print(contador_obj.most_common(2)) # Salida:[(1, 3), (2, 2)]

iter_elementos = contador_obj.elementos() # elements() devuelve iterador for elemento in iter_elementos: # El iterador devuelve elementos según su conteo print(elemento, end=" ") # Salida:3 2 2 1 1 1

contador_obj.limpiar() # clear() elimina todos los elementos del Counter print("\nDespués de limpiar:", contador_obj) # Salida:Después de limpiar: Counter()

Pasa un iterable, añade conteos al Counter actual

contador_obj.actualizar([3, 2, 1, 2, 1, 1]) print(contador_obj) # Salida: Counter({1: 3, 2: 2, 3: 1})


### defaultdict

from collections import defaultdict

Su principal ventaja es devolver un valor predeterminado al acceder a claves inexistentes

En lugar de lanzar KeyError como los diccionarios normales.

mi_dict = defaultdict(int) # int() devuelve 0 como predeterminado print(mi_dict) # Salida:defaultdict(<class 'int'>, {}) mi_dict["clave1"] += 1 print(mi_dict["clave1"]) # Salida:1 print(mi_dict["clave2"]) # Salida:0

mi_lista_dict = defaultdict(list) # list() devuelve lista vacía como predeterminada mi_lista_dict["clave1"].append(1) print(mi_lista_dict["clave1"]) # Salida:[1] print(mi_lista_dict["clave2"]) # Salida:[]

Función de valor predeterminado personalizada

def predeterminado_personalizado(): return ["valor predeterminado"]

mi_dict_personalizado = defaultdict(predeterminado_personalizado) print(mi_dict_personalizado["clave1"]) # Salida:['valor predeterminado']

Contar apariciones de elementos en una lista, defaultdict es más conciso que dict normal

Usando defaultdict

mi_lista = [1, 2, 3, 1, 2]

Usando defaultdict

contador_dict = defaultdict(int) for i in mi_lista: contador_dict[i] += 1 print(contador_dict) # Salida:defaultdict(<class 'int'>, {1: 2, 2: 2, 3: 1}) print(dict(contador_dict)) # Salida:{1: 2, 2: 2, 3: 1}

Usando dict normal

contador_dict = {} for i in mi_lista: if i in contador_dict: contador_dict[i] += 1 else: contador_dict[i] = 1 print(contador_dict) # Salida:{1: 2, 2: 2, 3: 1}


### deque

> Diferencias entre deque y list:

- deque es cola doble, implementación subyacente es bloques continuos + array de punteros, operaciones izquierda y derecha son eficientes (derecha ligeramente más rápida), por lo que tiene métodos appendleft/append y popleft/pop.
- list es array dinámico, operaciones derechas son mucho más eficientes que las izquierdas, por lo que no tiene appendleft y popleft.
- Por lo tanto, para solo operaciones derechas, list y deque tienen rendimiento similar; para operaciones izquierdas, deque es mucho más eficiente que list.

#### Pila

from collections import deque

1.Pila implementada con deque:

deque es cola doble, implementación subyacente es bloques continuos + array de punteros, operaciones izquierda y derecha son eficientes (derecha ligeramente más rápida), por lo que tiene métodos appendleft/append y popleft/pop.

Por lo tanto, la cima de la pila puede estar al final o al inicio.

pila = deque(maxlen=None) pila.append(1) pila.append(2) print("Después de apilar:", pila) cima = pila[-1] if pila else None print("Elemento superior:", cima) esta_vacia = len(pila) == 0 print("¿Está vacía?:", esta_vacia) tamaño = len(pila) print("Tamaño:", tamaño) pila.pop() print("Después de desapilar:", pila)

2.Pila implementada con list:

list es array dinámico, operaciones derechas son mucho más eficientes que las izquierdas, por lo que no tiene appendleft y popleft.

Por lo tanto, la cima de la pila está al final, operaciones de apilar y desapilar son al final.

pila = [] pila.append(1) pila.append(2) print("Después de apilar:", pila) cima = pila[-1] if pila else None print("Elemento superior:", cima) esta_vacia = len(pila) == 0 print("¿Está vacía?:", esta_vacia) tamaño = len(pila) print("Tamaño:", tamaño) pila.pop() print("Después de desapilar:", pila)


#### Cola

from collections import deque

Diferencias entre cola normal y cola doble:

1.Cola normal: solo puede encolar en un extremo y desencolar en el otro;

2.Cola doble: puede encolar y desencolar en ambos extremos.

Se pueden elegir diferentes combinaciones de append/appendleft y pop/popleft según las necesidades.

cola = deque() cola.append(1) cola.append(2) print(f"Cola después de encolar: {cola}") # Salida: deque([1, 2]) print(f"Ver primer elemento: {cola[0]}") # Salida: 1 print(f"Ver último elemento: {cola[-1]}") # Salida: 2 print(f"¿Está vacía?: {len(cola) == 0}") # Salida: False print(f"Tamaño de cola: {len(cola)}") # Salida: 2 cola.popleft() print(f"Cola después de desencolar: {cola}") # Salida: deque([2])

Estructura Union-Find
-----------------

class UnionFind: def init(self, n): self.padre = list(range(n + 1)) # Array de padres self.rango = [0] * (n + 1) # Rango (altura del árbol) self.contador = n # Número de conjuntos

def buscar(self, x):
    """Buscar nodo raíz + compresión de ruta"""
    if self.padre[x] != x:
        self.padre[x] = self.buscar(self.padre[x])  # Compresión de ruta
    return self.padre[x]

def unir(self, x, y):
    """Unir dos conjuntos (unión por rango)"""
    raiz_x = self.buscar(x)
    raiz_y = self.buscar(y)

    if raiz_x == raiz_y:
        return False  # Ya están en el mismo conjunto

    # Unión por rango: unir árbol más bajo a árbol más alto
    if self.rango[raiz_x] < self.rango[raiz_y]:
        self.padre[raiz_x] = raiz_y
    elif self.rango[raiz_x] > self.rango[raiz_y]:
        self.padre[raiz_y] = raiz_x
    else:
        self.padre[raiz_y] = raiz_x
        self.rango[raiz_x] += 1

    self.contador -= 1  # Disminuir número de conjuntos
    return True  # Unión exitosa

def conectados(self, x, y):
    """Verificar si dos elementos están conectados"""
    return self.buscar(x) == self.buscar(y)

========== Ejemplo 1: uso básico ==========

print("=== Ejemplo 1: uso básico ===") uf = UnionFind(10)

Operaciones de unión

uf.unir(1, 2) uf.unir(2, 3) uf.unir(4, 5) uf.unir(6, 7) uf.unir(7, 8)

Consultar conectividad

print(f"¿Están 1 y 3 conectados? {uf.conectados(1, 3)}") # True print(f"¿Están 1 y 4 conectados? {uf.conectados(1, 4)}") # False print(f"¿Están 6 y 8 conectados? {uf.conectados(6, 8)}") # True

Unir conjuntos diferentes

uf.unir(3, 4) print(f"Después de unir, ¿están 1 y 4 conectados? {uf.conectados(1, 4)}") # True

print(f"Número actual de conjuntos: {uf.contador}") # Salida: 4

Lista de Adyacencia (estructura de almacenamiento)
---------

> Se usa para implementar grafos y árboles (grafos conexos sin ciclos)

import sys sys.setrecursionlimit(10**7) # Establecer límite de recursión, predeterminado 1000 input = sys.stdin.readline

n nodos, m aristas

n, m = map(int, input().split()) ady = [[] for _ in range(n + 1)] # Índices desde 1 son más intuitivos

for _ in range(m): u, v, w = map(int, input().split()) ady[u].append((v, w)) # Almacenar (destino, peso) # ady[v].append((u, w)) # Solo para grafos no dirigidos

Módulo datetime
--------

from datetime import date, datetime, timedelta

Crear objeto fecha =====================

d = date(2026, 3, 30)

Extraer atributos (para condiciones) =======================================

print(d.year, d.month, d.day) print(d.weekday()) # 0=lunes, 6=domingo (diferente a ISO) print(d.isoweekday()) # 1=lunes, 7=domingo (más intuitivo)

Suma y resta de fechas (técnica clave: usar timedelta para recorrer) =======================================================================

Por ejemplo: ¿qué fecha es 100 días después?

nueva_d = d + timedelta(days=100) print(nueva_d) # Salida:2026-07-08

datetime casi no se usa

t1 = datetime(2023, 1, 1, 12, 0, 0) t2 = datetime(2023, 2, 2, 13, 30, 0)

diff = t2 - t1 print(diff.days) # Parte de días de la diferencia: 1 print(diff.seconds) # Segundos restantes después de quitar días: 5400 (1.5 horas) print(diff.total_seconds()) # Total de segundos de diferencia: 2770200.0

Etiquetas: algoritmos Python estructura-de-datos competencias-programacion

Publicado el 7-3 22:07

Friki Work

Funciones y Módulos Esenciales para Competencias de Algoritmos (Python)

Entrada y Salida

Bucles For

Cadenas F

Métodos Integrados sin Importar

Métodos Comunes de Cadenas

strip(): Elimina caracteres especificados al inicio y final, predeterminados espacios en blanco

Solo inicio

Solo final

Busca primera aparición de subcadena.

Si encuentra, devuelve índice inicial; si no, devuelve -1

find() busca desde la izquierda, rfind() desde la derecha

index(),rindex corresponden a find(),rfind(),

la diferencia es que si no encuentra, los primeros lanzan ValueError, los segundos devuelven -1

Métodos Comunes de Listas

Métodos Comunes de Diccionarios

setdefault() establece par clave-valor, si no existe lo añade

keys() devuelve vista iterable de claves

values() devuelve vista iterable de valores

items() devuelve vista iterable de tuplas (clave, valor)

Salida:

a

b

c

Salida:

1

2

3

Salida:

('a', 1)

('b', 2)

('c', 3)

Salida:

a 1

b 2

c 3

Elimina elemento especificado, lanza error si no existe

Elimina elemento especificado, no lanza error si no existe

Usar pop()+insertar()/agregar() y pop_izquierda()+insertar()/agregar_izquierda() también modifica

Orden de importancia:

Esenciales: sys (entrada/salida rápida), collections.deque (BFS, colas, pilas, ventana deslizante)

Frecuentes: collections.defaultdict (grafos, conteo, agrupación), heapq (Top K, Dijkstra, colas prioritarias), collections.Counter (frecuencia, conteo), itertools (permutaciones, combinaciones, producto cartesiano), math (mcd, sqrt, ceil, floor)

Moderados: bisect (búsqueda binaria, inserción en lista ordenada), functools (optimización recursiva, ordenación personalizada), copy (copia profunda)

Menos frecuentes: datetime (cálculo de fechas), funciones especiales de math (comb, perm), operaciones avanzadas de itertools (suma prefija, agrupación)

Devuelve el menor entero >= x

Devuelve el mayor entero <= x

Devuelve raíz cuadrada de x. x debe ser >= 0,否则ValueError

Devuelve e^x

Devuelve logaritmo de x en base base, si no se especifica base, usa e

Devuelve seno, coseno y tangente de x (en radianes)

Devuelve arcoseno, arcocoseno y arcotangente de x (resultados en radianes)

Convierte radianes a grados

Convierte grados a radianes

Devuelve n!

Devuelve mcd de a y b

Devuelve número de combinaciones de n elementos tomados de k en k

Calcula distancia euclidiana entre dos puntos de misma dimensión

Crear heap método 1: desde heap vacío

heap = []

Crear heap método 2: desde lista existente (recomendado, O(n))

Insertar en heap

Ver mínimo sin eliminar

Tamaño del heap

Verificar si está vacío

Eliminar del heap (extrae mínimo)

heapreplace = pop + push (más eficiente)

heappushpop = push + pop (más eficiente)

Parámetro key especifica clave de comparación

Salida:[{'nombre': 'Luis', 'puntuacion': 92}, {'nombre': 'David', 'puntuacion': 90}]

Devuelve todas las permutaciones de elementos del iterable

Si se especifica r, devuelve permutaciones de longitud r

Salida: (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

Salida: [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

Sin repeat, calcula producto cartesiano de múltiples iterables

Con repeat, calcula producto cartesimo del iterable consigo mismo repeat veces

Salida: (1, 'a') (1, 'b') (1, 'c') (2, 'a') (2, 'b') (2, 'c') (3, 'a') (3, 'b') (3, 'c')

Con repeat, calcula producto cartesimo del iterable consigo mismo repeat veces

Salida: (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)

Conecta múltiples iterables en un único iterador