Informe de resolución de problemas de la semifinal del grupo popular noip2009

Salida del polinomio

Declaración del problema:

Dado el grado y el coeficiente de cada término de un polinomio de una variable, genere el polinomio de acuerdo con los requisitos de formato especificados. .

Análisis:

Preguntas sobre el agua en el grupo de popularización. Deberías estar familiarizado con los polinomios. Solo presta atención a algunos puntos al generar:

1. Si el término de mayor orden es positivo, no hay signo más al principio.

2. Si el coeficiente es 0, no se generará.

3. El término lineal genera x, no x^1.

4. Cuando el coeficiente del término no constante es 1 o -1, los signos positivos y negativos se generan directamente, pero el término constante necesita generar el número.

A excepción del tercer ítem, los errores se pueden comprobar en la muestra. Sin embargo, si no se tiene en cuenta el tercer punto, sólo obtendrás 50 puntos.

Programa:

var i,k,n:longint;

comenzar

assign(entrada,'poly.in') ;restablecer(entrada);

asignar(salida,'poly.out');reescribir(salida);

readln(n);

para i :=n hasta 0 hacer

comenzar

leer(k);

si k=0 entonces continuar;

si (k >0) y (i<>n) entonces escribe('+');

si i=0 entonces escribe(k)

si no (abs(k)<> 1) luego escribe(k) si no, si k=-1 entonces escribe('-');

si i<>0 entonces

si i=1 entonces escribe('x ')

else write('x^',i);

end;

writeln;

close(input);

cerrar(salida);

fin.

2009-11-28 12:03 Responder

Gato Suicida

0 fans

3er piso

Demarcación de líneas de puntuación

Paráfrasis de la pregunta:

Indique el número de admisiones y todos los entrevistados Puntuación, número de prueba. Encuentre la línea de puntuación y el número real de estudiantes admitidos, y genere los números de prueba y las puntuaciones de los candidatos admitidos en orden descendente. Si las puntuaciones son las mismas, los números de prueba y las puntuaciones de los estudiantes admitidos se generarán en orden ascendente. .

Análisis:

Doble clasificación por palabras clave. Dado que n es alrededor de 5000, para garantizar que no haya TLE, se debe utilizar la clasificación nlogn, como la clasificación rápida. Luego apunte el puntero a la última persona admitida en el programa y deslícese hasta la última persona con la misma puntuación. El punto antes del puntero es el entrevistador admitido real.

Programa:

escribe arr=array;temp1:=a;

repetir

mientras (a>temp1) o (( a=temp1) y (a

mientras que (atemp2)) hacen dec(j);

si i<=j entonces

comenzar

swap(a[i],a[j]);

inc( i);dec(j);

fin;

hasta i>j;

si i p>

si j>l entonces qsort(l,j);

fin;

comenzar

aleatorizar;

asignar(entrada,'score.in');reset(entrada);

assign(salida,'score.out');reescribir(salida);

readln( n, m);

m:=trunc(m*1.5);

para i:=1 an hacer readln(a,a);

a :=0;

qsort(1,n);

i:=m;

mientras que a=a hace inc(i);

writeln(a,' ',i);

para j:=1 que hago

writeln(a,' ',a);

cerrar(entrada);cerrar(salida);

fin.

2009-11-28 12:04 Responder

Gato Suicida

0 ventiladores

4to piso

División celular

Paráfrasis de la pregunta:

Dado m1, m2 y varios si , encuentre el valor mínimo de a en si^a mod m1^m2=0. Si no hay solución, genera -1.

Análisis:

Cuestiones matemáticas. Dado que m1 <= 30000 y m2 <= 10000, no se puede calcular directamente en absoluto, por lo que la respuesta debe obtenerse mediante análisis matemático. Si un número puede dividir a otro número, entonces este número debe tener todos los elementos del otro número después de la factorización, y el número de cada elemento debe ser mayor o igual que el número de los mismos elementos del otro número. Por lo tanto, primero podemos factorizar m1 y multiplicar el número de elementos correspondientes por m2. Luego lee cada número y determina si el número tiene todos los elementos en m1 después de la factorización. Si lo hay, calcula el número máximo de divisiones de la celda, que corresponde al número de elementos m1/el número de elementos en si y luego redondea hacia arriba. Simplemente actualice la respuesta al final.

Tenga en cuenta que 1 es especial en factorización, por lo que debe juzgarse por separado.

Programa:

escriba arr=array:=i;

a:=0;

mientras k mod i=0 haga

comienzo

inc(a);

k:=k div i;

fin;

end;

hasta k=1;

end;

procedimiento principal;

var i,z,max:longint;

comenzar

max:=-1;

read(k);

para i:=1 hasta hacer el total

comenzar

si k mod a<>0 entonces salir;

z:=0;

mientras k mod a=0 hacerlo

comenzar

inc(z);

k:=k div a;

finalizar;

si ( a+z-1) div z>max entonces max:=(a+z-1) div z;

end;

si max

fin;

comenzar

asignar(entrada,'cell.in');reset(entrada);

asignar(salida ,'cell.out');reescribir(salida);

ans:=maxlongint;

readln(n);

readln(m1,m2) ;

si m1=1 entonces comience writeln(0);close(input);close(output);halt;end;

factorización(m1,a,total);

for i:=1 to total do a:=a*m2;

for i:=1 to n do

main;

si ans=maxlongint entonces writeln(-1) si no writeln(ans);

cerrar(entrada);

cerrar(salida);

fin .

2009-11-28 12:05 Responder

Suicide Cat

0 fans

5to Piso

Juego de carreteras

Enunciado del problema:

Hay una carretera circular con n puntos en la carretera. El i-ésimo punto y el i+1-ésimo punto están conectados por un borde. (el punto n-ésimo El punto está conectado al primer punto por un borde). Cada punto puede producir un robot a un costo diferente, y el robot no puede caminar más de p pasos en el sentido de las agujas del reloj (cada paso consume una unidad de tiempo) y recoger las monedas de oro en el camino en este momento. Como máximo, sólo puede haber un robot en la carretera. La cantidad de monedas de oro en cada camino es diferente en diferentes momentos. Encuentra la cantidad máxima de monedas de oro que se pueden obtener al final. (es decir, la cantidad de monedas de oro recogidas menos la cantidad de monedas de oro necesarias para producir el robot).

Análisis:

La descripción de la pregunta es extremadamente repugnante. Después de ordenar sus pensamientos, debería poder darse cuenta de que esta pregunta es programación dinámica. Dado que myn llegan a 1000, solo podemos diseñar una regla dinámica con una complejidad temporal de O (mn). El modelo dinámico de este tipo de problema es más fácil de pensar, a saber:

donde f[i,j] es el número máximo de monedas de oro obtenidas en el punto j en el momento i. Coin[i,j] es el número de monedas de oro de Ruth en los momentos i y j.

El costo [k] representa la cantidad de monedas de oro gastadas para comprar el robot en el punto k. Entre ellos 1<=k<=n. paso [i, j] representa el número de pasos que ha dado el robot cuando estaba en el estado de f [i, j]. pasado [j] es el punto antes de j. Es decir, pasado[i]=i-1(2<=i<=n) pasado[1]=n.

Tenga en cuenta que esta regla móvil es tridimensional, pero debido a que el valor óptimo de la etapa anterior no cambia, solo necesitamos guardar el valor más grande después de calcular el valor óptimo de esta etapa como la siguiente. El valor de la etapa anterior en una etapa es suficiente.

Programa:

var i,j,k,n,m,p,pastmax,nowmax:longint;

coin,f,step:array[ 0..1000,0..1000] de entero largo;

costo,pasado:matriz[1..1000] de entero largo;

comenzar

asignar (entrada,'juego.in');reset(entrada);

asignar(salida,'juego.out');reescribir(salida);

filldword(paso,tamañode (paso) shr 2,maxlongint);

readln(n,m,p);

for i:=2 to n do

pasado[i ]:=i-1;

pasado[1]:=n;

para i:=1 a n hacer

para j:=1 a m do

read(coin[j,i]);

for i:=1 to n do read(cost[i]);

pastmax :=0;

para i:=1 a m hacer

comenzar

nowmax:=-maxlongint;

para j: =1 a n hacer

comenzar

si paso[i-1,pasado[j]]

comenzar

si pastmax-cost[past[j]]>f[i-1,past[j]]

entonces comience el paso[i,j]:=1;f[i,j]:=pastmax -coste[pasado[j]]+moneda[i,pasado[j]];fin

si no comienza el paso[i,j]:=paso[i-1,pasado[j]]+1 ;f[i,j]:=f[i-1,pasado[j]]+moneda[i,pasado[j]];fin;

fin

más comenzar paso[i,j]:=1;f[i,j]:=pastmax-cost[pasado[j]]+moneda[i,pasado[j]];fin;

si f[ i,j]>nowmax entonces nowmax:=f[i,j];

fin;

pastmax:=nowmax;

fin;

writeln(nowmax);

cerrar(entrada);

cerrar(salida);

fin.