บิตมาสก์ในฐานะเซตขนาดเล็ก
แทนเซตย่อยด้วยจำนวนเต็ม
บิตมาสก์ในฐานะเซตขนาดเล็ก เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
จำนวนเต็มแทนเซต
จำนวนเต็มเพียงตัวเดียวสามารถแทนเซตทั้งเซตได้: หากบิต i เป็น 1 หมายความว่าสมาชิก i อยู่ในเซต วิธีนี้บรรจุสับเซตไว้ในค่าขนาดเล็กและรวดเร็วเพียงค่าเดียว 🎒
เซตว่างและเซตเต็ม
เลข 0 คือเซตว่าง ส่วนค่าที่ n บิตล่างสุดเป็น ON ทั้งหมด หมายความว่าสมาชิกทุกตัวอยู่ในเซต
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsเพิ่มสมาชิก
หากต้องการเพิ่มสมาชิก i ลงในเซต ให้ใช้ OR กับบิตของสมาชิกนั้น นี่คือการตั้งค่าบิตแบบเดียวกัน เพียงมองในรูปของยูเนียนกับสมาชิกหนึ่งตัว
s = 0
s |= (1 << 2) # add element 2ลบสมาชิก
หากต้องการลบสมาชิก i ให้ใช้ AND กับบิตกลับด้าน สมาชิกนั้นจะออกจากเซต ส่วนสมาชิกอื่นยังคงอยู่ นี่คือผลต่างของเซตโดยลบสมาชิกหนึ่งตัว
s &= ~(1 << 2) # remove element 2ตรวจสอบการเป็นสมาชิก
ตรวจสอบว่าสมาชิก i อยู่ในเซตหรือไม่ด้วยการใช้ AND กับบิตของสมาชิกนั้น หากผลลัพธ์ไม่เป็นศูนย์ แสดงว่าสมาชิกนั้นเป็นสมาชิกของเซต
if s & (1 << 2):
print('2 is in the set')ยูเนียนและอินเตอร์เซกชัน
ใช้ OR กับมาสก์สองตัวเพื่อหาค่ายูเนียน และใช้ AND เพื่อหาค่าอินเตอร์เซกชัน การดำเนินการกับเซตทั้งเซตจึงกลายเป็นคำสั่งเครื่องอย่างละหนึ่งคำสั่ง
union = a | b
inter = a & bขนาดเซตคือจำนวนบิตที่เป็น 1
จำนวนสมาชิกในมาสก์บิตก็คือจำนวนบิต 1 ของมาสก์นั้น ใช้ bit_count เพื่อหาขนาดได้ทันที
size = mask.bit_count()วนดูสับเซตทั้งหมด
สำหรับสมาชิก n ตัว จำนวนเต็มตั้งแต่ 0 ถึง 2 ยกกำลัง n ลบ 1 จะแสดงสับเซตทุกสับเซต ลูปช่วงแบบง่ายเพียงลูปเดียวก็ครอบคลุมทั้งหมด
for mask in range(1 << n):
pass # mask is one subsetวนดูมาสก์ย่อยอย่างรวดเร็ว
หากต้องการดูเฉพาะสับเซตของมาสก์ที่กำหนด ให้ใช้ลูปมาสก์ย่อยแบบคลาสสิก ลูปนี้จะไล่ผ่านแต่ละสับเซตจากค่ามากไปค่าน้อย
sub = mask
while sub:
sub = (sub - 1) & maskDP ด้วยมาสก์บิต
มาสก์บิตเป็นสถานะสำหรับโจทย์ DP จำนวนมาก เช่น ปัญหาเซลส์แมนเดินทาง ซึ่งมาสก์จะติดตามว่าโหนดใดบ้างที่คุณเยี่ยมชมแล้ว
รักษาให้ n มีค่าขนาดเล็ก
เนื่องจากมีสับเซต 2 ยกกำลัง n วิธีนี้จึงใช้งานได้จริงเฉพาะเมื่อ n มีค่าขนาดเล็ก โดยปกติไม่เกินประมาณ 20 หากมากกว่านั้นจำนวนจะเพิ่มขึ้นอย่างรวดเร็ว ⚠️
ตรวจสอบอย่างรวดเร็ว
คำถามสุดท้ายเกี่ยวกับการใช้มาสก์แทนเซต
ทบทวน: เซตด้วยมาสก์บิต
คุณสามารถเก็บเซตไว้ในจำนวนเต็มเพียงตัวเดียว เพิ่มและลบสมาชิกด้วยมาสก์ และวนดูสับเซตทุกสับเซตได้ แนวคิดนี้ทำให้ใช้ DP ด้วยมาสก์บิตได้อย่างรวดเร็ว 🎉
คำถามที่พบบ่อย
บทเรียน “บิตมาสก์ในฐานะเซตขนาดเล็ก” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “บิตมาสก์ในฐานะเซตขนาดเล็ก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “บิตมาสก์ในฐานะเซตขนาดเล็ก”
แทนเซตย่อยด้วยจำนวนเต็ม คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “บิตมาสก์ในฐานะเซตขนาดเล็ก” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- AND, OR, XOR และการเลื่อนบิต
- ตั้งค่า ล้าง และสลับบิต
- นับบิตและบิตที่ถูกตั้งค่าต่ำสุด
- บิตมาสก์ในฐานะเซตขนาดเล็ก