2528?2528号试题?d2528?Mayors posters

你是否正在寻找关于2528的内容？让我把最完整的东西奉献给你：

转载请注明出处：優YoU

大致题意：

有一面墙，被等分为1QW份，一份的宽度为一个单位宽度。现在往墙上贴N张海报，每张海报的宽度是任意的，但是必定是单位宽度的整数倍，且<=1QW。后贴的海报若与先贴的海报有交集，后贴的海报必定会全部或局部覆盖先贴的海报。现在给出每张海报所贴的位置（左端位置和右端位置），问张贴完N张海报后，还能看见多少张海报？（PS：看见一部分也算看到，。）

解题思路：

水题，区间压缩映射（离散化） 线段树

首先建立模型：

给定一条数轴，长度为1QW，然后在数轴上的某些区间染色，第i次对区间染色为i，共染色N次。给出每次染色的区间，问最后能看见多少种颜色。

常规思路：

若第i次在区间[ai , bi]染色，则把[ai , bi]的每一都染色为i。后染的颜色覆盖先染的颜色。由于染色N次，定义一个标记数组tagcol，从数轴第一开始检查，一直检查到最后，出现过得颜色则记录到tagcol，最后统计tagcol中不同颜色的个数，就是所求。

数据规模太大，必定TLE。

应该用线段树去求解，这题只是线段树的入门水题，不懂线段树的同学去找一些相关资料大概学习一下，然后看一下我代码中注释，这题就有思路做了。我推荐你们去看看“浙江大学acm校队”的关于线段树的PPT，里面有线段树从入门到精通的案例，也有涉及离散化的介绍，百度搜就有了。

然后我这里补充几点线段树的知识，网上关于线段树的资料很多有误导。

1、 线段树是二叉树，且必定是平衡二叉树，但不一定是完全二叉树。

2、 对于区间[a,b]，令mid=(ab)/2，则其左子树为[a,mid]，右子树为[mid1,b]，当a==b时，该区间为线段树的叶子，无需继续往下划分。

3、 线段树虽然不是完全二叉树，但是可以用完全二叉树的方式去构造并存储它，只是最后一层可能存在某些叶子与叶子之间出现“空叶子”，这个无需理会，同样给空叶子按顺序编号，在遍历线段树时当判断到a==b时就认为到了叶子，“空叶子”永远也不会遍历到。

4、 之所以要用完全二叉树的方式去存储线段树，是为了提高在插入线段和搜索时的效率。用p*2，p*21的索引方式检索p的左右子树要比指针快得多。

5、线段树的精髓是，能不往下搜索，就不要往下搜索，尽可能利用子树的根的信息去获取整棵子树的信息。如果在插入线段或检索特征时，每次都非要搜索到叶子，还不如直接建一棵普通树更来得方便。

但是这题单纯用线段树去求解一样不会AC，原因是建立一棵[1,1QW]的线段树，其根系是非常庞大的，TLE和MLE是铁定的了。所以必须离散化。

通俗点说，离散化就是压缩区间，使原有的长区间映射到新的短区间，但是区间压缩前后的覆盖关系不变。举个例子：

有一条1到10的数轴（长度为9），给定4个区间[2,4] [3,6] [8,10] [6,9]，覆盖关系就是后者覆盖前者，每个区间染色依次为 1 2 3 4。

现在我们抽取这4个区间的8个端点，2 4 3 6 8 10 6 9

然后删除相同的端点，这里相同的端点为6，则剩下2 4 3 6 8 10 9

对其升序排序，得2 3 4 6 8 9 10

然后建立映射

2 3 4 6 8 9 10

↓ ↓ ↓ ↓ ↓ ↓ ↓

1 2 3 4 5 6 7

那么新的4个区间为 [1,3] [2,4] [5,7] [4,6]，覆盖关系没有被改变。新数轴为1到7，即原数轴的长度从9压缩到6，显然构造[1,7]的线段树比构造[1,10]的线段树更省空间，搜索也更快，但是求解的结果却是一致的。

离散化时有一点必须要注意的，就是必须先剔除相同端点后再排序，这样可以减少参与排序元素的个数，节省时间。

附：海报张数上限为10000，即其端点映射的新数轴长度最多为20000。因此建立长度为1QW的离散数组dis时，可以使用unsigned short类型，其映射最多为20000，这样可以节约空间开销。

Source修正

Alberta Collegiate Programming Contest 2003.10.18

~acpc/2003/

Problem G

//Memory Time //21276K 547MS #include

以上就是关于2528的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/dianqi/article-13530-1.html