Usaco2011

USACO OPEN 2011

Problem 1: Mowing the Lawn [Neal Wu, 2008]

หลังจากที่ชาวนาจอห์นชนะการประกวดสนามหญ้าเมื่อปีก่อน เขาก็เริ่มขี้เกียจ เขาไม่ได้ตัดหญ้ามาตั้งแต่ตอนนั้น ซึ่งทำให้สนามหญ้าของเขารกมาก อย่างไรก็ตาม การประกวดกำลังจะเริ่มต้นเร็ว ๆ นี้ และ FJ ต้องการจะจัดการกับสนามหญ้าของเขาให้เรียบร้อยเพื่อที่จะได้พร้อมเข้าประกวด

FJ จะใช้วัว N ตัว (1 <= N <= 100,000) ที่เรียงต่อกันเป็นเส้น โดยมีหมายเลขตั้งแต่ 1 ถึง N มาช่วยจัดการกับสนามหญ้า วัวบางตัวจะมีประสิทธิภาพมากกว่าวัวตัวอื่น วันตัวที่ i มีประสิทธิภาพ E_i หน่วย (0 <= E_i <= 1,000,000,000)

FJ สังเกตว่าวัวตัวที่อยู่ติดกันมักรู้จักวัวตัวอื่น เขายังทราบว่าถ้าเขาเลือกวัวมากกว่า K ตัวติดกัน (1 <= K <= N) วัวเหล่านั้นจะไม่ทำงานและเริ่มจัดงานเลี้ยงแทน ดังนั้น FJ จึงต้องการให้คุณช่วยเลือกวัว ให้ได้ผลรวมของประสิทธิภาพมากที่สุด โดยที่ไม่เลือกวัว K ตัวติดกันเลย

Problem 2: Odd degrees [Traditional, 2011]

เหล่าวัวถูกบุกรุก! อาณาจักรของพวกเขาประกอบไปด้วยเมือง N เมือง (1 <= N <= 50,000) ที่เชื่อมต่อกันด้วยเส้นทาง M เส้น (1 <= M <= 100,000) ที่ไม่มีทิศทาง โดยสำหรับเส้นทางเส้นที่ i จะเชื่อมระหว่างเมือง A_i และ B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i; และไม่มีเส้นทางที่ซ้ำกัน) อย่างไรก็ตามอาณาจักรไม่จำเป็นต้องเชื่อมต่อกันทั้งหมด อาจจะมีเมืองบางกลุ่มที่ไม่สามารถเดินทางไปถึงเมืองอีกบางกลุ่มได้ผ่านทางเส้นทาง

เหล่าวัวทราบว่าผู้บุกรุกต้องการเก็บข้อมูลของเส้นทางทุกเส้นในอาณาจักร พวกวัวจึงต้องการจะปิดเส้นทางบางเส้นเพื่อทำให้ผู้บุกรุกทำงานได้ลำบาก

ช่วยเหล่าวัวหาวิธีในการปิดสับเซตของเส้นทางเพื่อที่จะรับประกันว่าในทุก ๆ เมือง จะมีเส้นทางที่เหลือที่ติดกับเมืองนั้นเป็นจำนวนคี่ หรือรายงานว่าสับเซตดังกล่าวไม่มี

พิจารณาตัวอย่าง

1---2
 \ /
  3---4

ถ้าเราเก็บเส้นทาง 1-3, 2-3, และ 3-4, และลบเส้นทาง 1-2, เมือง 1, 2, 4 เป็นเป็นจุดปลายของเส้นทางแค่หนึ่งเส้น และเมืองที่ 3 จะมีจุดปลายของถนนสามเส้น ดังรูป

1   2
 \ /
  3---4