Wenn ich Abfrage von Index 0 zu einem Index T hinzufügen möchten. Und ich habe den Binärwert von T. So für zB habe ich 0111010, so wird es 01110 nach dem Entfernen am meisten Bit. Nimm 0 als links und 1 als rechts. Ich füge die Elemente hinzu, wenn ich nach rechts gehe, und füge schließlich das Element am Index T hinzu. Bedeutet das, dass ich auf das BIT [] Array zugreife, wenn ich auf 1 stoße oder gibt es einen anderen Weg?Binary Tree Iteration
Ich weiß, woher diese Frage kommt. Es ist von Codechef langen Oktober. Bitte unterlassen Sie selbst Fragen zu Live-Wettbewerben.
Nun, ich weiß, dass Sie verzweifelt nach der richtigen Logik suchen werden. Ich habe mich für dieses Problem sehr angestrengt, nach vielen Versuchen habe ich eine AC bekommen (was für ein Gefühl!). Denken Sie nicht über Fenwick Tree nach, schreiben Sie stattdessen eine Simulation für die gegebene Berechnung.
Fdown(i) = (i & (i + 1))
Tun Sie es in einer Schleife, wie
cout<<"\n\nEnter L : ";
cin>>l;
while(l > -1)
{
cout<<bitset<32>(l)<<"\n";
l = (l & (l+1))-1;
}
L in dezimal eingeben.
Sie werden sehen, was Sie finden müssen. (Betrachten Sie nichts anderes über BIT).
Ich habe das versucht, aber das Problem war der Dezimalwert ist zu groß, wenn L sehr lang ist. Ich habe gerade an meinem System versucht. Wie auch immer, was ist das Problem beim Zählen von 1en? –
@sam Der erste Testfall ist 51491, der für lange Int nicht zu groß ist. Alle anderen Fälle können getestet werden, indem L so lange int lang genommen wird. Zum Konvertieren von Binär in Dezimal können Sie dies verwenden: http://www.binaryhexconverter.com/binary-to-decimal-converter. Das Zählen zählt nicht, da man nicht alle zählen muss. Wenn Sie Ihr Programm abgeschlossen haben, versuchen Sie Zahlen wie 128, 256, 257, 255, etc. Hoffentlich fangen Sie an zu sehen, was Sie finden müssen. –
Vielen Dank für die Hilfe. Ich weiß, was du zu erzählen versuchst. Ich habe es vorher versucht, aber das Problem bestand in der Umwandlung von Bitstring in Dezimal. Für kleine Strings kann es von STL gemacht werden. Aber das Problem liegt in großen Saiten. Ich denke nicht, dass sie auch lange gespeichert werden. Betrachten Sie zum Beispiel eine Zeichenfolge von etwa 100 Bit Länge. Das Dezimaläquivalent überschreitet 18 Ziffern, das ist sogar mehr als das, was unsigned Long Long enthalten kann. Gibt es einen Weg dahin? –
Ich wollte nur wissen, wie man diesen Ansatz ändern kann, wenn es nicht richtig ist. Ich habe mich lange daran gehalten. Es frustriert mich. Außerdem geht es nur ums Lernen. Ich wollte nur wissen, ob wir Array nur auf 1 zugreifen oder nicht? –