Semifinales del NOIP C

Noip no tiene algoritmos de muy alta gama. Incluso el núcleo de la red de árboles del año pasado puede lograr una puntuación de nueve puntos utilizando el algoritmo O (n ^ 3). . . Por lo tanto, noip depende principalmente de RP para la aplicación de algoritmos básicos, programación dinámica y problemas de agua, principalmente debido a la competencia y la precaución en la programación. No hay una buena manera de hacer esto. Sólo puedo mejorarlo lentamente a través de las preguntas que hice antes de la revancha. La programación dinámica sólo se puede explicar con algunas preguntas clásicas y hace mucho más. En cuanto al algoritmo básico, el dominio es importante.

Con el paso de los años, el grupo general tiene que hacer las preguntas, y el grupo avanzado tiene que volver a hacer las preguntas, aunque no sean muy mayores. Por supuesto que el tiempo es limitado. . .

Repasar algoritmos básicos. Escribí todo lo que se me ocurrió que podría usarse aquí. No consideré algoritmos demasiado avanzados, sino básicamente algoritmos simples. Escríbalo primero, luego ajústelo y revíselo lentamente. . .

1. Estructura de datos simple:

Evaluación de expresiones (comprender el algoritmo, pero no escribir) el método de escritura de la cola circular (es decir, el valor inicial es 0, el acceso). El valor es (s 1 ) mod n, ver SPFA).

Funciones básicas de string cantor (recítalas nuevamente al final)

Hash (string cantor extiende mod zip para manejar conflictos)

2. procesamiento

Seleccionar o burbujear filas rápidas (incluida la selección rápida) filas de pila de tiempo lineal (ordenar en la pantalla inferior, insertar en la pantalla superior) palabras clave múltiples (ordenar por cada campo de datos y luego ordenar por separado, sin escritura) Método de búsqueda binaria de alta precisión (Buscar modularidad).

3. Estructura de datos no lineal

Árbol: recorrido y otros trabajos en el proceso transversal (estadísticas, DP, etc.), también se puede utilizar para encontrar los bordes de un anillo en un árbol sin raíces, no lo escribiré). Se busca el último ancestro común (encontrar el camino entre el ancestro común más cercano de un árbol y dos puntos, que es común a todos los árboles) para encontrar el árbol.

Figura: Ruta más corta del árbol de expansión mínima (SPFA, DJ, Freud) La ruta de Euler (DFS) es suficiente, los bordes se expanden y eliminan cada vez. Si no hay bordes, se almacenan, pero. La operación de eliminación no retrocede ni escribe). Encuentre el punto de corte (riego, ignore el algoritmo de gama alta O (n)) y el componente fuertemente conectado para encontrar la clasificación topológica de la ruta crítica del círculo mínimo.

4. Algoritmo de teoría de números

Divisores comunes, múltiplos comunes de números primos, permutaciones y combinaciones, transformación binaria, ¿eliminación gaussiana?

5. Consejo: Discretiza la matriz rodante (ti:=i mod 2, abre 0 y 1).