小天和小真得到了一個用來顯示數字的顯示器,內部是用位元運算實作的,有很多個0、1開關排成一排可以表示成一個由0和1組成的字串,這個字串會被當成二進制的數字用內部的轉換器轉成十進制後輸出並顯示。
小天是一個很好勝的人,他在小真還在研究顯示器時就偷偷找到了很多個顯示器的輔助工具──加速器,這些加速器內部是已經固定好的01字串,可以接在顯示器後方,進而把加速器字串為1的位置加速,而且每個加速器都有自己的加速效率。但嚴格的是,當多個加速器接在一起,只要任意一個加速器的a位置不是1,那麼整個連接起來的產物就無法對a位置加速。(換句話說,所有的加速器與欲顯示的X做and的邏輯運算後,如果是X,就可以對X加速。)
此時小天才發現,加速器的存在就是為了補齊顯示器的不足,因為把開關調整好後傳達訊息給轉換器的速度太慢了!於是好勝的小天試著組裝起這些加速器,他想在小真按出一個數字K的同時,想辦法用最快的速度按出不低於K的任意一個數字(也就是說,加速器加速的位置只要剛好能夠加速到任意一個小天想按出的數字的所有位置就好)。
請你撰寫一個程式,幫小天計算出他能夠組合出的最大效率總和,保證有解。
再更簡單的說法,給你一堆物品,物品有權重和效率,選取多個物品的權重是把這些物品的權重做位元運算and之後的數字,問當權重≥K時,可以湊出的最大效率總和。
為了表示方便,我們把每個加速器的01字串直接轉換成一個非負整數。
每筆測試資料的首行會有兩個正整數N,K以空格隔開。代表小天現在有N個加速器可以使用,且小真按出了數字K。接下來有N行,每行會有兩個正整數,第一個數字Ai代表簡化加速器的01字串過後的非負整數,第二個數字Bi代表加速器的效率。
在組合起來能夠顯示≥K任一數字的情況下,輸出加速器組合的最大效率總和。
注意,加速器是不可以翻轉的。
4 14 15 9 11 100 16 20 24 7
27
本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N≤22,Ai,Bi,K<230,全部解出可獲13分;
第二子題的測試資料 N≤1000,Bi<230,Ai,K<210,全部解出可獲37分;
第三子題的測試資料 N≤5×105,Ai,Bi,K<230,全部解出可獲50分。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|