Practice for algorithm
1.0.0
Pratique pour l'algorithme
Une arbre utilisée pour la recherche de dictionnaire, la question correspondante est l'arbre du dictionnaire dans le code à l'aide de tableaux pour implémenter la question correspondante
L'algorithme KMP est un algorithme de correspondance de motif de chaîne qui utilise un tableau suivant pour effectuer une correspondance à grande vitesse des chaînes. Ce qui suit est le modèle d'algorithme 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
La méthode de sortie de l'ordre du dictionnaire est prête à l'emploi dans STL. Next_permutation (A, A + 4) peut obtenir la permutation complète suivante du tableau avec la taille 4. L'algorithme non réécursif commence à partir du dernier bit, trouve la première position d'un [i - 1] <a [i], enregistre i - 1, commence à I et trouve ensuite le dernier numéro plus grand que [i - 1], enregistre sa position, échangez-en et i-i - 1] et a [k], puis dans la position K, échangent A et fait la prochaine arrangement complet. De HDU 1711
Une idée binaire
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;
}Utilisez des chaînes pour ajouter ou soustraire, sans être limitée par le nombre 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
Étant donné une séquence A [1], a [2], a [3] ...... a [n], votre travail consiste à calculer la somme maximale d'une sous-séquence. Par exemple, étant donné (6, -1,5,4, -7), la somme max dans cette séquence est 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
## Planification dynamique: le nombre de tours et de tours est un problème de planification dynamique typique. Il peut être imaginé comme à partir du sommet de la structure comme le triangle Yang Hui, à gauche ou à droite. La valeur maximale est requise à la fin. En utilisant la programmation dynamique et le calcul ascendant, une solution optimale peut être obtenue.
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 car le graphique peut être recherché par couche par couche, il peut être utilisé comme moyen de trouver le chemin le plus court. Bien sûr, c'est un graphique avec des poids égaux. Généralement, il y aura un tableau pour marquer s'il faut y accéder pour éviter un accès répété, mais certaines questions seront répétées, selon la situation. Fondamentalement, il existe un modèle unifié. Des files d'attente sont nécessaires, et parfois la question a besoin d'utiliser des files d'attente de priorité.
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 est une méthode de traversée d'un graphique complètement différent de la méthode BFS. Il recule sur un itinéraire au lieu de rechercher la couche par couche. Il est souvent utilisé pour trouver des itinéraires réalisables ou explorer des cartes. Que vous ayez besoin d'ajouter des marques de carte pour voir les exigences de question. Une fois un itinéraire recherché, vous devez souvent annuler la marque étape par étape, afin que d'autres itinéraires puissent marcher à ce stade de la carte. J'ai écrit le troisième labyrinthe de la question de la structure des données dans DFS. Le code est similaire à ce qui suit:
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
## Problème de sac à dos ### 01backpack 01backpack est le type de sac à dos le plus élémentaire: il y a n articles et un sac à dos avec une capacité de V. Le coût du i-tème élément est C [i] et la valeur est w [i]. Résolvez les éléments à mettre dans un sac à dos pour maximiser la somme de la valeur. L'équation d'état est: f [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]] + w [i]}
La solution de base est l'estimation inverse de la capacité du sac à dos: pour i = 1..n pour v = v..cost f [v] = max {f [v], f [vc [i]] + w [i]};
Pour la question, veuillez vous référer à HDU1203 && HDU2602 ### Le sac à dos complet est un type de sac à dos qui peut être placé d'innombrables fois pour chaque élément. Parce qu'il peut être placé d'innombrables fois, nous n'aurons plus besoin d'inverser le récursivement. Par conséquent, sa solution est: pour i = 1..n pour v = coût..v f [v] = max {f [v], f [vc [i]] + w [i]}; C'est juste qu'il y a une petite différence entre celui-ci et le sac à dos 01 ### Multi-Backpack, plusieurs sacs à dos multiples sont relativement compliqués. Comment dire que c'est qu'il y a une limite sur la quantité d'articles. Lorsqu'il y a suffisamment de quantités, nous utilisons toujours la méthode de randonnée complète. Lorsqu'il n'y a pas assez de quantités, nous divisons la quantité et la simplifions en sacs à dos 01 pour le résoudre. La méthode est: divisez le i-tème élément en plusieurs éléments, chaque élément a un coefficient, et le coût et la valeur de l'élément sont à la fois le coût et la valeur d'origine multipliés par ce coefficient. Faire ces coefficients 1, 2, 4, ..., 2 ^ (k-1), n [i] -2 ^ k + 1, et k est le plus grand entier qui satisfait n [i] -2 ^ k + 1> 0. Par exemple, si n [i] est 13, l'élément est divisé en quatre éléments avec des coefficients de 1, 2, 4, 6, respectivement. La solution est: Procédure multiple pack (coût, poids, montant)
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)
Référence du titre pour un sac à dos complet et un sac à dos multiple HDU 2159 HDU 2191 HDU 1171
