Practice for algorithm
1.0.0
Berlatih untuk algoritma
Pohon yang digunakan untuk pencarian kamus, pertanyaan yang sesuai adalah pohon kamus dalam kode menggunakan array untuk mengimplementasikan pertanyaan yang sesuai
Algoritma KMP adalah algoritma pencocokan pola string yang menggunakan array berikutnya untuk melakukan pencocokan string berkecepatan tinggi. Berikut ini adalah template algoritma 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++;
}
}
}Dari HDU 1027
Metode Output Urutan Kamus sudah jadi di STL. Next_permutation (a, a + 4) dapat memperoleh permutasi penuh berikutnya dari array dengan ukuran 4. Algoritma non -rekursif dimulai dari bit terakhir, menemukan posisi pertama dari [i - 1] <a [i], catatan i - 1, mulai dari saya dan kemudian menemukan nomor terakhir dari [i - 1], mencatat posisinya, menukar penukarannya. pengaturan penuh. Dari HDU 1711
Ide biner
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;
}Gunakan string untuk menambah atau mengurangi, tanpa dibatasi oleh jumlah bit
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;
}
Dari HDU 1002
Diberi urutan A [1], A [2], A [3] ...... A [n], tugas Anda adalah menghitung jumlah maksimum dari suatu sub-urutan. Misalnya, diberikan (6, -1,5,4, -7), jumlah maks dalam urutan ini adalah 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;
}
}Dari HDU 1003
## Perencanaan Dinamis: Jumlah menara dan menara adalah masalah perencanaan dinamis yang khas. Ini dapat dibayangkan sebagai mulai dari simpul struktur seperti segitiga Yang Hui, baik kiri atau kanan. Nilai maksimum diperlukan di akhir. Menggunakan pemrograman dinamis dan perhitungan bottom-up, solusi optimal dapat diperoleh.
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;
}Dari HDU 1176
## BFS Pencarian Lebar-pertama karena grafik dapat dicari lapisan demi lapis, itu dapat digunakan sebagai cara untuk menemukan jalur terpendek. Tentu saja, ini adalah grafik dengan bobot yang sama. Secara umum, akan ada array untuk menandai apakah akan mengaksesnya untuk mencegah akses berulang, tetapi beberapa pertanyaan akan diulang, tergantung pada situasinya. Pada dasarnya ada templat terpadu. Diperlukan antrian, dan kadang -kadang pertanyaan memiliki kebutuhan untuk menggunakan antrian prioritas.
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 " );
}Dari HDU 1072
## DFS DFS adalah metode traversal grafik yang sama sekali berbeda dari metode BFS. Ini mundur pada rute alih -alih mencari layer demi layer. Ini sering digunakan untuk menemukan rute yang layak atau menjelajahi peta. Apakah Anda perlu menambahkan tanda peta untuk melihat persyaratan pertanyaan. Setelah rute dicari, Anda sering perlu membatalkan tanda langkah demi langkah, sehingga rute lain dapat berjalan pada saat itu di peta lagi. Saya menulis labirin ketiga pertanyaan struktur data di DFS. Kode ini mirip dengan yang berikut:
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);
}
}
}
}Dari HDU 1312
## Masalah Ransel ### 01BackPack 01Backpack adalah jenis ransel paling dasar: Ada N item dan ransel dengan kapasitas V. Biaya item i-th adalah C [i] dan nilainya w [i]. Selesaikan item mana yang akan dimasukkan ke dalam ransel untuk memaksimalkan jumlah nilai. Persamaan keadaan adalah: f [i] [v] = max {f [i-1] [v], f [i-1] [vc [i]]+w [i]}
Solusi dasar adalah estimasi terbalik dari kapasitas ransel: untuk i = 1..n untuk v = v..kosta f [v] = max {f [v], f [vc [i]]+w [i]};
Untuk pertanyaannya, silakan merujuk ke HDU1203 && HDU2602 ### Full Backpack adalah jenis ransel yang dapat ditempatkan berkali -kali untuk setiap item. Karena dapat ditempatkan berkali -kali, kita tidak perlu lagi membalikkan rekursif. Oleh karena itu, solusinya adalah: untuk i = 1..n untuk v = biaya..v f [v] = max {f [v], f [vc [i]]+w [i]}; Hanya saja ada sedikit perbedaan antara itu dan ransel 01 ransel ### multi-backpack beberapa ransel relatif rumit. Bagaimana mengatakan itu adalah bahwa ada batasan jumlah item. Ketika ada jumlah yang cukup, kami masih menggunakan metode backpacking lengkap. Ketika tidak ada jumlah yang cukup, kami membagi jumlah dan menyederhanakannya menjadi 01 ransel untuk menyelesaikannya. Metode ini adalah: Membagi item i-th menjadi beberapa item, setiap item memiliki koefisien, dan biaya dan nilai item tersebut adalah biaya dan nilai asli yang dikalikan dengan koefisien ini. Buat koefisien ini 1, 2, 4, ..., 2^(k-1), n [i] -2^k+1, dan k adalah bilangan bulat terbesar yang memuaskan n [i] -2^k+1> 0. Misalnya, jika n [i] adalah 13, item dibagi menjadi empat item dengan koefisien masing -masing 1, 2, 4, 6. Solusinya adalah: Prosedur MultiplePack (Biaya, Berat, Jumlah)
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)
Referensi judul untuk ransel lengkap dan beberapa ransel HDU 2159 HDU 2191 HDU 1171
