Posted on 2009-02-12 22:34
hello_world 閱讀(1203)
評(píng)論(0) 編輯 收藏 引用
| 題目分類(lèi) |
| No Tipping |
二進(jìn)制表示狀態(tài)，DFS |
|
|
| Sumsets |
查找，搜索 |
| Zipf's Law |
字符串處理
|
| Ones |
簡(jiǎn)單題 |
No Tipping:
題目要求把一個(gè)有兩個(gè)支點(diǎn)的杠桿上的重物拿掉，使得杠桿始終保持平衡，然后輸出某個(gè)可行的順序。顯然，狀態(tài)的表示和物體拿走的順序有關(guān)，此題從正面入手，狀態(tài)表示比較困難。其實(shí)可以換個(gè)角度看，就是在一塊空的杠桿上，依次放上重物，杠桿要始終保持平衡，這個(gè)順序就是拿走的順序。用二進(jìn)制可以方便的表示狀態(tài)，如果（s|1<<i）這個(gè)狀態(tài)可行，就說(shuō)明在s的狀態(tài)下，放上物體i不會(huì)使杠桿傾斜。判斷是否平衡的條件，要用到物理知識(shí)，力矩=力避 x 力， 重心的坐標(biāo)，也可以通過(guò)(力矩/重力)求出。只要重心坐標(biāo)在兩個(gè)支點(diǎn)之間就能保持平衡。
Sumsets：
題目要求求出給定集合中最大的一個(gè)數(shù)，這個(gè)數(shù)要滿足是集合中其他三個(gè)數(shù)的和，即求 a+b+c=d ！
我的做法：先對(duì)集合排序，暴力算出集合中任意兩個(gè)數(shù)的和即a+b，然后對(duì)和排序，對(duì)集合中的數(shù)從大到小枚舉d，看是否存在c，使d-c在和的集合中！因?yàn)楹偷募鲜怯行虻?，所以可以二分查找，同時(shí)注意這四個(gè)數(shù)不能相同就可以了！
Zipf's Law：
字符串處理，按照題目意思做就好了，使用string會(huì)很方便，處理全部的單詞，然后排序處理~
Ones：
從1開(kāi)始不斷的模n，然后對(duì)結(jié)果*10+1，循環(huán)直到為0即可~