Beranda>Terkait pemrograman>Kode sumber lainnya
Unduh

Pemrograman dan latihan kompetitif

Ini adalah solusi C ++ saya dari beberapa masalah pemrograman kompetitif dan berbagai latihan. Masalah serupa diselesaikan dengan menggunakan algoritma dan struktur data yang berbeda - kadang -kadang menggunakan yang disediakan oleh perpustakaan standar, kadang -kadang menggunakan yang saya sendiri.

Sebagian besar solusi berada di C+11 karena batasan-hak-hakim online ex-UVA. Beberapa dari mereka setelah penyerahan yang berhasil dimodifikasi untuk menggunakan fitur C ++ 14/17.

Ex-UVA OJ Masalah

Sumber Masalah

PENGENAL Judul Kategori
001 08 Jumlah maksimum Pencarian Linier, Subarray Jumlah Maksimum, Algoritma Kadane
001 09 Scud Busters Hull cembung
001 12 Jumling Pohon Pohon biner
001 20 Tumpukan flapjacks Tumpukan, penyortiran pancake
001 22 Pohon di level Pohon biner, traversal tingkat tingkat, pencarian pertama yang luas
001 40 Bandwidth Permutasi, mundur
001 47 Dolar Pemrograman dinamis, perubahan koin
001 64 Komputer string Pemrograman dinamis, edit jarak
002 00 Urutan langka Penyortiran topologi, pencarian kedalaman pertama
002 16 Mengantre Pemrograman Dinamis, Hamiltonian Path, Bit Masker
002 18 Pemberantasan ngengat Hull cembung
002 22 Perjalanan Anggaran
002 40 Variabel Radix Huffman Encode Pohon Huffman, pencarian kedalaman pertama
002 59 Alokasi perangkat lunak
002 64 Mengandalkan Cantor
002 70 Berbaris
002 94 Pembagi
003 34 Mengidentifikasi peristiwa bersamaan
003 48 Optimal Array Mult. urutan Pemrograman dinamis, perkalian rantai matriks
003 50 Angka acak semu
003 53 Palindrom sial Hash rolling polinomial, pemrosesan string
003 57 Menghitung jalan
003 61 Polisi dan perampok
003 72 Notasi apa pun Pohon Biner, Konversi Traversal Pra-/Pasca-Urutan
003 74 Mod besar Eksponasi Biner, Eksponasi Modular
004 29 Transformasi kata
004 37 Menara Babel
004 39 Ksatria Bergerak Pencarian pertama yang luas
004 54 Anagram
004 55 String berkala Algoritma Knuth -Morris -Pratt
004 59 Konektivitas grafik Komponen Disjoint-Set/Union-Find, Grafik Terhubung
004 69 Lahan Basah Florida
004 81 Apa yang naik Peningkatan paling lama, pencarian biner
004 82 Array permutasi
005 01 Kotak hitam Pohon AVL, iterator pohon biner
005 07 Jill mengendarai lagi Pencarian Linier, Subarray Jumlah Maksimum, Algoritma Kadane
005 16 Tanah utama
005 26 Jarak string Pemrograman dinamis, edit jarak
005 36 Pemulihan pohon Pohon Biner, Konversi Traversal Pra-/Pasca-Urutan
005 40 Antrian Tim
005 43 Dugaan Goldbach Bilangan prima
005 48 Pohon
005 51 Sarang sekelompok tanda kurung
005 58 Lubang cacing
005 62 Membagi koin
005 68 Hanya faktanya Hubungan faktorial, kekambuhan
005 74 Jumlahkan
005 82 Jaring saraf kabel secara acak Pencarian kedalaman-pertama, grafik komponen biconnected
005 83 Faktor utama
006 12 Penyortiran DNA Gabungan, penghitungan inversi
006 23 500! Faktorial, bilangan bulat besar
006 30 Anagram
006 39 Jangan diputar
006 74 Perubahan Koin
006 79 Menjatuhkan bola
006 84 Penentu integral Eliminasi Gaussian, algoritma Euclidean
006 86 Dugaan Goldbach II Bilangan prima
007 01 Dilema Arkeolog Logaritma
007 14 Menyalin buku Partisi linier, pencarian biner implisit
007 19 Manik -manik kaca Rotasi minimal leksikografis, algoritma Duvan
007 27 Persamaan Ekspresi Parsing, Algoritma Halaman Mengocok
007 29 Masalah jarak hamming Mundur
007 50 Delapan masalah catur ratu Mundur
007 87 Produk sub-urutan maksimum Subarray produk maksimum, bilangan bulat besar
007 93 Koneksi Jaringan
007 96 Tautan kritis Pencarian kedalaman-pertama, jembatan grafik
008 20 Bandwidth Internet
008 33 Air jatuh
008 68 Labirin numerik Mundur
008 72 Pemesanan
009 08 Menghubungkan kembali situs komputer
009 29 Nomor labirin
009 42 Angka siklik Bilangan rasional, fraksi desimal, tabel hash
009 90 Menyelam untuk emas
009 91 Salam yang aman Kombinatorik, relasi kekambuhan, angka Catalan
011 21 Setelahnya Jendela geser
011 75 Pilihan wanita Masalah pencocokan yang stabil, algoritma Gale-Shapley
012 10 Jumlah bilangan prima berturut -turut Bilangan prima
012 52 Dua puluh pertanyaan
012 60 Penjualan
012 93 Derivasi simbolik Ekspresi parsing, shunting yard algorithm, eval simbolik.
013 72 Log Jumping
016 50 String angka Kombinatorik, hubungan kekambuhan
100 03 Memotong tongkat
100 04 Bicoloring
100 18 Mundur dan tambahkan Integers, 196-algoritma
100 61 Berapa banyak nol dan digit? Faktorial, bilangan prima, faktorisasi, logaritma
100 79 Pemotongan pizza Kombinatorik, bilangan poligonal pusat
101 07 Apa mediannya Antrian prioritas, algoritma online
101 71 Meeting Prof. Miguel
101 93 Yang Anda butuhkan hanyalah cinta Pembagi Umum Terbesar
102 20 Saya suka angka besar! Faktorial, bilangan bulat besar
102 23 Berapa banyak node Kombinatorik, relasi kekambuhan, angka Catalan
102 29 Fibonacci modular Jumlah Fibonacci, Eksponasi Modular
102 45 Masalah pasangan terdekat Sepasang poin terdekat 2D
102 68 498-bis Aturan Horner
102 82 Babelfish Tabel hash
102 98 String daya
103 05 Memesan tugas
103 11 Goldbach dan Euler Bilangan prima
103 19 Manhattan
103 27 Sortir flip Pohon AVL
103 41 Menyelesaikannya Numerics, Metode Newton
103 64 Persegi Backtracking, topeng bit
103 82 Rumput yang menyiram Serakah, penutup interval
104 28 Akarnya Temuan root, metode pembagian
104 54 Treekspresi Ekspresi parsing, algoritma halaman shunting, bilangan Catalan
104 96 Mengumpulkan punggung
105 33 Digit Primes
105 67 Membantu mengisi Bates
105 70 Bertemu dengan alien Permutasi, penghitungan pertukaran, penghitungan siklus
105 76 Bug Akuntansi Y2K
105 86 Sisa -sisa polinomial
106 00 Kontes dan pemadaman ACM
106 04 Reaksi kimia
106 51 Pebble Solitaire
106 55 Kontemplasi! Aljabar Hubungan kekambuhan, eksponensial modular
106 64 Bagasi
106 84 Jackpot
106 99 Menghitung faktor Bilangan prima, dekomposisi utama
107 23 Gen cyborg
107 38 Riemann vs Mertens Bilangan prima, fungsi möbius, fungsi mertens
108 01 Angkat hopping
108 10 Ultra Quicksort Gabungan/penyisipan, penghitungan inversi
108 55 Kotak berputar Rotasi Matriks, Transposisi Matriks
108 70 Rekurensi
109 20 Keran spiral Ekspresi analitik
109 31 Keseimbangan
109 34 Menjatuhkan balon air
109 35 Membuang kartu Antrian, daftar yang terhubung tunggal
109 38 Sirkus kutu
109 54 Tambahkan semua Tumpukan
109 57 SU Doku Checker Backtracking, Bit Mask
109 94 Penambahan sederhana Ekspresi analitik
110 57 Jumlah yang tepat
110 60 Minuman
110 77 Temukan permutasi Kombinatorik, relasi kekambuhan, angka stirling
111 37 Cubrency yang cerdik
111 51 Palindrom terpanjang Pemrograman dinamis, pemrosesan string
111 71 SMS Pemrograman dinamis, pemrosesan string, trie
111 95 Masalah N -rqueen lainnya Backtracking, Bit Mask
112 27 Peluru perak
112 35 Nilai yang sering
112 36 Toko kelontong
112 57 Rencana Pemasaran Baru Poligon, jari -jari lingkaran tertulis, antrian prioritas
112 58 Partisi string Pemrograman Dinamis
112 60 Jumlah akar yang aneh Ekspresi analitik, imp. Pencarian biner, aritmatika modular
112 71 Kisi resistor Hubungan kekambuhan, ekspansi asimptotik
112 83 Bermain boggle Mundur
112 97 Sensus Dekomposisi 2D SQRT
113 62 Daftar telepon Trie, pencocokan awalan
114 13 Isi wadah
114 20 Peti laci Kombinatorik, hubungan kekambuhan
114 56 Melatih
114 61 Nomor persegi Pencarian biner implisit
114 62 Jenis usia Hitung Sort
114 63 Komando
114 75 Meluas ke palindrome
115 17 Perubahan yang tepat
115 36 Sub-array terkecil Jendela geser
115 72 Kepingan salju yang unik Pencarian linier, tabel hash
115 84 Partisi oleh palindrom
116 21 Faktor kecil Logaritma
116 34 Menghasilkan angka acak
116 36 Halo, dunia! Ekspresi analitik, logaritma
116 58 Koalisi terbaik
116 86 Mengambil tongkat
116 91 Tes alergi
117 03 Sqrt, log, dosa Hubungan kekambuhan
117 14 Penyortiran buta Statistik pesanan (terbesar ke -2)
117 33 Bandara
119 02 Dominator
119 91 Masalah mudah dari Rujia Liu? Sorting, pencarian biner
119 97 K Jumlah terkecil
120 86 Potensiometer Pohon Fenwick
121 05 Lebih besar lebih baik (1)
121 05 Lebih besar lebih baik (2)
121 92 Anggur Pencarian biner
122 38 Koloni semut
123 47 Pohon pencarian biner Pohon pencarian biner, traversal pra/pasca-pesanan
124 55 Bar Pencarian lengkap, mundur
124 58 Oh, pohonku!
124 62 Persegi panjang Pencarian linier, tumpukan, topeng bit
124 94 Substring yang berbeda Lex. Rotasi minimal, algoritma Duvan, tabel hash
125 04 Memperbarui kamus Sortir cepat
126 40 Permainan jumlah terbesar Pencarian Linier, Subarray Jumlah Maksimum, Algoritma Kadane
126 97 Panjang subarray minimal Pencarian Linier, Subarray Jumlah Maksimum, Algoritma Kadane
127 02 Pelebaran Morfologi biner, pelebaran gambar biner
129 11 Jumlah subset Jumlah subset, pencarian lengkap, bertemu di tengah-tengah
130 50 Menemukan jalur Kombinatorik, hubungan kekambuhan
132 82 Cakey McCakeface (1) Pencarian Linear, Pencarian Linear
132 82 Cakey McCakeface (2) Bit topeng, ember

Kontes Komputasi Kinerja Tinggi Internasional

Sumber Masalah

PENGENAL Judul Kategori
C2 Dapatkan gambarnya Fractal, Mandelbrot Set, MPI, std::thread

Masalah dan Latihan Lainnya

Masalah lain -lain dari berbagai sumber online.

Judul Kategori
Array ke pohon pencarian biner Pohon pencarian biner
Array dengan unit adj. Pencarian Perbedaan Pencarian linier
Titik transisi array biner yang diurutkan Pencarian biner
Diameter pohon biner Pohon biner, traversal kedalaman-pertama
Tampilan teratas pohon biner Pohon biner, traversal pertama yang luas
Pencarian array bitonik Pencarian biner
Elemen umum dalam tiga array Pencarian linier
Titik koneksi dalam daftar tertaut berbentuk Y Daftar Singly-Linked
Hitung substring anagram Tabel hash, jendela geser
Hitung elemen yang lebih kecil di sebelah kanan Pohon AVL
Hitung kotak dalam kode pos Ekspresi analitik
Hitung kembar tiga Pencarian linier, Pencarian Jumlah Pasangan
Divisibilitas dalam aliran biner Aritmatika modular, Divisibilitas
Titik keseimbangan Pencarian linier
Menghasilkan tanda kurung (1) Combinatorics, backtracking
Memiliki subset dengan jumlah Pemrograman Dinamis
Adalah daftar tertaut adalah palindrome Daftar Singly-Linked
Adalah subtree (1) Pohon biner, traversal kedalaman-pertama
Elemen k-th dalam row-column sorted matrix Tumpukan
Jumlah terbesar dengan K Swaps Mundur
Persegi panjang terbesar dalam histogram Pencarian linier, tumpukan
Persegi terbesar matriks boolean Pemrograman Dinamis, Submatrix Kotak Terbesar
Dua digit terakhir fibonacci Jumlah Fibonacci, Aritmatika Modular, Eksponasi Biner
Daftar gabungan Daftar Singly-Linked
Daftar gabungan gabungan Daftar Singly-Linked, Gabungkan Sortir
Substring karakter terpanjang terpanjang Pencarian linier
Substring jumlah palindromik terpanjang Pencarian linier
Elemen mayoritas Algoritma pemungutan suara mayoritas boyer -moore
Membuat array semakin meningkat Peningkatan paling lama, pencarian biner
Rotasi Matriks Rotasi Matriks, Transposisi Matriks
Jarak maksimum antara elemen yang diurutkan Pencarian linier
Nilai numerik maksimum dalam suatu string Pencarian linier, perbandingan leksikografi
Maksimal setiap subarray (1) Jendela geser, pohon biner seimbang
Maksimal setiap subarray (1) Jendela geser, Deque
Produk maksimum 3 elemen Pencarian linier
Min-Stack Tumpukan
Elemen minimum dalam array yang diputar diurutkan Pencarian biner
Jumlah lompatan minimum (1) Pemrograman Dinamis
Jumlah lompatan minimum (2) Pencarian linier
Hampir disortir Sortir tumpukan, sortir penyisipan
Elemen Besar Berikutnya Pencarian linier, tumpukan
Node pada jarak k di pohon biner Pohon biner, traversal kedalaman-pertama
Jumlah jalur di dalam jaringan Kombinatorik
Partisi bahkan dan node aneh Daftar Singly-Linked
Mengantri sebagai dua tumpukan Antrian, tumpukan
Hapus node duplikat Daftar Singly-Linked
Hapus simpul tengah Daftar Singly-Linked
Kembalikan alfabet dari kamus Penyortiran topologi, algoritma Kahn
Membalikkan daftar yang terkait sendiri Daftar Singly-Linked
Membalik kata dalam string Pencarian linier
Putar daftar yang terhubung tunggal Daftar Singly-Linked
Pencarian array yang diputar Pencarian biner, pencarian linier
Terbesar kedua Statistik pesanan, elemen terbesar kedua, penghitung biner
Atur baris dan kolom jika Pencarian linier
Jumlah terkecil dalam permutasi Pencarian linier
Diurutkan dari ukuran ukuran 3 Pencarian linier
Diurutkan dari ukuran ukuran 4 Pencarian linier
Akar kuadrat Pencarian biner implisit
Subarray dengan jumlah yang diberikan Pencarian linier
Partisi tiga arah Partisi array
Dua elemen dengan jumlah yang diberikan Pencarian linier, tabel hash
Array yang sama tidak tertib Urutan, tabel hash
Daftar tertaut xor Daftar Doubly-Linked
Subarray Zero-Sum Pencarian linier, tabel hash
Memperluas
Informasi Tambahan
Aplikasi Terkait
Direkomendasikan untuk Anda
Informasi Terkait Semua