Cómo evaluar las preguntas de la prueba semifinal del grupo de mejora NOIP2016
Para ser honesto, debido a que no estoy en China, no puedo participar en el último NOIP de mi carrera en OI. Para reducir los arrepentimientos, me gustaría expresar algunas opiniones personales sobre las preguntas del examen. ......
--¡El examen ha terminado! --
Si los jugadores antiguos no conocen las preguntas específicas, simplemente escuche el resumen de las preguntas QwQ
1 Sin mencionar la simulación, no sabrá cómo hacerlo. programa en el examen
2. Primero, divida el camino en dos mitades desde LCA, luego mire las dos mitades del camino de arriba a abajo o de abajo hacia arriba, deje que di represente la profundidad de el i-ésimo punto, luego divida la profundidad del i-ésimo punto y luego divida el i-ésimo punto La profundidad de, y luego la profundidad del i-ésimo punto. La profundidad del punto i-ésimo, entonces la consulta que puede afectar el caminante de arriba hacia abajo siempre satisface wi - di = Constante, y la consulta que afecta el caminante de abajo hacia arriba es wi + di = Constante. A continuación, use la constante calculada para clasificar la consulta, divida la cadena de arriba hacia abajo en el árbol en dos categorías, el extremo inferior es +1 y el extremo superior es -1, y luego haga la suma del subárbol para cada tipo de consulta para obtenga cada punto La respuesta es que no puede hacer n dfs al sumar subárboles, pero puede resolverlo con un dfs siempre que se preprocese el ancestro de consulta similar más cercano.
3. Tenga en cuenta que el camino entre las dos rondas solo está relacionado con si hay una solicitud en las dos rondas. Se preprocesan cuatro situaciones de longitud de ruta esperada (ninguna de las partes aplica, la ronda anterior aplica y). se aplica la siguiente ronda), ambas partes se postulan), y luego simplemente haga el dp de mochila directamente f[i][j][k] significa que el j-ésimo estado de la solicitud de la j-ésima que se ha aplicado en el. La ronda i anterior es k (k es 1, lo que significa que la solicitud es 0 significa que ya se ha aplicado), enumere la siguiente ronda de solicitudes, f [i] [j] [k] significa que el i-ésimo estado de la solicitud entre las j- Las que se han aplicado en la i ronda anterior son k (k es 1, lo que significa que la solicitud no se ha realizado y 0 significa solicitudes aún no aplicadas), enumera la siguiente ronda de solicitudes. Postular), simplemente enumere si postularse para la siguiente ronda o no.
--Lo anterior es un código confuso para resolver el problema. Simplemente no lo entiendo. De todos modos, no escribí el código. Es solo una corriente de conciencia (niebla)--
En primer lugar, en los últimos años, la dificultad ha aumentado significativamente. Si está interesado, puede echar un vistazo a la segunda pregunta del año pasado: http://uoj.ac/problem/146 Creo que es la última. Segunda pregunta del año... ¿Cómo debería decirlo? Esto también lo puedo resolver yo, estoy más convencido. Para ser honesto, la segunda pregunta de este año ha alcanzado el nivel de dificultad de la tercera pregunta de NOIP. Incluso muchos maestros no han pensado en cómo hacerlo, sino que utilizan estructuras de datos avanzadas (como árboles de presidente de combinación heurística) para forzar consultas de mantenimiento. para solucionarlo, y también existe el riesgo de quedarse estancado con constantes.
Sin embargo, el algoritmo anterior solo necesita derivar el LCA y luego realizar un recorrido profundo del árbol para resolverlo. Detrás del conocimiento simple hay una mayor dificultad de pensamiento.
Estoy de acuerdo con este tipo de preguntas, pero tal vez la segunda pregunta del primer día sea un poco difícil, así que no sé cómo les fue a los concursantes.
En cuanto a la tercera pregunta, la encuentro muy confusa. Siempre que comprenda el significado de las expectativas, la tercera pregunta puede considerarse fácilmente como un modelo de mochila muy simple, no requiere pensar demasiado y es una "pregunta fija" en la programación dinámica. Dado que esta es la primera vez que NOIP diseña expectativas matemáticas, es probable que la dificultad de los jugadores radique en comprender las expectativas matemáticas en lugar de pensar en cómo resolver los problemas. Por supuesto, esto también puede deberse a la dificultad de producir preguntas de programación dinámica de alta calidad, y la programación dinámica es una idea importante que debe probarse.
En general, la dificultad ha aumentado, la cantidad de código ha aumentado y la prueba de pensamiento también ha aumentado. ¿Quizás tenga sentido cambiar la segunda y tercera pregunta (niebla)?
--El examen del día 2 ha terminado--
Primero resolvamos el problema del flujo de conciencia.
1. Encuentre directamente el número de combinaciones en el sentido del módulo k, y luego el prefijo 2D y cuente el número de ceros.
2. Tenga en cuenta que cuando se cortan dos lombrices de tierra adyacentes, el aumento de longitud no excederá q, y la longitud de las lombrices de tierra antes del corte no aumenta en q segundos, por lo que las lombrices de tierra después del corte deben ser más cortas que las lombrices de tierra antes del corte, por lo tanto, se abren tres colas para mantener las lombrices de tierra iniciales, la primera mitad de las lombrices de tierra y la segunda mitad de las lombrices de tierra nuevas se pueden agregar directamente al final de la cola. lineal.
3. La compresión del estado DP, f[s] significa que se han eliminado s pigs del conjunto, cuántos más deben lanzarse. Tenga en cuenta que se determina que los dos pigs y el punto lejano son parábolas. , y se enumeran directamente La transferencia de dos cerdos es n ^ 2. Tenga en cuenta que todos los cerdos serán eliminados al final, por lo que el cerdo con la marca más pequeña que no haya sido eliminado definitivamente será eliminado. en esta ronda y luego enumerar la otra! La complejidad de los cerdos es n, y el preprocesamiento del conjunto de cerdos que pueden eliminarse mediante la parábola determinada por dos cerdos se puede completar con transferencias O(n), por lo que la complejidad es O(2^n*n).
--Maravilloso ejercicio--
2A. Escuché que la constante del árbol de parábola izquierda es muy pequeña, entonces, ¿por qué no escribir una? Tal vez pueda superarla.
2B. El montón binario es demasiado bajo. Usamos un montón de 32 bifurcaciones y utilizamos operaciones de bits para mantener el montón, que parece atascarse en el espacio.
3A. Para cada subconjunto, determine la capacidad de destruirlo con un pájaro a la vez. El coeficiente de habilidad es 1; de lo contrario, es 0 y se obtiene la serie de potencia establecida. Podemos dividirlo por la mitad k veces, y luego encontramos el conjunto y la convolución de la serie de potencias de este conjunto k veces, y determinamos si el coeficiente de todo el conjunto es anterior a> 0. Si es mayor que 0, significa. se puede eliminar. Esta complejidad es O (2 ^ n * n * logn) y la constante de la Transformada rápida de Walsh (FWT) es muy pequeña, por lo que parece relativamente fácil ejecutarla.
3B Dundun dijo: De hecho, FWT es lo mismo que módulo, también puede ser una n Jaja, no sé cómo hacer esto. Yjq me enseñó el algoritmo 3.
Creo que NOIP ha mejorado mucho en términos de calidad de la propuesta (comparable al D1T3 del año pasado), es decir, presta más atención al examen del pensamiento. Después de examinar la capacidad de codificación, se examina la capacidad de pensamiento correspondiente. será revelado. El resultado correspondiente de centrarse en el pensamiento es un aumento sustancial de la dificultad, lo que aumentará la diferenciación de los jugadores de NOIP en los niveles intermedio y avanzado.
En general, apruebe las preguntas del examen~
Adjunto: no he mirado algunas de las configuraciones de puntuación, así que no sé si son amigables para OI novatos.