Preguntas sobre noip
La segunda pregunta es en realidad ingresar n, para que puedas calcular qué es (2 n-1)% 10000. Debido a que N = maxlongint, si se calcula directamente, O (N) expirará, por lo que se utiliza el algoritmo de divide y vencerás. La idea es muy simple, es decir:
2 n = (2 n). /2) * (2n/2 ). De esta forma, 2 n/2 se puede calcular una vez y no es necesario calcular la segunda multiplicación. La complejidad es O (logN), muy rápida. En cuanto a %10000, %10000 es suficiente cada vez.
El tercer problema es la clásica especificación dinámica de emparejamiento f(i, J), que representa la náusea mínima producida por el emparejamiento de la primera I en la secuencia A y la primera J en la secuencia B. Entonces:
F(i,j)=f(i-1,j-1)+abs(v[i]-v[j]) (elección) o f(i-1,j )(no seleccionar).
El más pequeño. Debido a que j es relativamente pequeño, no puede seleccionar la segunda secuencia perdida cuando la pierde.
El cuarto problema es la búsqueda extensiva de la memoria. Cada vez que encuentro un punto, si mi consumo actual es menor, actualizo mi valor de consumo mínimo a este punto. Una vez que se borra la cola, se puede generar el valor correspondiente. Tenga en cuenta que la programación dinámica no se puede utilizar para este problema porque existe un desvío deliberado.
La quinta pregunta debería ser sobre matrices de árboles. Realmente no puedo hacerlo. Simulemos 30 minutos.