Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:终于A了,下面写个大总结

Posted by hncsyjc at 2013-06-04 12:24:01 on Problem 2481
In Reply To:终于A了,下面写个大总结 Posted by:yuanchuanshun at 2010-08-20 10:12:04
> 在参考了众多的解题报告后给A了,联系pku2352,把这题的一维转化为二维坐标,s当作x,e当作y,那么就求在其左上方的顶点个数了,y按降序排插入树状数组,若相同则按x的升序排;这是很重要的,插入后,因为y已经是降序了,所以只需处理x了,用一维的树状数组c[i]来处理。你把2352做会了,这题就简单了,可有个问题开始错了,有下面这组强的数据:
> 
> 9
> 5 5
> 5 6
> 1 4
> 4 5
> 1 4
> 4 6
> 2 3
> 3 5
> 1 4
> 
> 正解4 1 0 2 0 0 3 0 0
> 错解4 1 0 2 1 0 3 0 2
> 为什么会这样呢因为有三个坐标相同,那么后两个计算的时候就会错了,不信你对比数据刚好是(1,4)坐标错误。
> 那么就解决这个问题,开始写了:
> t1=Getsum(a[i].s),t2=Getsum(a[i].s-1);
> if((t1-t2)!=0)  b[a[i].id]=t2;
> else  b[a[i].id]=t1;
> modify(a[i].s);
> 又错了,那么正确的写法是与前面的比较,为什么可以呢,因为我之前已经排序好了,只有临近的才可能相等的。
> P.S. 输入数据全部+1.
其实我的错解是:4 1 1 2 2 0 3 0 0


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator