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