Semifinales del NOIP C
noip no probará algoritmos de muy alta gama. Incluso el núcleo de la red de árboles del año pasado puede pasar nueve puntos usando el algoritmo O (N＾3). . . Por lo tanto, noip es principalmente la aplicación de algoritmos básicos, programación dinámica y preguntas basadas en agua que dependen principalmente de la habilidad y el cuidado de la programación. En las preguntas que hiciste antes de las semifinales, mejora aún más. Para la programación dinámica, solo puedes ver las explicaciones de algunas preguntas clásicas y hacer más preguntas. En cuanto al algoritmo básico, es muy importante dominar.
Para preguntas pasadas, el grupo de popularización debe hacer la dinámica. Si las preguntas del grupo de mejora son Si no eres demasiado mayor, es mejor hacerlas todas. Por supuesto, el tiempo es limitado. . .
Para revisar los algoritmos básicos, escribiré aquí lo que se me ocurre que se puede utilizar. No consideraré algoritmos demasiado avanzados. Para algoritmos con el mismo efecto, básicamente consideraré algoritmos simples. unos. Escríbalo primero, luego ajústelo y revíselo lentamente. . .
1. Estructura de datos simple:
Evaluación de expresiones (conozco el algoritmo, pero no lo escribiré) Cómo escribir una cola circular (es decir, el valor inicial es 0, y la entrada y salida es (s+1)) mod n, ver SPFA)
Funciones básicas de cadena (deben memorizarse nuevamente al final)
Hash (Cadena La cremallera mod de expansión de Cantor maneja conflictos)
2. Clasificación y procesamiento de datos
Seleccione o ordenación rápida por burbujas (incluida la selección rápida) Clasificación de pila de tiempo lineal (clasificación de filtro inferior e inserción de filtro superior) Múltiples palabras clave (ordenar según cada campo de datos y luego ordenar por separado, ya no se escriben) Alta precisión (buscando modular) Búsqueda binaria
3. Estructura de datos no lineal
Árbol: transversal y otros trabajos en el proceso transversal (estadísticas, DP, etc., también se pueden usar para encontrar los bordes de un anillo en un árbol sin raíz, no lo escribiré) El ancestro común más cercano (encuentre el ancestro común más cercano ***ancestro del árbol y el camino entre dos puntos, común a todo tipo de árboles) y busca el conjunto Árbol
Gráfico: Árbol de expansión mínima, camino más corto (SPFA, DJ, Freud) Circuito de Euler (DFS), expanda y elimine el borde cada vez, si no quedan bordes, luego Almacene, pero no retroceda la operación de eliminación, así que no la escribiré más) Encuentre el punto de corte (riego, ignore O (n ) algoritmo de gama alta) Encuentre el componente fuertemente conectado y encuentre la clasificación topológica de la ruta crítica del bucle mínimo
4 Algoritmo de teoría de números
p>Divisores comunes, múltiplos comunes, permutaciones de números primos. , conversión combinatoria, eliminación gaussiana?
5. Consejos: Matriz rodante (ti:=i mod 2, active 0 y 1) Procesamiento de discretización