Practice for algorithm
1.0.0
Práctica para algoritmo
Un árbol utilizado para la búsqueda del diccionario, la pregunta correspondiente es el árbol de diccionario en el código que usa matrices para implementar la pregunta correspondiente
El algoritmo KMP es un algoritmo de coincidencia de patrón de cadena que utiliza una siguiente matriz para realizar una coincidencia de alta velocidad de cadenas. La siguiente es la plantilla de algoritmo KMP:
void setNext (){
NEXT[ 0 ] = - 1 ;
int j = 0 , k = - 1 ;
while (j < par. length ()) {
if (k == - 1 || par[k] == par[j]) {
j++;
k++;
NEXT[j] = k;
}
else
k = NEXT[k];
}
}
void solve (){
int p = 0 , q = 0 ;
while (p < ori. length ()) {
if (q == - 1 || par[q] == ori[p]) {
q++;
p++;
}
else
q = NEXT[q];
if (q == par. length ()) {
ans++;
}
}
}De HDU 1027
El método de salida del orden del diccionario está listo en STL. Next_permutation(a, a + 4) can obtain the next full permutation of the array with size 4. The non-recursive algorithm starts from the last bit, finds the first position of a[i - 1] < a[i], records i - 1, starts from i and then finds the last number greater than a[i - 1], records its position k, exchanges a[i - 1] and a[k], and then inverts the position i y obtiene el siguiente arreglo completo. De HDU 1711
Una idea binaria
int quickMPow ( int a, int b){
if (b == 0 ) {
return 1 ;
}
int reslut = 1 ;
while (b) {
if (b & 1 ) {
reslut *= a;
}
a *= a;
b >>= 1 ;
}
return reslut;
}Use cadenas para sumar o restar, sin estar restringido por el número de bits
void solve (){
int lenNum1 = strlen (num1), lenNum2 = strlen (num2), min = 0 , c = 0 , count = 0 ;
if (lenNum1 >= lenNum2) {
min = lenNum2;
} else {
min = lenNum1;
}
while (min) {
int temp;
temp = num1[lenNum1 - 1 ] + num2[lenNum2 - 1 ] - 96 ;
min--;
lenNum1--;
lenNum2--;
sum[count] = (temp % 10 + c) % 10 + 48 ;
count++;
if (temp % 10 + c >= 10 ){
c = 1 ;
}
else {
c = 0 ;
}
if (temp >= 10 ) {
c++;
}
}
while (lenNum1) {
sum[count] = (num1[lenNum1 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num1[lenNum1 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum1--;
}
while (lenNum2) {
sum[count] = (num2[lenNum2 - 1 ] - 48 + c) % 10 + 48 ;
count++;
if (num2[lenNum2 - 1 ] - 48 + c >= 10 ){
c = 1 ;
} else {
c = 0 ;
}
lenNum2--;
}
if (c) {
sum[count] = ' 1 ' ;
count++;
}
count--;
for ( int i = 0 ; i <= count; i++) {
if (sum[i] != ' 0 ' )
break ;
if (i == count){
cout << ' 0 ' << endl;
return ;
}
}
while (count >= 0 ) {
cout << sum[count];
count--;
}
cout << endl;
}
De HDU 1002
Dada una secuencia a [1], a [2], a [3] ...... a [n], su trabajo es calcular la suma máxima de una subsecución. Por ejemplo, dado (6, -1,5,4, -7), la suma máxima en esta secuencia es 6 + (-1) + 5 + 4 = 14.
for ( int i = 0 ; i < T; i++) {
int count, start = 1 , end = 1 , max = - 1 << 31 , dp = 0 , temp = 1 ;
cin >> count;
for ( int k = 0 ; k < count; k++) {
int num;
cin >> num;
dp += num;
if (dp > max) {
max = dp;
start = temp;
end = k + 1 ;
}
if (dp < 0 ){
dp = 0 ;
temp = k + 2 ;
}
}
cout << " Case " << i + 1 << " : " << endl;
cout << max << " " << start << " " << end << endl;
if (i != T - 1 ) {
cout << endl;
}
}De HDU 1003
## Planificación dinámica: el número de torres y torres es un problema típico de planificación dinámica. Se puede imaginar que comienza desde el vértice de la estructura como el triángulo Yang Hui, ya sea a la izquierda o a la derecha. El valor máximo se requiere al final. Usando programación dinámica y cálculo ascendente, se puede obtener una solución óptima.
int H1176_Solve (){
for ( int i = maxTime - 1 ; i >= 0 ; i--) {
for ( int k = 0 ; k < 11 ; k++) {
int maxValue = arr[k][i + 1 ];
if (k - 1 >= 0 ) {
if (arr[k - 1 ][i + 1 ] > maxValue) {
maxValue = arr[k - 1 ][i + 1 ];
}
}
if (k + 1 <= 10 ){
if (arr[k + 1 ][i + 1 ] > maxValue) {
maxValue = arr[k + 1 ][i + 1 ];
}
}
arr[k][i] = arr[k][i] + maxValue;
}
}
int max = arr[ 4 ][ 1 ];
for ( int i = 4 ; i < 7 ; i++) {
if (arr[i][ 1 ] > max){
max = arr[i][ 1 ];
}
}
return max;
}De HDU 1176
## BFS Broadness-First Search Debido a que el gráfico se puede buscar en capa por capa, se puede usar como una forma de encontrar la ruta más corta. Por supuesto, es un gráfico con igualdad de pesas. En general, habrá una matriz para marcar si acceder a él para evitar el acceso repetido, pero algunas preguntas se repetirán, dependiendo de la situación. Básicamente hay una plantilla unificada. Se requieren colas y, a veces, la pregunta tiene la necesidad de usar colas prioritarias.
void solve (){
queue<Node> s;
memset (flag, 0 , sizeof (flag));
now. x = inx;
now. y = iny;
now. time = 6 ;
now. output = 0 ;
flag[inx][iny] = 6 ;
s. push (now);
while (!s. empty ()) {
now = s. front ();
s. pop ();
for ( int i = 0 ; i < 4 ; i++) {
nex = now;
nex. x = now. x + fx[i];
nex. y = now. y + fy[i];
if (nex. x >= 0 && nex. x < N && nex. y >= 0 && nex. y < M && flag[nex. x ][nex. y ] < now. time - 1 ){
if (mp[nex. x ][nex. y ] == 0 ) {
}
if (mp[nex. x ][nex. y ] == 3 ){
}
if (mp[nex. x ][nex. y ] == 1 ) {
}
if (mp[nex. x ][nex. y ] == 4 ) {
}
}
}
}
printf ( " -1 n " );
}De HDU 1072
## DFS DFS es un método transversal de un gráfico que es completamente diferente del método BFS. Va hacia atrás en una ruta en lugar de buscar capa por capa. A menudo se usa para encontrar rutas factibles o explorar mapas. Si necesita agregar marcas de mapas para ver los requisitos de la pregunta. Después de buscar una ruta, a menudo debe cancelar la marca paso a paso, para que otras rutas puedan caminar en ese punto nuevamente en el mapa. Escribí el tercer laberinto de la pregunta de la estructura de datos en DFS. El código es similar al siguiente:
int fx[ 4 ] = { 0 , 0 , 1 , - 1 };
int fy[ 4 ] = { 1 , - 1 , 0 , 0 };
void solve ( int x, int y){
if ((mp[x][y] == ' . ' || mp[x][y] == ' @ ' ) && vis[x][y] == 0 ){
num++;
vis[x][y] = 1 ;
for ( int i = 0 ; i < 4 ; i++) {
int nexX = x, nexY = y;
nexX += fx[i];
nexY += fy[i];
if (nexX >= 0 && nexX < N && nexY >= 0 && nexY < M) {
solve (nexX, nexY);
}
}
}
}De HDU 1312
## Problema de mochila ### 01BackPack 01BackPack es el tipo más básico de mochila: hay n elementos y una mochila con una capacidad de V. El costo del elemento i-th es c [i] y el valor es w [i]. Resuelva qué elementos poner en una mochila para maximizar la suma del valor. La ecuación de estado es: f [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
La solución básica es la estimación inversa de la capacidad de la mochila: para i = 1..n para v = v..cost f [v] = max {f [v], f [vc [i]]+w [i]};
Para la pregunta, consulte HDU1203 && HDU2602 ### La mochila completa es un tipo de mochila que se puede colocar innumerables veces para cada elemento. Debido a que se puede colocar innumerables veces, ya no necesitaremos revertir el recursivamente. Por lo tanto, su solución es: para i = 1..n para v = costo..v f [v] = max {f [v], f [vc [i]]+w [i]}; Es solo que hay una pequeña diferencia entre él y la mochila 01 ### múltiples mochilas múltiples son relativamente complicadas. Cómo decir que es que hay un límite en la cantidad de artículos. Cuando hay suficientes cantidades, todavía usamos el método de mochilero completo. Cuando no hay suficientes cantidades, dividimos la cantidad y la simplificamos en 01 mochilas para resolverla. El método es: divide el elemento I-Th en varios elementos, cada elemento tiene un coeficiente, y el costo y el valor del artículo son tanto el costo y el valor originales multiplicados por este coeficiente. Haga estos coeficientes 1, 2, 4, ..., 2^(k-1), n [i] -2^k+1, y k es el entero más grande que satisface N [i] -2^k+1> 0. Por ejemplo, si N [i] es 13, el elemento se divide en cuatro elementos con coeficientes de 1, 2, 4, 6, respectivamente. La solución es: procedimiento múltiplo (costo, peso, cantidad)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
Referencia de título para la mochila completa y múltiples mochila HDU 2159 HDU 2191 HDU 1171
