He comenzado la programación competitiva y puedo resolver el codificador superior Div 2 250 y div 2 500 cómodamente y, a veces, div2 1000. Pero me quedo estancado cuando algunas de las soluciones son más de naturaleza matemática y no con respecto a algoritmos o DS.

Answer 1

Es más de naturaleza algorítmica que matemática, al menos según el lenguaje común de programación competitiva.

Así es como resuelve (o al menos, cómo resolví) este problema en particular:

• Necesitamos encontrar el número total de subcadenas [L..R] (indexación desde 0) que tienen al menos una subcadena de K consonantes consecutivas (llame a [L..R] una subcadena válida)
• Para una R dada, cuentemos cuántas L existen de modo que [L..R] sea válido
• Sea [i..j] la última subcadena de K consonantes consecutivas de modo que j <= R. Entonces [L..R] es válido para L = 0,1 … i, dando un total de i + 1 subcadenas válidas
• Por lo tanto, nuestro problema se reduce a encontrar el comienzo de la última subcadena de K consonantes consecutivas para cada R. Esto se puede hacer mediante programación dinámica estándar.

//The beginning position of the latest substring of K consecutive consonants int latestbegin=-1; //The current length of consecutive consonants int consonants=0; long long answer=0; for(int R=0;R=K) { //Update the latest valid position for L latestbegin=R-K+1; } } answer+=latestbegin+1; } return answer; 

La programación dinámica no se considera demasiado matemática en las competencias de programación al menos. Esa palabra generalmente está reservada para la teoría de números y la geometría avanzada y otras cosas que no se espera que un codificador de nivel IOI sepa. Cualquier libro de algoritmos estándar le dará una introducción decente a la programación dinámica y otras técnicas algorítmicas que necesita para los concursos de programación. Pero tendrá que practicar mucho para resolver la mayoría de los problemas, ya que el DP generalmente no es muy obvio. Quora tiene un tema completo dedicado a ello. ahmed-aly.com tiene una lista de problemas de DP. Buena suerte.