Preguntas semifinales del grupo de mejora NOIP2007

Ingrese un número n (n

Entrada de muestra:

ocho

2

Cuatro

2

Cuatro

Cinco

100

2

100

Resultado de muestra:

2 3

4 2

5 1

100 2

Segunda pregunta: Expansión de cadenas expandidas

Podemos usar el signo menos para abreviar letras o números consecutivos, de modo que la cadena a-dha3-68 se pueda expandir a abcdha34568.

Ingrese tres parámetros p1, p2, p3 y luego ingrese una cadena que consta solo de números, letras minúsculas y signos menos (la longitud no debe exceder 100

El significado de cada parámetro es el siguiente). :

Parámetro p 1 = 1->; todas las letras completadas están en minúsculas;

Parámetro p 1 = 2->; todas las letras completadas Las buenas letras están en mayúsculas;

Parámetro p 1 = 3->; Todas las letras y números rellenos se reemplazan con asteriscos;

Parámetro p2 = k-> Escribe el mismo carácter de relleno k veces; p>

Parámetro P3 = 1->; relleno secuencial;

Parámetro P3 = 2-& gt; relleno inverso

Además, si los caracteres en ambos lados de el signo menos son números y letras, o el código ASCII en el lado derecho del signo menos no es mayor que el del lado izquierdo, permanecerá sin cambios.

Entrada de muestra 1:

1 2 1

abcs-w1234-9s-4zz

Salida de muestra 1:

abcsttuuvw 1234556677889s-4zz

Entrada de muestra 2:

2 3 2

Respuesta-respuesta-respuesta

Salida de muestra 2:

aCCCBBBd-d

Entrada de muestra 3:

3 4 2

di-jkstra2-6

Salida de muestra 3:

dijkstra2* **** *******6

Pregunta 3: Juego de acceso a la matriz del juego

Una matriz con N filas y M columnas necesita sacar N números según sea necesario, M veces. Saca exactamente todos los números. Cada vez que sacas un número, obtendrás una puntuación.

Los requisitos para sacar números a la vez: toma exactamente un número de los números restantes. número en la posición más a la derecha

Para cada número tomado, el valor del número tomado se multiplica por 2 I, donde I indica que esta es la ronda I de tomar números

. El número es un número natural que no excede 100 y 1

Entrada de muestra:

2 3

1 2 3

3 4 2

Resultado de muestra:

82

Descripción de muestra:

1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

Pregunta 4: El núcleo de la red central del árbol.

Existe un camino único entre dos puntos cualesquiera del árbol. La distancia desde un punto del árbol hasta un camino se define como la longitud mínima del camino desde ese punto hasta todos los puntos del camino. Defina la excentricidad de un camino en un árbol como la distancia máxima desde todos los demás puntos hasta ese camino. Defina el diámetro del árbol como el camino más largo a través del árbol (que puede no ser único). Dado un árbol sin raíz con n nodos, encuentre un camino con una longitud menor que s en un cierto diámetro (puede degenerar en un punto) para minimizar su excentricidad. Por favor envíe el valor de esta excentricidad mínima.

La pregunta te ha dicho el siguiente teorema: los puntos medios de todos los diámetros de un árbol deben coincidir (el punto medio puede estar en una arista). De hecho, esta conclusión es obvia, porque si los puntos medios no coinciden, puedes encontrar un camino más largo.

5 & lt= n & lt=300, & lt= s & lt=1000, el peso del borde es un entero positivo que no excede 1000.