Preguntas del examen semifinal Noip de años anteriores
Ser zrw por un konjac
1 Descripción general de la pregunta (porque la pregunta no se ha publicado al escribir)
.Varios amigos envían su propia información (cumpleaños). Cada amigo solo enviará la información que conoce al único, pero puede recibir mucha información. Después de recibir la información, se la enviará al único. En la siguiente ronda, uno de ellos (Secret Love 233333) preguntó cuántas rondas tomaría antes de recibir el mensaje que envió originalmente.
Entrada: La primera línea es un número entero n, lo que indica que hay n personas.
En las siguientes n líneas, cada línea tiene un número J. Supongamos que esta es la I-ésima línea excepto la primera línea, entonces J significa que la I-ésima persona solo pasará la información a la J -ésima persona.
Salida: un número entero que indica al menos cuántas rondas serán necesarias para que se le devuelva su información.
Entrada de muestra:
cinco
2 4 2 3 1
Salida de muestra:
tres
p>
Proporción de datos: 100 nlt
2. ¿Qué tipo de algoritmo se necesita?
Según el tamaño de los datos, podemos juzgar aproximadamente cuántos algoritmos eficientes se necesitan y, a veces, incluso podemos adivinar qué algoritmo se utiliza para este problema. Para esta pregunta, 60 es probablemente un algoritmo O (n 2), que generalmente es un retroceso violento y una búsqueda extensa violenta (lo vi en la barra NOIP).
Si se requiere AC, la eficiencia del algoritmo debe ser al menos O(nlogn) (aquí log se basa en 2 en lugar de 10).
Sin embargo, este problema tiene un algoritmo O(n), que se analizará a continuación.
Hagamos un dibujo (puede que sea feo, pero se ve bien)
Sabrás lo que estás haciendo si haces un dibujo.
Tome datos de muestra como ejemplo:
Podemos encontrar fácilmente que 2, 3 y 4 forman un anillo, mientras que 1 y 5 son inútiles...
Por lo tanto, en el anillo 234, se necesitan tres rondas para enviar la información porque cada ronda puede enviar la información conocida en la ronda anterior a la única persona siguiente.
Dibuja más (porque soy vago, solo hice un pequeño dibujo de una situación especial):
(Siento que tu círculo está muy desordenado.)
Podemos ver que 1, 5 y 6 se convierten en un anillo, 2, 3, 4 y 8 también se convierten en un anillo, y 7 y 9 son salsa de soja.
Entonces, para estos dos anillos, debido a que cada ronda puede pasar la información de la ronda anterior a la siguiente persona, es obvio que 1, 5 y 6 se pasan antes, tres rondas.
Para decirlo sin rodeos, es encontrar el anillo más pequeño de la imagen.
4.ABCD, ¿cuál eliges?
Así que existen varios algoritmos de ruta más corta para resolver este problema, pero creo que aún es necesario estudiar la complejidad del tiempo. Para ser honesto, no sé si estos algoritmos pueden comunicarse. Por ejemplo, en el algoritmo SPFA, inicialmente O(kE)k es una constante, aproximadamente igual a 2, y E es el número de aristas. La estimación aquí es O (nkE), que es O (nE), porque cada punto solo apuntará a un borde, por lo que el borde es N, que es O (n 2, si no está optimizado, es probable que lo haga). explotar (preste atención a mi redacción).
Algunas personas en Tieba también dijeron que es un conjunto de búsqueda paralelo, que se dice que está habilitado por AC, pero no sé cómo planea hacerlo. Creo que debería ser difícil de entender.
Para decirlo sin rodeos, todavía tenemos que tomar este camino.
Una cosa está clara, dado que una persona solo pasará información a otra persona, podemos usar una matriz unidimensional para almacenar esta relación. Supongamos que la matriz es padre [], entonces padre [i] significa que la I-ésima persona puede enviar información a la I-ésima persona, ahorrando así espacio y tiempo de acceso.
6. Entonces aquí viene la pregunta...
El excavador... oh no, ¿cuál es la mejor técnica de optimización?
Muchas personas pueden quedar atrapadas aquí.
Entonces, analicemos los datos de muestra y echemos un vistazo:
¿Sientes que cuanto más miras esta imagen, más incómoda se vuelve? )
Si cada punto está sujeto a SPFA, el algoritmo del camino más corto de Freud, entonces los dos transeúntes 1 y 5 son completamente inútiles. Además, para 2, 3 y 4, lleva mucho tiempo si todos caminan.
¡Tienes que pensarlo, pero hay 100 formas oficiales de obtener datos para que no puedas AC!
Pero obviamente, si se utiliza una matriz para registrar si este punto ha sido visitado por otros, ¿no sería trágico si fuera descubierto por el anillo de un transeúnte?
7. Salsa de soja, basura, ¡tírala!
Cómo deshacerse de la salsa de soja es un gran problema, pero es necesario saber qué es la salsa de soja para solucionarlo.
¡El punto que no puede formar anillo es la salsa de soja!
Entonces, ¿cómo podemos evitar que se forme un anillo?
Shabi, nadie le dio información, solo debe tener su propia información, y no hay forma de formar un bucle, como 5:
Si es inútil, ¿por qué? conservarlo? Baja el arma.
Luego encontrarás que 1 también es salsa de soja, y luego tiras:
Movió 2. La penetración de 2 no es 0, por lo que no se realiza la operación.
El resultado fue un anillo perfecto.
Para decirlo sin rodeos, significa eliminar el punto con una penetración inicial de 0 y reducir la penetración del punto puntiagudo en uno. Si la fuerza de penetración del punto puntiagudo después de la resta también es 0, continúe con la misma operación hasta encontrar un punto donde la fuerza de penetración después de la resta no sea 0.
Para aquellos que son más débiles que yo:
en grados: en un gráfico, para un punto determinado, el número de aristas que conducen a ese punto es en grados. Asimismo, el grado relativo es el número de lados desde este punto hasta otro punto. Por ejemplo, en la muestra, el grado de entrada de 5 es 0 y el grado de salida es 1; el grado de entrada de 1 es 1 y el grado de salida es 1 y el grado de salida es 2; -el grado es 1.
Por supuesto, también es una buena opción establecer una matriz visit[] para indicar si este punto ha sido visitado, porque se usará más adelante. Establezca el acceso del punto con profundidad 0 a ya visitado.
Para el segundo gráfico de ahora, también hice el mismo proceso y el gráfico resultante es así:
¿Te sientes mejor? )
Si aún no lo entiendes, echa un vistazo al siguiente breve párrafo:
"
Mi idea es mirar 2 4 2 3 1.
Descubrí que la quinta persona no recibió el mensaje.
Así que lo probé.
En ese momento, no recibí el mensaje. tampoco
Entonces 1. También es t
Solo quedan dos, tres o cuatro personas
Entonces la salida es 3
.” - una cita más popular del poeta Eric de Tieba ID.
Para eliminar puntos y bordes, se pueden utilizar tanto dfs (búsqueda en profundidad) como bfs (búsqueda en amplitud), y la eficiencia debería ser similar. Me gusta presumir y hacer cola, por eso uso Guangsou.
El peor de los casos, n=200000, 1 punto a 2, 2 puntos a 3... hasta el final 199998 puntos 19999, 199999 puntos 200000, 200000 puntos 19999, o(.
Está bien, el problema de la "salsa de soja" está resuelto, todo lo que queda es concentrarse en resolver el problema del anillo mínimo
8 Visita la matriz para crear milagros
Ya sabes, siempre habrá un detalle involuntario que afecta el resultado.
Entonces, la mierda puede ser complicada, pero la bandera no se puede establecer.
Primero, déjame decir algo. Un amigo en la barra de publicaciones (bueno, la persona citada anteriormente) conoce el algoritmo anterior, pero como no ha aprendido demasiados algoritmos de teoría de grafos, no sabe cómo jugar el anillo mínimo, así que lo explicaré.
Para ser honesto, nunca he aprendido muchos algoritmos de teoría de grafos → _→
Como acabo de decir, usar la matriz unidimensional de mi padre para guardar este gráfico ahorra espacio y tiempo. .
Entonces solo necesitamos encontrar los puntos cuyo grado no es 0 (de hecho, en este momento solo deberían quedar puntos con grado 1, porque cada punto solo puede estar en un anillo, por lo que puedes haga varios dibujos. Prueba), y luego llame al anillo con la matriz principal (esto es similar a un conjunto de búsqueda paralelo).
Sin embargo, si se llama al bucle cada vez que se encuentra un punto, el peor caso es O(n^2).
¿Qué pasa con el O(nlogn) acordado?
Sin pelear ni pelear, ¿cuál es el beneficio de visitar? ¡Dáselo a quien sea adecuado!
Para la muestra, después de visitar el punto 2 y los anillos 2, 3 y 4, se han visitado los puntos 3 y 4. Debido a que la longitud del mismo anillo debe ser la misma, no es necesario buscar. para los puntos 3 y 4 nuevamente 4.
Luego use la matriz de acceso para registrar si el punto ha sido visitado. Al visitar un bucle, cada vez que visita un punto, lo marca como visitado y puede omitirlo la próxima vez que visite ese punto, ahorrando tiempo.
Es por eso que el punto con una tasa de penetración de 0 en este momento debe establecerse en un punto que ya ha sido visitado: sin salsa de soja.
Peor caso: n=200000, 1 punto a 2, 2 puntos a 3...199999 puntos a 200000, 200000 puntos a 1.
Bucle For: n veces
Al buscar: n veces
u O(n)
Resumen
He hecho algunas preguntas sobre el segundo tema del día 1 del grupo de mejora en los últimos años, pero creo que esta vez debería ser lo más fácil (pero esta vez no escribiré sobre el tercer tema. Mirando los datos especiales solo me engañarán 30 puntos), lo que significa que todos obtendrán puntos según el tema de mañana (cierto partido en FJ colocó una bandera diciendo que si alguien habla sobre el tercer tema en FJ AC, se transmitirá. vivir).
Creo que, realmente, el dibujo es la clave de este problema (recuerdo que mi antiguo profesor de competición, el Sr. Wang, solía decir que una cosa es la combinación de números y formas). Haga más dibujos y simule más y podrá encontrar fácilmente soluciones a los problemas. Estoy demasiado débil. Siempre me toma alrededor de una hora y menos de media hora terminar una o dos preguntas. Personalmente, creo que este algoritmo debería considerarse como uno de los algoritmos más eficientes para este problema, porque excepto para la búsqueda final, no hay cálculos repetidos. Y debería ser el algoritmo más fácil de entender, por lo que AC no debería tener problemas. En cuanto a otros algoritmos, soy demasiado débil para entenderlos.
Por cierto, he adjuntado una captura de pantalla de mi cara después de que el maestro la publicara como contraejemplo (el código también se publicará más adelante):