Practice for algorithm
1.0.0
Algorithmus üben
Ein Baum, der für die Wörterbuchsuche verwendet wird. Die entsprechende Frage ist der Wörterbuchbaum im Code, der Arrays verwendet, um die entsprechende Frage zu implementieren
Der KMP-Algorithmus ist ein String-Muster-Matching-Algorithmus, der ein nächstes Array verwendet, um die Hochgeschwindigkeits-Matching von Saiten durchzuführen. Das Folgende ist die KMP -Algorithmus -Vorlage:
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++;
}
}
}Von HDU 1027
Die Ausgangsmethode der Wörterbuchauftrags ist in STL hergestellt. Next_permutation (a, a + 4) kann die nächste vollständige Permutation des Arrays mit Größe 4 erhalten. Der nicht rekursive Algorithmus beginnt vom letzten Bit, findet die erste Position eines [i - 1] <a [i], Aufzeichnungen i - 1, startet von i und findet dann die letzte Nummer ein [i - 1]. Nächstes volles Arrangement. Aus HDU 1711
Eine binäre Idee
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;
}Verwenden Sie Zeichenfolgen, um hinzuzufügen oder zu subtrahieren, ohne durch die Anzahl der Bits eingeschränkt zu werden
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;
}
Von HDU 1002
Bei einer Sequenz A [1], A [2], A [3] ...... a [n] ist Ihre Aufgabe, die maximale Summe einer Subsequenz zu berechnen. Beispielsweise beträgt die maximale Summe in dieser Sequenz 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;
}
}Von HDU 1003
## Dynamische Planung: Anzahl der Türme und Türme ist ein typisches Dynamikplanungsproblem. Es kann sich als aus dem Scheitelpunkt der Struktur wie dem Yang -Hui -Dreieck entweder links oder rechts anfassen. Der Maximalwert ist am Ende erforderlich. Mit dynamischer Programmierung und Bottom-up-Berechnung kann eine optimale Lösung erhalten werden.
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;
}Von HDU 1176
## BFS BREIDNESS-FRIST-Such Da der Diagramm für die Schicht für Schicht gesucht werden kann, kann es verwendet werden, um den kürzesten Pfad zu finden. Natürlich ist es ein Diagramm mit gleichen Gewichten. Im Allgemeinen wird es ein Array geben, um zu markieren, ob er darauf zugreifen soll, um einen wiederholten Zugriff zu verhindern. Je nach Situation werden jedoch einige Fragen wiederholt. Grundsätzlich gibt es eine einheitliche Vorlage. Warteschlangen sind erforderlich, und manchmal muss die Frage vorrangige Warteschlangen verwenden.
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 " );
}Von HDU 1072
## DFS DFS ist eine Traversalmethode eines Diagramms, das sich vollständig von der BFS -Methode unterscheidet. Es geht auf einer Route zurück, anstatt Schicht für Schicht zu suchen. Es wird oft verwendet, um realisierbare Routen zu finden oder Karten zu erkunden. Unabhängig davon, ob Sie Kartenmarken hinzufügen müssen, um die Fragenanforderungen anzuzeigen. Nach der Durchsuchung einer Route müssen Sie die Marke häufig Schritt für Schritt abbrechen, damit andere Routen an diesem Punkt wieder auf der Karte laufen können. Ich habe das dritte Labyrinth der Datenstrukturfrage in DFS geschrieben. Der Code ähnelt wie folgt:
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);
}
}
}
}Von HDU 1312
## Backpack Problem ### 01BackPack 01BackPack ist der grundlegendste Rucksacktyp: Es gibt N-Artikel und einen Rucksack mit einer Kapazität von V. Die Kosten des I-ten sind c [i] und der Wert beträgt W [i]. Lösen Sie, welche Elemente in einen Rucksack gesteckt werden sollen, um die Summe des Wertes zu maximieren. Die Zustandsgleichung lautet: f [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
Die grundlegende Lösung ist die umgekehrte Schätzung der Rucksackkapazität: für i = 1..n für v = V..Cost f [v] = max {f [v], f [vc [i]]+w [i]};
Die Frage finden Sie unter HDU1203 && HDU2602 ### Full Rucksack ist eine Art Rucksack, der für jeden Artikel unzählige Male platziert werden kann. Da es unzählige Male platziert werden kann, müssen wir das rekursiv nicht mehr umkehren. Daher ist seine Lösung: für i = 1..n für v = cost..v f [v] = max {f [v], f [vc [i]]+w [i]}; Es ist nur so, dass es einen kleinen Unterschied zwischen ihm und dem 01-Rucksack ### Multi-Backpack Mehrere Rucksäcke sind relativ kompliziert. Wie man sagt, dass die Menge der Elemente eine Grenze gibt. Wenn es genügend Mengen gibt, verwenden wir immer noch die Methode des vollständigen Rucksacks. Wenn es nicht genügend Mengen gibt, teilen wir die Menge auf und vereinfachen sie in 01 Rucksäcke, um sie zu lösen. Die Methode lautet: Teilen Sie das I-te Element in mehrere Elemente, jeder Artikel verfügt über einen Koeffizienten, und die Kosten und der Wert des Artikels sind sowohl die ursprünglichen Kosten als auch der Wert multipliziert mit diesem Koeffizienten. Machen Sie diese Koeffizienten 1, 2, 4, ..., 2^(k-1), n [i] -2^k+1 und k ist die größte Ganzzahl, die N [i] -2^K+1> 0 erfüllt. Wenn N [i] beispielsweise 13 ist, ist der Artikel in vier Elemente mit Koeffizienten von 1, 2, 4, 6 unterteilt. Die Lösung ist: Verfahren Multiple Pack (Kosten, Gewicht, Menge)
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)
Titelreferenz für den vollständigen Rucksack und mehrere Backpack HDU 2159 HDU 2191 HDU 1171
