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

若存在兩個(gè)方案刪數(shù)后的方案相同，設(shè)為 A ， B （集合），

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

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

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

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

? 若 bj － ai ＝ j － i ，因?yàn)?/span> ai+1...aj=bi...bj-1, 所以 bj-ai-1>=j-i, 所以不可能

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

?? 因?yàn)槿?/span> A ， B 存在，則必滿足 (m-j)+(i-1)<=(n-bj)+(ai-1)

?? 因?yàn)?/span> n ＝ m ＋ m-1, 所以 bj-ai<=j-i+m-1, 該情況也不能

?

綜上所述，不可能存在兩個(gè)方案刪數(shù)后的方案相同。