regional Tokyo (Japan) 2009/2010 by Puzzle

Posted on 2010-03-24 22:23 Puzzle 阅读(189) 评论(0)  编辑 收藏 引用 所属分类: 理论AC区
A.两种view,对应如果有相同的同时消去并加入一次计数,如果2个view不相同的则都加入计数。(topsky ac)

B.BFS,如果TLE则双向广搜,难点可能在于判重,试试tire树。(topsky)

C.模拟题,用一个struct{int dt,int t},开两个队列,每次比较两个队列头元素的时间,取时间小的,并将对应队列中余下的元素中时间小于头元素时间的元素取出,并将这些元素的时间修改为头元素的时间,把取出来的元素按照游完一圈所需时间排序后,进入另一个队列,为了方便还可以用一个堆,直到模拟到结束。(topsky ac)

D.经典题,有红蓝点集,问是否存在一条直线将其划分,做法先求凸包,然后判相交。(haozi)

E.模拟,维护面集和铰链集.(ac by haozi)

F.给你一个化学方程式,将他配平。最后的系数保证在int范围内,且为正整数。涉及到表达式运算,和高斯消元。由于结果要是整数。我们可以在消元的每一步都保持系数是整数,这样最后结果就是整数。具体说就是两行相消的时候乘回一个系数,再约掉最大公约数。(haozi ac by lwc)

G.想二分一个圆的半径,然后确定另外两个圆的位置,判断这两个圆是相交,还是想离。
   ps. lwc topsky帮我在网上搜几个更好的解法,我搜不到了(haozi)

H.集合DP,考虑某个状态a1, a2, .. ak考虑过了,并且标明其属性(yes / no),其他未考虑,这个状态最坏还需要问几次。转移就是在做一次提问,转移到下一个状态,边界就是当某一个状态的人数不超过1时,标明还需问0次。(haozi  ac by lwc)

I.搜索加模拟,暂没想法.(topsky)

J. bfs,用一个数字2^25*25来记录当前状态,25位压缩表示某一位上是否有'#',25表示当前'@'在哪一位上。可以先处理出和某位相邻的位置为哪些来加速,map来判重,hash效果基本相同,现在2.7s.(topsky ac)

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


posts - 3, comments - 8, trackbacks - 0, articles - 4

Copyright © Puzzle