SGOI13之《小行星之谜》解题报告
   
题目大意:
  本题主要是对一个固定区域内的行星数目进行统计和更新。

算法分析:
  如果用数组直接记录每一个区域的行星个数,在查询时需要O(n^3)的时间,速度较慢,所以可以采用树状数组来记录小行星的个数。这样只需要O((lg n)^3)的时间。大大提高了算法的效率。
根据题意还必须记录下每个返回的信息,以便纠错时使用。对于电话号码如果采用一个0..9999999的树组记录则浪费了很多的空间;如果依次记录每个电话号码,在查找时将浪费许多的时间。所以最好采用搜索树来存储每一个电话。

数据分析:
  本题共有十个测试数据,分值从5~15不等,最大的数据有50万行命令。每个数据的询问,更新和纠错的个数比不尽相同,可以从多方面测试选手的程序。

参考程序:

  
  
  
  
  
        
      
    
    
 

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有