|
二 23
这是NOI计划的第二份题解。NOI1998的6道题是[个人所得税][免费馅饼][围巾裁剪][SERNET模拟][软件安装盘][并行计算]，相对于NOI1997要稍难一些，不过还都是可以接受的。 [个人所得税]是一个简单题，[免费馅饼][围巾裁剪]是基本的动态规划问题，难度都还算容易。[SERNET模拟]涉及到了图论的最短路算法构造，需要稍稍思考。[软件安装盘]是一个比较困难的搜索题，目前还没有较好的方法。[并行计算]用了随机+贪心的方法，细节非常多，构造也不是很容易。 做这些题花了我8天时间，主要原因是在[并行计算]上浪费了过多的时间，接下来要掌握节奏。 十二 06
很明显，这个题是求连通块的个数。关键在于正确判断两个矩形相交。 我们知道，在一维的数轴上，两个区间[a,b] [c,d] (a<=b)，这两个区间相交的充分必要条件是c<=b。对于题中所述的边平行于坐标轴的矩形，我们需要分别判断x轴方向和y轴方向都相交，那么这个矩形一定相交。 假设我们对于给定的两个矩形A，B，A矩形的左下点坐标为(A.x1,A.y1)，右上点坐标(A.x2,A.y2)，同理B点，判断这两个矩形相交，要分为以下四种情况
根据以上四种情况分类讨论，可以判断A和B是否相交。但是以上方法会造成一个遗漏，就是按题意如果两个矩形只有一个公共点，不能算作相交。对于这种特殊判断，需要排除只有一个交点的状态。
根据以上方法，我们就可以判断每对矩形是否相交了。接下来要求出所有的连通块，由于N多达7000，一般的O(N^2)的广搜会超时，需要用并查集求连通块。 初始时把每个矩形作为单独的一个集合，如果两个矩形相交，合并这两个矩形所属的集合，最后统计剩余的集合数，就是连通块的个数。这样时间复杂度虽然还近似是O(N^2)，但是会减少搜索时许多无用的操作，所以可以解决问题。 十二 04
从描述中看出，非前缀且权值和最小，于是我想到了哈夫曼编码。类似的，对于这道题，我们可以考虑建立一个k叉树，这个树的每个叶节点代表一个字符串，只须找出最小的n个叶节点的权值，就是结果。 首先建立一个0节点，在此基础上首先加入每个单个字母，当叶节点的个数不足n个时，取出最小的一个节点，对这个节点进行扩展，即把它的权值分别加上每个字母的权值，作为新的k个叶节点。否则把前n小的节点取出，计算它们的权值之和。如果这个和小于当前已知最优解，更新最优解，否则结束，因为再扩展一定不会比当前值小。 实际上我们并不需要建立树结构，只需要对叶节点的权值抽象的维护。首先把每个字母的权值插入优先队列，每次取出前n小的值计算，并以最小值来维护。 一般情况下我们用最小堆实现优先队列，但是堆中可能会存在n^2个元素，大大超过了空间限制。但是优先队列中只有前n小的元素是对我们有用的，我们可以以此改进堆，只存储前n小的元素。当插入一个新的元素时，把堆中的最大值删除，这样维护的一定是前n小的。这样又会带来新的问题，在最小堆中取最大值是O(n)时间复杂度的。于是必须同时维护一个最大堆，使取删最大值变为O(logn)。需要同时维护两个堆，在每个元素之间建立映射关系，每次删除都要对两个堆进行维护。 这样虽然可以解决问题，但是会大大增加编程的复杂度，可以考虑不用堆来维护。我用了更强大的数据结构，平衡树。平衡树在插入、取最大、取最小、删除上均有O(logn)的时间复杂度，使用平衡树可以使编程思路更清晰。我用的是Treap。 以下是我用Treap实现的代码。 十二 03
这道题的解决方法隐藏得很深，不经过严密的数学推理分析是很难想到正确方法的。 注意到题上的一个看似无关紧要的条件，“不包括三角形”，这是一个突破口。由这个条件，我们可以证明，如果一个图不存在度数为1的顶点，B永远也追不上A。也就是B想追上A，必须让A“走投无路”。 于是我们首先把原图处理一下，求出对于A来说的安全区。对于A来说的安全区，也就是一个没有度为1的顶点的最大子图。我们把这个安全区求出，并标记上。 A要想不被B抓住，则一定要向安全区中逃跑。如果A能够在B追上A之前逃离到安全区，则B就永远也追不上A。否则，A无论如何也会被B追上。在A“必死无疑”的时候，A要想尽可能晚的被B追上，就必须想远离B的方向跑。 有了以上的分析，得出下列算法 时间复杂度：O(M+N)
21 queries. 0.542 seconds.
Designed by NattyWP .
Images by desEXign.
|
Recent Comments