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