M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

【第一场选拔赛解题报告】

今天做的还可以,当然,对我来说。唯一的缺点是别人当水题做的D我没做出来。简单的BFS,我愣是不会。哎,还是要把基础打好啊。最后A掉3道,还有一道线段树的没有过,过些时间补上。我该抓紧时间复习了...

A - River Pollution   

          线段树,求面积的并,很基础的线段树+离散化+扫描线,但我就是不会~

B - Middle number  
   
         今天这个是第一个过的,如果这个不过我相信后边会更加艰难。给定一个数的序列,然后不断的插入数字并保持递增,最后询问中间的数是多少。如果
数的个数是偶数,输出中间两个中小的。数据很大,时间是5s,我冒了个险,第一次先排序,每次二分找到要插入的位置,然后顺序修改后边的序列,过了!
二分的效率啊!!我看到后边这个题无数人TLE到死。。。这个题给了我很大信心,不然。。。
现在知道了,正解是用两个堆,一个大顶堆,一个小顶堆,大顶堆只能和小顶堆元素个数相同或者正好多一个。开始时将小的一般给大顶堆,大的一半给小顶堆,插入时和堆顶元素比一下,若大于大顶堆的堆顶元素,则插给小堆,否则给了大堆。询问时只需输出大堆的堆顶元素就可以了。
C - Game of Stones 

         JL出的题,乍一看很难,但是后来才知道简单的要命:两个人A和B玩游戏,有两堆石子M和N,每次两个人都至少从两堆中任意一堆拿至少一个石子,直到两堆石子都为空最后一个拿的人WIN。,A总是第一个拿,给定M和N,问A能否获胜。( 0 < M , N < 10^50 )
         答案:如果M==N,A输,否则,A赢。我考虑到奇偶上了,结果WA了5次,哎。。。

D - The longest athletic track  

         给定N个点,和一棵生成树(N-1条边),最后问最长的一条路是多少。

                                                                     
            上图的答案是80。
            求树的直径,两次BFS,第一次任选起点,则终点一定是直径的一个端点。然后再来一次BFS就可以了。

E - Buy Car         
    
           Brent喜欢骑摩托,现在有N个城市,Brent 想把所有城市逛一遍,但是他怕油不够。每升油可以跑10km,他可以在任何一个城市加油。给出M条边,
最后问Brent的摩托的容量最小是多少,如果不能逛完所有城市,输出-1。

           简单的最小生成树(正是Brent讲座讲的~),找出最小生成树最小的一条边长度为A。如果A%10==0,答案是A/10;否则答案是A/10+1;

最后排名大概是10名?(除去老队员和admin大概是7,8名的样子),问题应该不大了。嘻嘻,加油吧~ 可恶的BFS。。。一定搞定它。

posted on 2010-05-16 22:37 M.J 阅读(135) 评论(0)  编辑 收藏 引用


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