Explicación de las preguntas reales de Noip

Declaración: El código y los ejemplos utilizados en este artículo provienen de "Diseño y análisis de algoritmos informáticos" (Editor en jefe Wang Xiaodong, Electronic Industry Press). Hice algunas modificaciones al código para poder ver los resultados del tema en modo gráfico tc.

Título: En un tablero de ajedrez que consta de (2 k) * (2 k) cuadrados, hay un cuadrado especial que es diferente de otros cuadrados, que se llama cuadrado especial. Este tablero de ajedrez se llama especial. tablero de ajedrez. Ahora es necesario llenar el resto del tablero de ajedrez con cuadrados en forma de L (nota: el cuadrado en forma de L se compone de 3 celdas. También es el triángulo estúpido tabú en Go, con cualquier dirección). los cuadrados no pueden superponerse ni cubrirse. La forma del cuadrado en forma de L es la siguiente:

■■*■■***■*■

■******■*■■*■ ■

La solución al problema adopta el método de divide y vencerás, es decir, la subpregunta y la pregunta general tienen la misma forma. Dividimos el tablero de ajedrez, y el tablero de ajedrez después de cortarlo una vez se muestra en la Figura 1. Podemos ver que el tablero de ajedrez está cortado en cuatro subtableros del mismo tamaño, y el cuadrado especial debe ubicarse en uno de los cuatro subtableros. Supongamos que el cuadro especial está ubicado en la esquina superior derecha como se muestra en la Figura 1. Colocamos un cuadro en forma de L (relleno de gris) en la posición en la imagen. De esta forma, cada subtablero tiene un "cuadrado especial", y continuamos dividiendo cada subtablero de esta manera hasta que el tamaño del subtablero sea 1.

El número de cuadrados en forma de L utilizados es (4 K-1)/3 y el tiempo del algoritmo es O (4 K), que es una solución óptima asintótica.