Competitive Programming Guide

Buku Panduan CP adalah satu tempat untuk semua pencinta program yang kompetitif kerana mengandungi semua algoritma dan struktur data. Juga setiap topik mengandungi contoh dan masalah yang tidak dapat diselesaikan untuk latihan.

Pengaturcaraan Bersaing adalah sukan, maksud saya secara harfiah. Ikuti sukan apa pun, mari kita mempertimbangkan kriket dalam hal ini, anda masuk untuk memukul buat pertama kalinya. Berayun dan ketinggalan, lakukan beberapa kali dan akhirnya anda akan terkena tali. Sekarang, pertimbangkan pertandingan pengaturcaraan sebagai permainan kriket, secara kiasan. Kumpulkan kod dan hantar, anda mungkin mendapat WA (Jawapan Salah).

Buat perubahan pada kod dan akhirnya anda akan mendapat AC pertama anda (Diterima / Betul Jawapan). Izinkan saya mengintip anda, kira-kira 20% soalan dalam pertandingan pengaturcaraan adalah penukaran bahasa Inggeris biasa kepada kod bahasa pengaturcaraan kegemaran anda.

Berjalan terus ke dalamnya, anda akan mempelajari peraturan permainan yang tidak tertulis semasa anda bermain lebih keras dan menjadi lebih baik.

 Dan percayalah, anda tidak perlu mengetahui algoritma "nama mewah" atau struktur data untuk memulakan. Pernah mendengar tentang "Waft shot", namun anda adalah pemukul terbaik di jalan anda, bukan?

Baiklah, mari kita mengatasi 20% masalah pengaturcaraan pertama di luar sana.

Anda perlu tahu:

Pertengahan pertengahan mana-mana bahasa pengaturcaraan

Bahasa Inggeris! Tukar bahasa Inggeris ke kod!

Mari kita ambil contoh masalah tahap ini: Chandu yang mengerikan

Yang perlu anda lakukan ialah, baca baris input dari STDIN dan cetak terbalik baris tersebut ke STDOUT. Teruskan, buat penyerahan. Cari AC pertama anda. Mahu lebih? Kami mempunyai banyak bahagian di bahagian latihan kami. Cari yang mempunyai ribuan penyerahan yang betul.

Baiklah, sekarang anda sudah bersedia untuk menghadapi cabaran sebenar. Pegang erat, kami menyelam lebih dalam.

Anda perlu tahu:

1. Susun dan Cari algoritma

2. Mencambuk

3. Teori Nombor

4. Teknik tamak

Lebih penting lagi, anda harus memikirkan apa, kapan dan di mana menggunakannya. Ia menjadi sangat sukar dan oleh itu untuk membantu para pemula memperoleh rasa percaya diri, kami menjalankan beberapa siri peraduan sebagai Code Monk. Sebelum setiap peraduan, kami mengeluarkan tutorial mengenai topik tertentu dan kemudian dalam peraduan masalah hanya ditujukan pada topik tertentu. Saya mengesyorkan anda membaca tutorial dan menyelesaikan satu atau dua soalan mengenai setiap topik.

Sekarang anda telah menyedari bahawa soalan-soalan itu dibentuk untuk menipu cara kita berfikir. Kadang kala, Jika anda menukar bahasa inggeris menjadi kod, anda akan mendapat keputusan TLE (Had Masa Melebihi). Anda perlu mempelajari satu set teknik dan algoritma baru untuk mengatasi had masa. Dalam kes tertentu, Pengaturcaraan Dinamik (DP) dapat menyelamatkannya. Sebenarnya, anda mungkin sudah menggunakan teknik ini secara intuitif. Selalu ada sekurang-kurangnya satu soalan dalam setiap pertandingan yang dapat diselesaikan oleh DP.

Anda juga perasan bahawa ada soalan yang tidak dapat diselesaikan dengan struktur data array linear.

1. Teori Grafik

2. Disjoint Set Union (Union-cari)

3. Pokok Rentang Minimum

Set struktur data ini akan membawa anda cukup jauh. Lebih-lebih lagi, anda pasti menganggap bahawa seni yang sebenarnya adalah mengubah teknik yang anda ketahui untuk menyelesaikan soalan. Semua soalan tahap Mudah-Sederhana dan Sederhana dapat diselesaikan dengan cara ini.

Anda sudah siap untuk menduduki tangga teratas Cabaran Pengaturcaraan Pendek, teruskan kegigihan. Seperti yang telah saya nyatakan, ini adalah sukan, anda tidak akan dapat menguasainya sehingga anda berjaya melakukannya. Teruskan, sertai peraduan pendek, ketahui kekuatan, kelemahan dan lihat bagaimana anda mengendalikan mod adrenalin ketika jam berdetik.

Ikutilah logik anda sendiri selama mungkin, anda akhirnya akan menghasilkan sesuatu yang serupa dengan algoritma yang diperlukan untuk menyelesaikan soalan. Anda hanya perlu menyikatnya. Beberapa teknik ini akan membantu anda menyelesaikan beberapa masalah yang paling sukar di sekitar.

1. Pokok Segmen

2. Algoritma Rentetan

3. Percubaan, Pohon Suffix, Array Suffix.

4. Penguraian Cahaya Berat

5. Pewarnaan Grafik, Aliran Rangkaian

6. Penguraian Sqrt.

Oleh itu, Muat turun Buku Panduan CP ini dan nikmati mempelajari perkara-perkara baru juga jangan lupa untuk MENGATASI mereka dengan Kerumitan Masa yang kurang.