Gnirut

Para facilitar la discusión, usemos las siguientes definiciones:

• Definiciones 2.1. Muchas de las secuencias que son rimas binarias se alternan de una rima binaria ~S~ se expresan en ~(X_S, Y_S)~, donde ~X_S~ denota el número de secuencias impares y ~Y_S~ representa el número de secuencias pares.

Subpregunta 1

Tenga en cuenta que la longitud máxima de una rima binaria satisfactoria S es A + B. Por lo tanto, estamos Puede utilizar la fuerza bruta para producir todas las rimas binarias con una longitud que no exceda A + B en profundidad. ~O(2^{A + B})~. Después de eso, también podemos verificar el número de secuencias de rimas binarias que se alternan en ~O(2^{A + B})~. Con esto, podemos buscar las rimas binarias que queramos. Esta solución tiene una complejidad de ~O(2^{2^{A+B}})~

Subpregunta 2

Para una rima binaria S con muchas rimas binarias alternas (X S, Y S), entonces: El número de secuencias de rimas binarias alternativas de S0 es (X S, Y S + X S) El número de secuencias alternas de rimas binarias de S1 es (X S + Y S + 1, Y S) Por lo tanto, el cálculo del número de secuencias alternas de versos binarios se puede hacer en O (| S |). Para Para resolver esta subpregunta, simplemente podemos reemplazar la búsqueda por el número de secuencias de esta manera. Esta solución tiene una complejidad de \(O (2^{A + B} × (A + B) + Q × (R [i] - L [i]))\).

Subpregunta 3

Usando las observaciones del subsuelo anterior, podemos verificar si alguna rima binaria cumple mediante programación dinámica (DP). El estado del DP es (X S, Y S) que es resultados anteriores, con la transición que sigue a la observación en la subpregunta 2. Defina la función f (X S, Y S) como una función que verifica si con muchas secuencias de rimas binarias alternativamente (X S, Y S) podemos lograr muchas secuencias de rimas binarias alternas (A, B).

La verificación se realiza llamando a f (1, 0). Dado que para cada estado (X S, Y S) se aplica X S ≤ A e Y S ≤ B, la complejidad de este DP es O (AB). Para encontrar rimas binarias satisfactorias, podemos retroceder usando DP la. Esta solución tiene una complejidad de O (AB + Q × (R [i] - L [i])).

Subpregunta 4

Para resolver este subsuelo, considere la siguiente entrada:

Lema 2.1. Si hay una rima binaria que tiene tantas secuencias, la rima binaria se turnará para tantas (A, B), entonces solo la rima binaria tiene tantas secuencias como la rima binaria (A, B).

Prueba. Mire detrás de la búsqueda para llenar rimas binarias. Tenga en cuenta que cuando rima el binario S tiene muchas secuencias alternas de rimas binarias (X S, Y S), entonces:

• Si X S> Y S (más impar que par), entonces S debe tener la forma T1, donde Y T = Y S y X T = X S - Y S - 1

• Si X S ≤ Y S (no más impar que par), entonces S debe tener la forma T 0, donde X T = X S y Y T = Y S - X S

4 Por lo tanto, se puede determinar que si hay una rima binaria que satisface, solo la rima binaria servirá. Realizar.

Usando estas entradas y pruebas, podemos buscar rimas binarias que se llenen desde atrás en O (A + B), agregando carácter a carácter. Esta solución tiene una complejidad de O (A + B + Q × (R [i] - L [i])).

Subtarea 5

Dado que Q = 0, para esta subtarea es suficiente comprobar si alguna rima binaria contiene múltiples las secuencias de la rima binaria se alternan tanto como (A, B). Tenga en cuenta que podemos acelerar la solución anterior haciendo uso del módulo (similar Algoritmo de Euclides). Esta solución tiene una complejidad de O (log (min (A, B))).

Subtarea 6

En lugar de mantener rimas binarias completas que se llenan en forma de cadenas, podemos almacenar repeticiones: hermano, el mismo personaje. Por ejemplo, la rima binaria 1111001 la almacenamos como [(0 1 0, 4), (0 0 0, 2), (0 1 0, 1)].

Recuerda el número de iteraciones de la solución 5 es solo O (log (min (A, B)), podemos almacenar la rima binaria satisface simplemente almacenando O (log (min (A, B)) repeticiones de caracteres en forma de matriz. responder cada pregunta, podemos buscar caracteres en el índice x iterando en una matriz hemos salvado. Esta solución tiene una complejidad O (log (min (A, B)) + Q × (R [i] - L [i]) × log (min (A, B))) = O (Q × (R [i ] - L [i]) × log (min (A, B))), y es la solución para obtener el valor total en este problema.