成都東軟學院新生周賽(五)

---

感受

這次比賽打的非常艱辛，全程1.20小時的時間全在寫A題，而且還沒有寫出來。還是自己太菜了。比賽過程中根本就沒有想到用位運算去寫著三個題。

考點

位運算:位運算是二進制下的運算,運算速度最快,運算級別最低.

名稱且或異或取反左移右移

C符號	&	|	^	~	<<	>>
規則	兩個二進制為都為1,則二進制位的結果為1,否則為0.	兩個二進制位只要有一個為1,則二進制位的結果為1	若兩個二進制位的值相同為0,不同為1	對二進制數按位取反,將0變1	將一個數的二進制數全部左移N位,右補0	將一個數的二進制數全部右移N位,移到右端的低位被舍棄,對于無符號數,高位補0

• C語言中數都是以補碼的形式存在的,所以取反的時候要注意這一點(正負數的考慮).

A:找出數組中唯一只出現過一次的數，別個數都出現兩次。

在做這個題的時候，根本就沒有想到位運算，所以我就把我能用的方法都試了一下，map，排序，暴力。發現都不行。賽后問他們發現這題太水了，一個異或就可以解決的事情。

我們知道異或可以理解為不進位的加法(兩個數相加最高位不會改變).但這題關鍵和不進位沒有關系.我們可以發現兩個相同的數互相異或的值為0,我們是不是可以把數組中的每個數都異或一次,最后的結果就是我們要的到的數.

B:找出數組中兩個只出現過一次的數，別個數都出現兩次

這個題和上個題很像,是異或的進擊版.還是和上面一樣,但是這次我們的出來的值ans = a^b.顯然我們要在這里面得出答案.最后的答案肯定不是0,根據異或的定義,可以知道兩個數二進制位不同為1,我們把這一位找出來輔助為flag,然后運用位運算且,循環遍歷整個數組,把每個數與flag比較,如果為真,則用a異或,否則用b異或,這樣就可以把兩個數獨立出來.

C:找出數組中唯一只出現過一次的數，別個數都出現三次(數組大小為3*N+1)

這個題就不好直接的用異或,但是可以借用上面的思想,由于不知道數據的大小,就當成64位的long long來算,我們開始一個大小為65的數組,我們用這個數組來模擬二進制.

將每個數都轉換成二進制,并存入數組中,最后我們就得到所有數的二進制情況.我們只需要遍歷這個數組,把每一位對3取余,如果不為0,則把這一位轉換成10進制存入ans中.

感想

昨天晚上看到題解補完題后,只能說這次不應該報零.還是自己的實力不夠,有人AK,有人報零.最近狀態一直不在,是要找個時間好好的調整一下了.

總結

以上是生活随笔為你收集整理的成都东软学院新生周赛(五)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。