Practice for algorithm
1.0.0
Prática para o algoritmo
Uma árvore usada para pesquisa de dicionário, a pergunta correspondente é uma árvore de dicionário no código usando matrizes para implementar a pergunta correspondente
O algoritmo KMP é um algoritmo de correspondência de padrão de string que usa uma próxima matriz para executar a correspondência de strings de alta velocidade. A seguir, o modelo 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
O método de saída da ordem do dicionário está pronto no 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 and gets the Próximo arranjo completo. De HDU 1711
Uma ideia binária
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 strings para adicionar ou subtrair, sem ser restrito pelo 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 uma sequência a [1], a [2], a [3] ...... a [n], seu trabalho é calcular a soma máxima de uma subscensão. Por exemplo, dado (6, -1,5,4, -7), a soma máxima nesta sequência é 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
## Planejamento dinâmico: o número de torres e torres é um problema típico de planejamento dinâmico. Pode ser imaginado como a partir do vértice da estrutura como o triângulo Yang Hui, para a esquerda ou direita. O valor máximo é necessário no final. Usando programação dinâmica e cálculo de baixo para cima, uma solução ideal pode ser obtida.
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 Prime Pesquisa porque o gráfico pode ser pesquisado camada por camada, ele pode ser usado como uma maneira de encontrar o caminho mais curto. Obviamente, é um gráfico com pesos iguais. Geralmente, haverá uma matriz para marcar se a acessando para evitar acesso repetido, mas algumas perguntas serão repetidas, dependendo da situação. Basicamente, existe um modelo unificado. São necessárias filas e, às vezes, a pergunta tem a necessidade de usar filas prioritárias.
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 é um método de travessia de um gráfico que é completamente diferente do método BFS. Ele vai para trás em uma rota em vez de pesquisar camada por camada. É frequentemente usado para encontrar rotas viáveis ou explorar mapas. Se você precisa adicionar marcas de mapa para ver os requisitos da pergunta. Depois que uma rota é pesquisada, muitas vezes você precisa cancelar a marca passo a passo, para que outras rotas possam andar nesse ponto no mapa novamente. Eu escrevi o terceiro labirinto da questão da estrutura de dados no DFS. O código é semelhante ao seguinte:
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
## Backpack Problem ### 01backpack 01backpack é o tipo mais básico de mochila: existem n itens e uma mochila com capacidade de V. O custo do i-ésimo item é c [i] e o valor é w [i]. Resolva quais itens colocar em uma mochila para maximizar a soma do valor. A equação do estado é: f [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
A solução básica é a estimativa reversa da capacidade da mochila: para i = 1..n para v = v..cost f [v] = max {f [v], f [vc [i]]+w [i]};
Para a pergunta, consulte o HDU1203 && HDU2602 ### Full Backpack é um tipo de mochila que pode ser colocada inúmeras vezes para cada item. Como pode ser colocado inúmeras vezes, não precisaremos mais reverter o recursivamente. Portanto, sua solução é: para i = 1..n para v = custo..v f [v] = max {f [v], f [vc [i]]+w [i]}; Só que há uma pequena diferença entre ele e a mochila 01 ### multi-backpack várias mochilas são relativamente complicadas. Como dizer é que há um limite na quantidade de itens. Quando há quantidades suficientes, ainda usamos o método de mochila completa. Quando não há quantidades suficientes, dividimos a quantidade e a simplificamos em 01 mochilas para resolvê -la. O método é: divida o i-ésimo item em vários itens, cada item tem um coeficiente e o custo e o valor do item são o custo e o valor originais multiplicados por esse coeficiente. Faça esses coeficientes 1, 2, 4, ..., 2^(k-1), n [i] -2^k+1 e k é o maior número inteiro que satisfaz n [i] -2^k+1> 0. Por exemplo, se n [i] tiver 13 anos, o item é dividido em quatro itens com coeficientes de 1, 2, 4, 6, respectivamente. A solução é: Procedimento Multippack (custo, peso, quantidade)
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)
Referência de título para mochila completa e múltiplas mochilas HDU 2159 HDU 2191 HDU 1171
