2. Preguntas interesantes de Hankson (son.pas/c/cpp)
Análisis
Examina principalmente el conocimiento matemático Encuentra el máximo común divisor mediante división euclidiana. Todo el mundo lo conoce, así que no diré más.
Algoritmo 1:
Enumere exhaustivamente (b1), la puntuación esperada es 50.
Algoritmo 2:
Como mcd(x, a0)=a1, también puedes establecer x=p*a1.
Entonces lcm(x,b0)=lcm(p* a1,b0)=p*a1*b0/gcd(p*a1,b0)=b1
Podemos obtener p=b1* gcd(p* a1,b0)/a1/b0, puedes encuentre p después de enumerar gcd(p*a1,b0), y luego encuentre x, simplemente verifique si gcd(p*a1,a0) es a1.
Porque gcd(p*a1,b0) es un divisor de b1, la cantidad de enumeración es O(sqrt(b1)) y la complejidad final es O(N*sqrt(b1)*log(b1)), puntuación esperada 100.
Algoritmo 3:
Debido a que mcm(x,b0)=x*b0/gcd(x,b0)=b1, entonces x/gcd(x,b0) =b1/b0 también podrías descomponer b1/b0. en factores primos, y x tiene un divisor a1. La búsqueda con la tabla de números primos también puede producir resultados rápidamente. La eficiencia no es fácil de analizar y la puntuación esperada es 100.
3. Comercio óptimo (. trade.pas/c/cpp)
Análisis
Algoritmo 1:
Combinado con escala de datos Para el 30% de los datos, puede utilizar una alternativa. Algoritmo cúbico similar a floyed para encontrar el máximo y el mínimo Para el 50% de los datos, se puede ver en el significado de la pregunta que esta parte de los datos está ordenada topológicamente y dp se puede usar directamente. comenzando desde el primer punto y llegando al i-ésimo punto, apunte la bola de cristal que se puede comprar con la menor cantidad de dinero. La ecuación de transición de estado es la siguiente: F = min (F [j], A). El i-ésimo punto puede llegar al N-ésimo punto, luego actualice la respuesta con A-F. Este algoritmo necesita combinar datos, la complejidad de la programación es grande, si la clasificación topológica está bien escrita, puede obtener más de 50 puntos. (50-80).
Algoritmo 2:
Fuerte Después de conectar las ramas, es obvio que el gráfico todavía está topológicamente ordenado. Sin embargo, se puede resolver con un dp similar. , la fuerte conectividad parece exceder el esquema de la liga y la complejidad de la programación es alta. Dado que el método es muy clásico, no se presentará en detalle. Complejidad O (N + M), puntuación esperada 100.
Utilice spfa alternativo (es decir, encuentre los valores máximo y mínimo) para encontrar el punto de partida desde el primer punto. El costo mínimo para comprar una bola de cristal desde otros puntos después de revertir todos los puntos. bordes, comenzando desde N puntos, encuentre el costo máximo para vender la bola de cristal desde el punto N hasta el punto i. Este costo corresponde a la imagen original. El beneficio máximo que se puede obtener desde el punto i hasta el punto N. -ésimo punto. Para cada punto, simplemente actualice la respuesta con el beneficio máximo y el costo mínimo. La complejidad es difícil de estimar, pero la eficiencia del gráfico disperso spfa está muy garantizada y la complejidad de la programación es relativamente excelente. algoritmo. La puntuación esperada es 100.