Competitive Programming Repository

การตั้งโปรแกรมการแข่งขัน

การรวบรวมอัลกอริทึมและโครงสร้างข้อมูลใน C ++ ใช้กันอย่างแพร่หลายในการแข่งขันการเขียนโปรแกรมที่แข่งขันได้

หัวข้อต่อไปนี้ครอบคลุม:

การอัปเดตและสอบถามช่วง

• แบบสอบถามรวมช่วง :
  • ต้นไม้ดัชนีไบนารี (บิต) :
    • แบบสอบถามช่วงการอัปเดตจุด
    • แบบสอบถามช่วงการอัปเดตช่วง
    • คำสั่งซื้อแบบสอบถามสถิติ
    • ต้นไม้ที่มีการจัดทำดัชนีแบบไบนารี 2d
  • ต้นไม้เซ็กเมนต์ (Segtree) :
    • แบบสอบถามช่วงการอัปเดตจุด
    • Segtrees ซ้ำเร็ว
    • แบบสอบถามจุดอัปเดตช่วง - Propogation ขี้เกียจ
    • ผลรวมย่อยสูงสุดในช่วง
    • ต้นไม้เซ็กเมนต์ 2d
    • ต้นไม้เซ็กเมนต์แบบไดนามิก - การแทรก/การลบระหว่างองค์ประกอบ
    • ต้นไม้เซ็กเมนต์แบบไดนามิก - ย้อนกลับเซ็กเมนต์
  • ผสานต้นไม้เรียงลำดับ :
    • ผสานต้นไม้เรียงลำดับ
    • ผสานต้นไม้เรียงลำดับ - สถิติการสั่งซื้อ
  • ตารางกระจัดกระจาย :
    • ช่วงการค้นหาขั้นต่ำ
  • อัลกอริทึม MO :
    • อัลกอริทึม MO - อาร์เรย์
• การเขียนโปรแกรมแบบไดนามิก :
  • เทมเพลตการเขียนโปรแกรมแบบไดนามิก :
    • digit dp / bitwise dp
  • ปัญหา DP มาตรฐาน :
    • ต่อมาเพิ่มขึ้นนานที่สุด
    • ลำดับที่ยาวที่สุด palindromic
    • ระยะทางเลเวนสไตน์ / ระยะแก้ไข
• กราฟ :
  • อัลกอริทึมเส้นทางที่สั้นที่สุดเดียว :
    • Dijkstra ในกราฟหนาแน่น
    • dijkstra โดยใช้คิวลำดับความสำคัญ
    • เส้นทางที่สั้นที่สุดระหว่างโหนดโดยใช้ dijkstra
    • การตรวจจับวัฏจักรเชิงลบของเบลแมนฟอร์ด
  • เส้นทางที่สั้นที่สุดคู่ทั้งหมด :
    • การใช้เลขชี้กำลังไบนารี
    • Floyd Warshall
  • การตรวจจับวัฏจักร :
    • การตรวจจับรอบในกราฟที่ไม่ได้กำกับ/กำกับ
  • ต้นไม้ที่ทอดน้อยที่สุด :
    • อัลกอริทึม Kruskal
  • การเรียงลำดับทอพอโลยี / ส่วนประกอบที่เชื่อมต่ออย่างยิ่ง :
    • การจัดเรียงทอพอโลยี
    • ส่วนประกอบที่เชื่อมต่ออย่างมาก
  • Maxflow/Matching :
    • การจับคู่ Hopkroft Karp Max
    • Dinic Max Flow
  • MISC :
    • สะพานในกราฟ
    • การเชื่อมต่อ
    • การตรวจสอบ bipartite
• ต้นไม้ :
  • คำค้นหาบรรพบุรุษ :
    • บรรพบุรุษสามัญต่ำสุด
    • Kth บรรพบุรุษ
  • แบบสอบถามเส้นทาง :
    • ตารางเบาบาง *
    • การสลายตัวของแสงหนักโหนดถ่วงน้ำหนัก
    • การสลายตัวของแสงหนักขอบถ่วงน้ำหนัก
  • MISC :
    • เส้นผ่านศูนย์กลางของต้นไม้
    • Preorder/Postorder Stamps อยู่ใน Subtree หรือไม่?
• การขยายไบนารี :
  • คำนวณ n^m โดยใช้การกำหนดไบนารี
  • การแก้ปัญหาการเกิดซ้ำเชิงเส้น
• สตริง :
  • อัลกอริทึมสตริง :
    • อัลกอริทึม Z
    • อัลกอริทึม KMP
    • การแฮ็กสตริงกลิ้ง
    • การแฮชสตริงแบบกลิ้งสำหรับสตริงแบบไดนามิก
  • โครงสร้างข้อมูลสตริง :
    • อาร์เรย์คำต่อท้าย *
• การเรียงลำดับ :
  • การเรียงลำดับ
  • เลือกอย่างรวดเร็ว
• อินพุต/เอาต์พุตที่รวดเร็วการแปลงสตริง/จำนวนเต็ม :
  • อินพุต/เอาต์พุตที่รวดเร็ว
  • การแปลงสตริง/จำนวนเต็ม
• อื่น ๆ โครงสร้างข้อมูล :
  • ชุดแยก
  • ชุดแยก (สนับสนุนการดำเนินการเลิกทำ)
  • คิวลำดับความสำคัญสูงสุด/นาทีพร้อมการอัปเดต
  • Binary Trie สำหรับการเพิ่มประสิทธิภาพของ XOR/minimization
  • Bigint *
  • ต้นไม้ไบนารีที่เพิ่มขึ้นสำหรับสถิติการสั่งซื้อและการสืบค้นอันดับ
  • คิวลำดับความสำคัญแบบเดียว
  • แต้ม
• โครงสร้างข้อมูลถาวร :
  • ต้นไม้เซ็กเมนต์แบบถาวร (Segtree) :
    • ต้นไม้เซ็กเมนต์แบบถาวร
    • ทรีเซ็กเมนต์แบบถาวร - สถิติการสั่งซื้อ
• อัลกอริทึมทฤษฎีจำนวน :
  • การตรวจสอบเบื้องต้น :
    • การตรวจสอบเบื้องต้นของ Fermat
  • ตะแกรง :
    • ตะแกรงของ Eratosthenes
    • ตะแกรงแบ่งส่วนสำหรับช่วงเวลาขนาดใหญ่
    • การนับปัจจัยสำคัญ
  • การคูณพหุนาม :
    • ฟูริเยร์ฟูริเยร์ฟูริเยร์
    • คารัทบะ
  • MISC :
    • combinatorial และ catalan - การประมวลผลล่วงหน้าแบบแฟคทอเรียล
    • ฟังก์ชั่น Mobeius
    • ฟังก์ชันออยเลอร์
    • Lucas Theorm - Combinatorics
• เรขาคณิตการคำนวณ :
  • นูน
• MISC :
  • ผลรวมของพื้น (x) ด้วย x = 1: n
  • ผลรวมของฟังก์ชั่นวงจร *
  • องค์ประกอบที่ใหญ่ที่สุดก่อน/หลังทุกองค์ประกอบ
  • จำนวนเต็มยาวหลายตัว
  • จำนวนเต็มยาวหลายตัว - การตรวจจับล้น
  • Scanline - ผสานช่วงตัดผ่าน