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大学生程序设计竞赛训练》暑期课面向全球招生!

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

Posted by yuanchuanshun at 2010-08-20 10:12:04 on Problem 2481
在参考了众多的解题报告后给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.

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