集訓隊作業(yè)winsock3beta解題報告

1、湖南長郡中學 王俊Winsock 3 Beta解題報告問題簡述 給定的一個非負整數(shù)M，確定是否有且僅有唯一的K使得K+1.2K之間恰好有M個數(shù)的二進制表示中恰好有3個數(shù)位為1。分析該題給出雖然題目僅一句話但由M關系到K，又到K+1.2K的數(shù)，再到每個數(shù)的二進制表示法，轉了多個彎。要想直接從M來思考，感覺無法入手，沒有突破口。不妨先從最簡單的單獨的數(shù)開始分析：定義S數(shù)為二進制表示中恰有3個數(shù)位為1 的數(shù)。下表是一些正整數(shù)的二進制表示：十進制數(shù)二進制表示二進制表示中1的個數(shù)111210171113810001910012101010211101131211002131101314111031511

2、114再來看看K+1.2K中S數(shù)的個數(shù)KK1.2K中S數(shù)的個數(shù)10203041516273似乎看不出太多規(guī)律，還是來進行一定的理論分析吧！設Pn表示n的是否為S數(shù)，如果是則Pn = 1，否則Pn = 0。設Cn表示n+1 . 2n中S數(shù)的個數(shù)，即有：觀察發(fā)現(xiàn)：因為2n的二進制表示只是在n的二進制表示后多一個0，其所含1的個數(shù)和n相同，所以n和2n或者同為S數(shù)，或者均不是S數(shù)，即P2n = Pn所以 又因為 , 所以 所以當對于某個M，有唯一的K滿足條件，則必滿足即 設L為2k-1的二進制表示的位數(shù)， 即 (L3) Ai表示2k1的二進制表示中位權為2i-1的位。Bi表示2k1的二進制表示中位權

3、為2i-1的位。因為2k1為奇數(shù), 所以A1 = 1，又因為AL = 1，所以A2 . AL 1中有且僅有一個為1, 設At = 1 ()。假設， 因為2k + 1 = (2k 1) + 2, 所以 與2k+1的二進制表示中恰有3個數(shù)位為1矛盾， 所以t = 2。即 。所以 ， 即那么k+1.2k中的數(shù)可分為兩類：k+1.2k-5即 ，包含所有長度為L1的S數(shù)。因為首位必為1， 所以剩下的L2位中有2個數(shù)位為1，那么S數(shù)的個數(shù)為。2K4.2K即，這一類僅有5個數(shù)，其中只有這一個S數(shù)。 即對于M， 如果方程 有唯一一個大于3的正整數(shù)解，則滿足題目條件，否則不滿足。 因為，且為整數(shù)， 所以 , 且8m7為完全平方數(shù)。 所以當8m7為完全平方數(shù)且時滿足題目條件，即有且僅有唯一的K使得K+1.2K之間恰好有M個數(shù)的二進制表示中恰好有3個數(shù)位為1。問題得到完滿解決?？此坪翢o頭緒的題目，經(jīng)過一步步的分析，簡化，最后得到了算法即只是一個簡單的數(shù)學式子，時空復雜度均為O(1)?！绢}目來源】Petrozavodsk Summer Training Sessions 20