Posted on 2009-02-12 22:34
hello_world 阅读(1172)
评论(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即可~