一道來自 IPSC的題目
IPSC這個比賽很有意思 所有題目都是提交答案式的 可惜我英文不好 還要組隊
有意與我組隊請與我聯系 我的郵箱：wwy250@gmail.com
還有通過這個比賽的排名還是看出中國的教育存在著巨大的問題
學生組具有壟斷地位 而成人組就不行了
言歸正傳
很容易想到的是二分圖最大匹配的問題 可以在比賽的時間內跑出來
還有一種更優的方法 對于每種S 可以在O(1)時間內接觸c
對于每一種S:{a1,a2,～～,a(n+1)/2} (a1<a2<～～<a(n+1)/2) c=a((a1+a2+～～+a(n+1)/2)%((n+1)/2))
這個可以用反證法證明：

若存在兩個方案刪數后的方案相同，設為 A ， B （集合），

另 a1<a2< …… <am,b1<b2< …… <bm ，

若 A 中刪去元素 ai ， B 中刪去 bj ，不妨設 i<j ，顯然有 ai<bj

根據條件， j-i=(bj-ai) mod m,

所以 bj － ai ＝ j-i 或者 j-i+m

? 若 bj － ai ＝ j － i ，因為 ai+1...aj=bi...bj-1, 所以 bj-ai-1>=j-i, 所以不可能

? 若 bj － ai ＝ j － i+m,

?? 因為若 A ， B 存在，則必滿足 (m-j)+(i-1)<=(n-bj)+(ai-1)

?? 因為 n ＝ m ＋ m-1, 所以 bj-ai<=j-i+m-1, 該情況也不能

?

綜上所述，不可能存在兩個方案刪數后的方案相同。