competitive_programming

การเขียนโปรแกรมและแบบฝึกหัดการแข่งขัน

นี่คือโซลูชั่น C ++ ของฉันเกี่ยวกับปัญหาการเขียนโปรแกรมที่แข่งขันได้และแบบฝึกหัดต่าง ๆ ปัญหาที่คล้ายกันได้รับการแก้ไขโดยใช้อัลกอริทึมและโครงสร้างข้อมูลที่แตกต่างกัน - บางครั้งใช้สิ่งที่ได้รับจากไลบรารีมาตรฐานบางครั้งใช้ของฉันเอง

โซลูชันส่วนใหญ่อยู่ใน C+11 เนื่องจาก EX-UVA ข้อ จำกัด การตัดสินออนไลน์ บางส่วนของพวกเขาหลังจากการส่งที่ประสบความสำเร็จได้รับการแก้ไขเพื่อใช้คุณสมบัติ C ++ 14/17

ปัญหา Ex-Uva OJ

แหล่งที่มาของปัญหา

รหัสประจำตัว	ชื่อ	หมวดหมู่
001 08	ผลรวมสูงสุด	การค้นหาเชิงเส้น, subarray ผลรวมสูงสุด, อัลกอริทึมของ Kadane
001 09	บัสเตอร์สกั๊ด	นูน
001 12	การรวมต้นไม้	ต้นไม้ไบนารี
001 20	สแต็คของ flapjacks	สแต็คการเรียงลำดับแพนเค้ก
001 22	ต้นไม้ในระดับ	ทรีไบนารีการเดินทางแบบลำดับชั้นตามลำดับการค้นหาแบบกว้างก่อน
001 40	แบนด์วิดธ์	การเรียงลำดับการย้อนรอย
001 47	เงินดอลลาร์	การเขียนโปรแกรมแบบไดนามิกการเปลี่ยนแปลงเหรียญ
001 64	คอมพิวเตอร์สตริง	การเขียนโปรแกรมแบบไดนามิกแก้ไขระยะทาง
002 00	คำสั่งหายาก	การเรียงลำดับทอพอโลยีการค้นหาครั้งแรก
002 16	เข้าแถว	การเขียนโปรแกรมแบบไดนามิกเส้นทางแฮมิลตันมาสก์บิต
002 18	การกำจัดมอด	นูน
002 22	การเดินทางงบประมาณ
002 40	การเข้ารหัส Radix Huffman ตัวแปร	Huffman Tree, การค้นหาครั้งแรก
002 59	การจัดสรรซอฟต์แวร์
002 64	ไว้วางใจคันทอร์
002 70	ซับใน
002 94	ตัวหาร
003 34	ระบุเหตุการณ์ที่เกิดขึ้นพร้อมกัน
003 48	อาร์เรย์ที่ดีที่สุด ลำดับ	การเขียนโปรแกรมแบบไดนามิกการคูณโซ่เมทริกซ์
003 50	ตัวเลขสุ่มหลอก
003 53	palindromes ที่น่ารำคาญ	แฮชกลิ้งพหุนามการประมวลผลสตริง
003 57	นับวิธี
003 61	ตำรวจและโจร
003 72	สัญกรณ์ whatfix	Tree Binary, การแปลงการเดินทางข้ามล่วงหน้าก่อน/in-/post-order
003 74	MOD ขนาดใหญ่	การชดเชยแบบไบนารี, การชดเชยแบบแยกส่วน
004 29	การแปลงคำ
004 37	หอคอยแห่งบาบิโลน
004 39	อัศวินเคลื่อนไหว	การค้นหาครั้งแรกที่กว้าง
004 54	แอนนาแกรม
004 55	สตริงเป็นระยะ	สตริงอัลกอริทึม Knuth - Morris - Pratt
004 59	การเชื่อมต่อกราฟ	ส่วนประกอบที่เชื่อมต่อกราฟ
004 69	พื้นที่ชุ่มน้ำแห่งฟลอริดา
004 81	เกิดอะไรขึ้น	การค้นหาแบบไบนารีที่เพิ่มขึ้นนานที่สุด
004 82	อาร์เรย์เรียงความ
005 01	กล่องดำ	ต้นไม้ AVL, Iterator Tree Binary
005 07	จิลล์ขี่อีกครั้ง	การค้นหาเชิงเส้น, subarray ผลรวมสูงสุด, อัลกอริทึมของ Kadane
005 16	ดินแดนสำคัญ
005 26	ระยะสตริง	การเขียนโปรแกรมแบบไดนามิกแก้ไขระยะทาง
005 36	การฟื้นตัวของต้นไม้	Tree Binary, การแปลงการเดินทางข้ามล่วงหน้าก่อน/in-/post-order
005 40	คิวทีม
005 43	การคาดเดาของ Goldbach	จำนวนนายก
005 48	ต้นไม้
005 51	การทำรังของวงเล็บ
005 58	หนอน
005 62	หารเหรียญ
005 68	เพียงแค่ข้อเท็จจริง	แฟคทอเรียล
005 74	สรุป
005 82	ตาข่ายประสาทแบบมีสายแบบสุ่ม	การค้นหาที่ลึกครั้งแรกส่วนประกอบกราฟ biconnected
005 83	ปัจจัยสำคัญ
006 12	การเรียงลำดับดีเอ็นเอ	รวมเรียงลำดับการนับการผกผัน
006 23	500!	แฟคทอเรียลจำนวนเต็มขนาดใหญ่
006 30	แอนนาแกรม
006 39	อย่าได้รับการชื่นชม
006 74	การเปลี่ยนเหรียญ
006 79	ลูกหล่น
006 84	ตัวกำหนดอินทิกรัล	การกำจัดแบบเกาส์เซียนอัลกอริทึมยุคลิด
006 86	การคาดเดาของ Goldbach II	จำนวนนายก
007 01	ภาวะที่กลืนไม่เข้าคายไม่ออกของนักโบราณคดี	ลอการิทึม
007 14	การคัดลอกหนังสือ	การแบ่งพาร์ติชันเชิงเส้นการค้นหาไบนารีโดยนัย
007 19	ลูกปัดแก้ว	อัลกอริทึมของ Duvan
007 27	สมการ	การแยกวิเคราะห์การแสดงออกอัลกอริทึมลาน
007 29	ปัญหาระยะทาง hamming	การย้อนรอย
007 50	ปัญหาหมากรุกของควีนส์แปดตัว	การย้อนรอย
007 87	ผลิตภัณฑ์ลำดับย่อยสูงสุด	subarray ผลิตภัณฑ์สูงสุดจำนวนเต็มขนาดใหญ่
007 93	การเชื่อมต่อเครือข่าย
007 96	ลิงค์ที่สำคัญ	การค้นหาครั้งแรกที่ลึกซึ้งกราฟบริดจ์
008 20	แบนด์วิดธ์อินเทอร์เน็ต
008 33	น้ำตก
008 68	เขาวงกตเชิงตัวเลข	การย้อนรอย
008 72	การสั่งซื้อ
009 08	เชื่อมต่อเว็บไซต์คอมพิวเตอร์อีกครั้ง
009 29	จำนวนเขาวงกต
009 42	ตัวเลขวัฏจักร	จำนวนเหตุผลเศษส่วนทศนิยมตารางแฮช
009 90	ดำน้ำเพื่อทองคำ
009 91	คำทักทายที่ปลอดภัย	Combinatorics, ความสัมพันธ์การเกิดซ้ำ, หมายเลขคาตาลัน
011 21	ลำดับ	หน้าต่างเลื่อน
011 75	ทางเลือกของผู้หญิง	ปัญหาการจับคู่ที่มั่นคงอัลกอริทึม Gale-Shapley
012 10	ผลรวมของจำนวนนายกติดต่อกัน	จำนวนนายก
012 52	ยี่สิบคำถาม
012 60	ฝ่ายขาย
012 93	การได้มาเป็นสัญลักษณ์	การแยกวิเคราะห์การแสดงออก, อัลกอริทึมลาน,, symbolic eval
013 72	บันทึกการกระโดด
016 50	สตริงหมายเลข	Combinatorics, ความสัมพันธ์การเกิดซ้ำ
100 03	แท่งตัด
100 04	การทำสีสองทาง
100 18	ย้อนกลับและเพิ่ม	จำนวนเต็ม 196 อัลกอริทึม
100 61	ศูนย์และตัวเลขกี่ตัว?	แฟคทอเรียล, ตัวเลขที่สำคัญ, การแยกตัวประกอบ, ลอการิทึม
100 79	การตัดพิซซ่า	Combinatorics, ตัวเลขรูปหลายเหลี่ยมกลาง
101 07	ค่ามัธยฐานคืออะไร	คิวลำดับความสำคัญอัลกอริทึมออนไลน์
101 71	พบศาสตราจารย์ มิเกล
101 93	สิ่งที่คุณต้องการคือความรัก	ตัวหารที่ยิ่งใหญ่ที่สุด
102 20	ฉันรักตัวเลขใหญ่!	แฟคทอเรียลจำนวนเต็มขนาดใหญ่
102 23	กี่โหนด	Combinatorics, ความสัมพันธ์การเกิดซ้ำ, หมายเลขคาตาลัน
102 29	ฟีโบนัคชีแบบแยกส่วน	หมายเลข Fibonacci, การยกระดับแบบแยกส่วน
102 45	ปัญหาคู่ที่ใกล้ที่สุด	คู่ที่ใกล้เคียงที่สุด 2d
102 68	498-bis	กฎของฮอร์เนอร์
102 82	Babelfish	ตารางแฮช
102 98	สายไฟ
103 05	งานสั่งซื้อ
103 11	โกลด์บาคและออยเลอร์	จำนวนนายก
103 19	ประเทศแมนฮัตตัน
103 27	การจัดเรียง	ต้นไม้ AVL
103 41	แก้ปัญหา	ตัวเลขวิธีการของนิวตัน
103 64	สี่เหลี่ยม	การย้อนรอยหน้ากากบิต
103 82	หญ้ารดน้ำ	โลภครอบคลุมช่วงเวลา
104 28	ราก	การค้นหารูทวิธีการแบ่งแยก
104 54	การบีบอัด	การแยกวิเคราะห์การแสดงออก, อัลกอริทึมหลา, หมายเลขคาตาลัน
104 96	การรวบรวมบี๊บ
105 33	ตัวเลขหลัก
105 67	ช่วยเติมเบตส์
105 70	พบกับมนุษย์ต่างดาว	การเปลี่ยนแปลงการนับการแลกเปลี่ยนการนับรอบ
105 76	ข้อผิดพลาดการบัญชี Y2K
105 86	ซากพหุนาม
106 00	การประกวด ACM และความมืดมน
106 04	ปฏิกิริยาเคมี
106 51	Pebble Solitaire
106 55	การไตร่ตรอง! พีชคณิต	ความสัมพันธ์ที่เกิดซ้ำการชดเชยแบบแยกส่วน
106 64	กระเป๋าเดินทาง
106 84	แจ็คพอต
106 99	นับปัจจัย	ตัวเลขที่สำคัญการสลายตัวของนายก
107 23	ยีนไซบอร์ก
107 38	Riemann vs Mertens	ตัวเลขที่สำคัญ, ฟังก์ชั่นMöbius, ฟังก์ชั่น Mertens
108 01	ยกกระโดด
108 10	Ultra Quicksort	การเรียงลำดับ/การแทรกการนับการนับจำนวน
108 55	สี่เหลี่ยมหมุน	การหมุนของเมทริกซ์การขนย้ายเมทริกซ์
108 70	การเกิดซ้ำ
109 20	แตะเกลียว	การวิเคราะห์
109 31	ความเท่าเทียมกัน
109 34	บอลลูนน้ำทิ้ง
109 35	ทิ้งการ์ด	รายการคิว
109 38	Flea Circus
109 54	เพิ่มทั้งหมด	กอง
109 57	Su Doku Checker	Backtracking, Bit Mask
109 94	เพิ่มเติมง่ายๆ	การวิเคราะห์
110 57	ผลรวมที่แน่นอน
110 60	เครื่องดื่ม
110 77	ค้นหาการเรียงสับเปลี่ยน	Combinatorics, ความสัมพันธ์การเกิดซ้ำ, ตัวเลขสเตอร์ลิง
111 37	คิวบา
111 51	palindrome ที่ยาวที่สุด	การเขียนโปรแกรมแบบไดนามิกการประมวลผลสตริง
111 71	SMS	การเขียนโปรแกรมแบบไดนามิกการประมวลผลสตริง Trie
111 95	อีกปัญหา N -queen	Backtracking, Bit Mask
112 27	กระสุนเงิน
112 35	ค่าบ่อย
112 36	ร้านขายของชำ
112 57	แผนการตลาดใหม่	รูปหลายเหลี่ยมรัศมีวงกลมที่จารึกไว้คิวลำดับความสำคัญ
112 58	พาร์ติชันสตริง	การเขียนโปรแกรมแบบไดนามิก
112 60	ผลรวมรากคี่	นิพจน์การวิเคราะห์, Impl. การค้นหาแบบไบนารีเลขคณิตแบบแยกส่วน
112 71	ตาข่ายของตัวต้านทาน	ความสัมพันธ์ที่เกิดซ้ำการขยายตัวของซีมโทติค
112 83	เล่น Boggle	การย้อนรอย
112 97	การสำรวจสำมะโนประชากร	2d Sqrt Decomposition
113 62	รายการโทรศัพท์	Trie, คำนำหน้าการจับคู่
114 13	เติมภาชนะ
114 20	หีบลิ้นชัก	Combinatorics, ความสัมพันธ์การเกิดซ้ำ
114 56	การฝึกซ้อม
114 61	หมายเลขสี่เหลี่ยมจัตุรัส	การค้นหาไบนารีโดยนัย
114 62	อายุ	นับเรียงลำดับ
114 63	หน่วยคอมมานโด
114 75	ขยายไปถึง palindrome
115 17	การเปลี่ยนแปลงที่แน่นอน
115 36	อาเรย์ย่อยที่เล็กที่สุด	หน้าต่างเลื่อน
115 72	เกล็ดหิมะที่เป็นเอกลักษณ์	การค้นหาเชิงเส้นตารางแฮช
115 84	การแบ่งพาร์ติชันโดย palindromes
116 21	ปัจจัยเล็ก ๆ	ลอการิทึม
116 34	สร้างตัวเลขสุ่ม
116 36	สวัสดีโลก!	การวิเคราะห์การวิเคราะห์ลอการิทึม
116 58	พันธมิตรที่ดีที่สุด
116 86	รับแท่ง
116 91	การทดสอบโรคภูมิแพ้
117 03	sqrt, log, sin	ความสัมพันธ์ที่เกิดซ้ำ
117 14	การเรียงลำดับคนตาบอด	สถิติการสั่งซื้อ (ใหญ่ที่สุด เป็น อันดับ 2)
117 33	สนามบิน
119 02	ผู้ปกครอง
119 91	ปัญหาง่าย ๆ จาก Rujia Liu?	การเรียงลำดับการค้นหาแบบไบนารี
119 97	K กี้เล็กที่สุด
120 86	โพเทนชิโอมิเตอร์	ต้นเฟนวิค
121 05	ใหญ่กว่าดีกว่า (1)
121 05	ใหญ่กว่าดีกว่า (2)
121 92	ต้นองุ่น	การค้นหาแบบไบนารี
122 38	มดอาณานิคม
123 47	แผนผังไบนารี	แผนผังค้นหาไบนารีการสำรวจก่อน/หลังการสั่งซื้อ
124 55	บาร์	การค้นหาที่สมบูรณ์ย้อนรอย
124 58	โอ้ต้นไม้ของฉัน!
124 62	สี่เหลี่ยมผืนผ้า	การค้นหาเชิงเส้น, สแต็ค, หน้ากากบิต
124 94	สายย่อยที่แตกต่างกัน	ไฟแนนเชี่ยล การหมุนขั้นต่ำอัลกอริทึมของ Duvan ตารางแฮช
125 04	อัปเดตพจนานุกรม	จัดเรียงอย่างรวดเร็ว
126 40	เกมผลรวมที่ใหญ่ที่สุด	การค้นหาเชิงเส้น, subarray ผลรวมสูงสุด, อัลกอริทึมของ Kadane
126 97	ความยาว subarray ขั้นต่ำ	การค้นหาเชิงเส้น, subarray ผลรวมสูงสุด, อัลกอริทึมของ Kadane
127 02	การขยาย	สัณฐานวิทยาไบนารีการขยายภาพไบนารี
129 11	ผลรวมชุดย่อย	ผลรวมชุดย่อยการค้นหาที่สมบูรณ์พบกันกลาง
130 50	ค้นพบเส้นทาง	Combinatorics, ความสัมพันธ์การเกิดซ้ำ
132 82	Cakey McCakeface (1)	การเรียงลำดับการค้นหาเชิงเส้น
132 82	Cakey McCakeface (2)	หน้ากากบิต

การประกวดคอมพิวเตอร์ประสิทธิภาพสูงระหว่างประเทศ

แหล่งที่มาของปัญหา

รหัสประจำตัว	ชื่อ	หมวดหมู่
C2	รับภาพ	Fractal, Mandelbrot Set, MPI, std::thread

ปัญหาและการออกกำลังกายอื่น ๆ

ปัญหาเบ็ดเตล็ดจากแหล่งออนไลน์ที่แตกต่างกัน

ชื่อ	หมวดหมู่
อาเรย์ไปยังแผนผังไบนารี	แผนผังไบนารี
อาร์เรย์พร้อมหน่วย adj การค้นหาที่แตกต่างกัน	การค้นหาเชิงเส้น
จุดเปลี่ยนอาร์เรย์แบบเรียงลำดับแบบไบนารี	การค้นหาแบบไบนารี
เส้นผ่านศูนย์กลางของต้นไม้ไบนารี	ต้นไม้ไบนารีการสำรวจความลึกเป็นครั้งแรก
มุมมองด้านบนของต้นไม้ไบนารี	ต้นไม้ไบนารีการเดินทางครั้งแรกที่กว้าง
ค้นหาอาร์เรย์ Bitonic	การค้นหาแบบไบนารี
องค์ประกอบทั่วไปในสามอาร์เรย์	การค้นหาเชิงเส้น
จุดเชื่อมต่อในรายการที่เชื่อมโยงรูปตัว y	รายการเชื่อมโยง
นับหมวดย่อยแอนนาแกรม	ตารางแฮชหน้าต่างเลื่อน
นับองค์ประกอบเล็ก ๆ ทางด้านขวา	ต้นไม้ AVL
นับสี่เหลี่ยมในรหัสไปรษณีย์	การวิเคราะห์
นับแฝดสาม	การค้นหาเชิงเส้นคู่ค้นหาผลรวม
การแบ่งแยกในลำธารไบนารี	เลขคณิตแบบแยกส่วนแบ่งแยกได้
จุดดุลยภาพ	การค้นหาเชิงเส้น
สร้างวงเล็บ (1)	Combinatorics, backtracking
มีชุดย่อยที่มีผลรวม	การเขียนโปรแกรมแบบไดนามิก
เป็นรายการที่เชื่อมโยงกับ palindrome	รายการเชื่อมโยง
เป็นทรีย่อย (1)	ต้นไม้ไบนารีการสำรวจความลึกเป็นครั้งแรก
องค์ประกอบ K-th ในเมทริกซ์เรียงลำดับคอลัมน์คอลัมน์	กอง
จำนวนมากที่สุดพร้อมการแลกเปลี่ยน k	การย้อนรอย
สี่เหลี่ยมที่ใหญ่ที่สุดในฮิสโตแกรม	การค้นหาเชิงเส้นสแต็ก
สี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดเมทริกซ์บูลีน	การเขียนโปรแกรมแบบไดนามิก submatrix สี่เหลี่ยมที่ใหญ่ที่สุด
สองหลักสุดท้ายของ Fibonacci	ตัวเลข Fibonacci, เลขคณิตแบบแยกส่วน, การยกตัวแบบไบนารี
รายการผสาน	รายการเชื่อมโยง
รายการรวมเรียงลำดับ	รายการที่เชื่อมโยงกับการเรียงลำดับ
สตริงย่อยตัวอักษรที่ยาวที่สุด	การค้นหาเชิงเส้น
สตริงย่อยที่ยาวที่สุด palindromic	การค้นหาเชิงเส้น
ส่วนใหญ่	อัลกอริทึมการโหวตเสียงข้างมากของ Boyer - Moore
ทำให้อาร์เรย์เพิ่มขึ้นอย่างเคร่งครัด	การค้นหาแบบไบนารีที่เพิ่มขึ้นนานที่สุด
การหมุนของเมทริกซ์	การหมุนของเมทริกซ์การขนย้ายเมทริกซ์
ระยะห่างสูงสุดระหว่างองค์ประกอบที่จัดเรียง	การค้นหาเชิงเส้น
ค่าตัวเลขสูงสุดในสตริง	การค้นหาเชิงเส้นการเปรียบเทียบพจนานุกรม
สูงสุดของแต่ละ subarray (1)	หน้าต่างบานเลื่อนต้นไม้ไบนารีที่สมดุล
สูงสุดของแต่ละ subarray (1)	หน้าต่างบานเลื่อน deque
ผลิตภัณฑ์สูงสุด 3 องค์ประกอบ	การค้นหาเชิงเส้น
ซ้อนขั้นต่ำ	กองซ้อน
องค์ประกอบขั้นต่ำในอาร์เรย์หมุนแบบเรียงลำดับ	การค้นหาแบบไบนารี
จำนวนการกระโดดขั้นต่ำ (1)	การเขียนโปรแกรมแบบไดนามิก
จำนวนการกระโดดขั้นต่ำ (2)	การค้นหาเชิงเส้น
เกือบเรียงลำดับ	การเรียงลำดับกองเรียงลำดับการแทรก
องค์ประกอบที่ยิ่งใหญ่กว่าถัดไป	การค้นหาเชิงเส้นสแต็ก
โหนดที่ระยะไกล k ในต้นไม้ไบนารี	ต้นไม้ไบนารีการสำรวจความลึกเป็นครั้งแรก
จำนวนเส้นทางในตาราง	combinatorics
พาร์ติชันแม้โหนดแปลก ๆ	รายการเชื่อมโยง
คิวเป็นสองสแต็ค	คิวสแต็ก
ลบโหนดที่ซ้ำกัน	รายการเชื่อมโยง
ลบโหนดกลาง	รายการเชื่อมโยง
คืนค่าตัวอักษรจากพจนานุกรม	การเรียงลำดับทอพอโลยีอัลกอริทึมของ Kahn
ย้อนกลับรายการที่เชื่อมโยงอย่างเดียว	รายการเชื่อมโยง
ย้อนกลับคำในสตริง	การค้นหาเชิงเส้น
หมุนรายการที่เชื่อมโยงอย่างเดียว	รายการเชื่อมโยง
การค้นหาอาร์เรย์แบบหมุน	การค้นหาแบบไบนารีการค้นหาเชิงเส้น
ใหญ่เป็นอันดับสอง	สถิติการสั่งซื้อองค์ประกอบที่ใหญ่เป็นอันดับสองเคาน์เตอร์ไบนารี
ตั้งแถวและคอลัมน์ถ้า	การค้นหาเชิงเส้น
จำนวนน้อยที่สุดในการเปลี่ยนแปลง	การค้นหาเชิงเส้น
เรียงลำดับตามขนาด 3	การค้นหาเชิงเส้น
เรียงลำดับตามขนาด 4	การค้นหาเชิงเส้น
รากที่สอง	การค้นหาไบนารีโดยนัย
subarray ด้วยผลรวมที่กำหนด	การค้นหาเชิงเส้น
พาร์ติชันสามทาง	การแบ่งพาร์ติชันอาร์เรย์
สององค์ประกอบที่มีผลรวมที่กำหนด	การค้นหาเชิงเส้นตารางแฮช
อาร์เรย์ที่ไม่ได้เรียงลำดับ	ลำดับตารางแฮช
รายการ xor linked	รายการเชื่อมโยงสองเท่า
subarray zero-sum	การค้นหาเชิงเส้นตารางแฮช