The Sun Also Rises

Algorithm, Mathematica, 计算机科学, C++, photography, GNU/Linux的讨论空间

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks

比较不错的一套题,很多题挺有意思的~

Strange Billboard

经典思路了,枚举第一行的使用方法(2^16),然后推后面的方案。

Cell Phone
以每个点为圆心,r为半径画圆,问题转化为求被覆盖次数最多的区域次数。可以在每个圆上将相交的圆弧求出来,排序扫描,复杂度O(n^2logn)
CEOI06 Antenna有一种解法就是二分半径然后用这个方法来求最多能覆盖多少个点。
CODE


Hexagonal Parcels
Euclid空间上的Steiner树有一个性质就是n个点,增加的点不超过n-2个。然后这道题有点Steiner树的感觉,然后我们就猜增加的点至多2个,求最小生成树。。。然后就对了。不会严密证明。
标程的另一种做法是基于状态压缩的DP好像,没看懂。。。

Key Task
简单的BFS题。

Gates of Logic
很麻烦的处理题,暂时没做。

Weird Numbers
负进制转换。用类似于正进制的方法做,每次保证余数在[0,b)范围内即可。
证明如下:
设我们要转-b进制,先得到b进制表达式
N = an*b^n + an-1 * b^(n-1) + ... + a0*b^0
注意到p为偶数时,ap*b^p = ap * (-b)^p
p为奇数时,ap*b^p = 1*(-b)^(p+1) + (b - ap) * (-b)^p
~~~

Rectangular Polygon
由于Polygon的特殊性,我们拉一条平行于x或y轴的直线,则上面一定经过偶数个顶点,并且连边一定是0-1, 2-3……
这样可以construct出边来,判断方向可以使用有向面积(即按照当前方向走一遍算面积,根据面积的正负号来判断是否需要reverse)
参见SGU 128, Snake

Reaux! Sham! Beaux!
简单题

Robotic Sort
需要支持定位某个数和将某一段reverse两种操作,可以使用分块处理或者splay_tree。
因为是按照从小到大的顺序把数依次归位的,所以我们可以理解为每次将这个数归位后就把这个数删掉,每次就是reverse从头开始的一段,这样可以减少常数 & 编程复杂度。
用splay_tree的主要想法就是利用树的中序遍历来表示序列。利用SplayTree的spaly操作,设当前要归位的元素为x,把x splay到根,标记根左边节点为reverse,并删除根。
SplayTree的节点需要维护cnt和rev域。在遍历树的时候需要应用父节点的rev状态(类似于线段树的处理方法)
CODE


Tough Water Level
重心关于含水量的高度是一个单峰函数(感觉比较像~),因此可以三分。
注意到由于厚度和宽度的函数是一个指定的函数,需要数值积分和表达式求值。
写起来还是有点麻烦的~



posted on 2008-01-28 15:49 FreePeter 阅读(1188) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Creative Commons License
This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用创作共用版权协议, 要求署名、相同方式共享. 转载本站内容必须也遵循“署名-相同方式共享”的创作共用协议. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.