【线段树 + 离散化 + 详细诠释】北大 poj 2528 Mayor's posters
【线段树 + 离散化 + 详细注释】北大 poj 2528 Mayor's posters
第二次
第一次
第二次
/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/problem?id=2528 Name : 2528 Mayor's posters Date : Saturday, October 1, 2011 Time Stage : one and half an hours Result: 9378439 panyanyany 2528 Accepted 1248K 79MS C++ 3804B 2011-10-01 00:36:01 9378423 panyanyany 2528 Wrong Answer C++ 3707B 2011-10-01 00:30:47 Test Data : Review : 第二次做,还是有很多地方没有注意到的。比如 2 * n,以及递归到达叶子时没有判断 和 退出 //----------------------------------------*/ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std ; typedef __int64 LL ; int max (int lhs, int rhs) { return (lhs > rhs ? lhs : rhs) ; } int min (int lhs, int rhs) { return lhs < rhs ? lhs : rhs ; } #define MAXSIZE 10010 #define L(n) ((n) << 1) #define R(n) (((n) << 1) + 1) #define MID(a, b) (((a) + (b)) >> 1) // 此结构体用来映射新的端点值 typedef struct { bool isLeft ; // 判断此端点是否左端点 int id ; // 标记此站点是第几个端点 int val ; // 此端点的原来的值 } MAP ; // 此结构体用来做线段树的节点 typedef struct { int id ; // 海报序号,若为0则表示在[left,right]内海报的张数不确定 int left, right ; // left , right 分别代表此区间的 左,右 端点 } NODE ; int tcase, n, cnt ; bool flag[MAXSIZE] ; int left[MAXSIZE], right[MAXSIZE] ; MAP map[MAXSIZE * 2] ; NODE tree[MAXSIZE * 14] ; int cmp(MAP lhs, MAP rhs) { return lhs.val < rhs.val ; } void build (int node, int left, int right) { tree[node].id = 0 ; tree[node].left = left ; tree[node].right = right ; if (left == right) return ; int mid = MID (left, right) ; build (L(node), left, mid) ; build (R(node), mid + 1, right) ; } void update (int node, int left, int right, int NewId) { // 若张贴的海报刚好覆盖当前区间,则当前区间的 id 为该海报的 id if (tree[node].left == left && tree[node].right == right || tree[node].left == tree[node].right) { tree[node].id = NewId ; return ; } // 若海报不足以完全覆盖当前区间 // 若此区间之前已经被某海报完全覆盖 if (tree[node].id != 0) { tree[L(node)].id = tree[node].id ; // 假设左子树不被海报覆盖,则其 id 为根区间的 id tree[R(node)].id = tree[node].id ; // 假设右子树不被海报覆盖,则其 id 为根区间的 id tree[node].id = 0 ; // 因为在此区间内有两张海报,则此区间的 id 为不确定 } int mid = MID (tree[node].left, tree[node].right) ; // 若海报仅能覆盖左半区间 if (right <= mid) update (L(node), left, right, NewId) ; // 若海报仅能覆盖右半区间 else if (mid < left) update (R(node), left, right, NewId) ; // 若海报横跨本区间中部 else { update (L(node), left, mid, NewId) ; update (R(node), mid + 1, right, NewId) ; } } void count (int node) { // 若此区间恰有一张海报 if (tree[node].id) { // 若此海报未被记录 if (flag[tree[node].id] == false) { flag[tree[node].id] = true ; ++cnt ; } return ; } // 已经到达叶子,此节点仍为不确定状态,则退出 if (tree[node].left == tree[node].right) return ; // 若此区间的海报数量不确定 // 则递归查找子区间 count (L(node)) ; count (R(node)) ; } int main () { int i, j ; int t, tmp ; while (scanf ("%d", &tcase) != EOF) { while (tcase--) { scanf ("%d", &n) ; for (i = 1 ; i <= n ; ++i) { scanf ("%d%d", &left[i], &right[i]) ; map[i * 2 - 1].id = i ; map[i * 2 - 1].isLeft = true ; map[i * 2 - 1].val = left[i] ; map[i * 2].id = i ; map[i * 2].isLeft = false ; map[i * 2].val = right[i] ; } // 把端点值按从小到大排序, 注意 2 * n sort (map + 1, map + 1 + 2 * n, cmp) ; // 离散化 tmp = map[1].val ; // tmp 用来判断是否与前一个原始端点值相同 t = 1 ; // t 作为新的端点值(离散化) // 注意 2 * n for (i = 1 ; i <= 2 * n ; ++i) { if (tmp != map[i].val) { tmp = map[i].val ; ++t ; } if (map[i].isLeft == true) { left[map[i].id] = t ; } else { right[map[i].id] = t ; } } // 注意 2 * t build (1, 1, 2 * t) ; // 构造线段树 // 更新线段树 for (i = 1 ; i <= n ; ++i) update (1, left[i], right[i], i) ; memset (flag, false, sizeof (flag)) ; cnt = 0 ; count (1) ; printf ("%d\n", cnt) ; } } return 0 ; }
第一次
/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/problem?id=2528 Name : 2528 Mayor's posters Date : Monday, September 26, 2011 Time Stage : Three hours Result: 9363927 panyanyany 2528 Accepted 1252K 94MS C++ 3304B 2011-09-26 21:12:59 9363885 panyanyany 2528 Accepted 1272K 94MS C++ 3738B 2011-09-26 21:05:46 9363864 panyanyany 2528 Wrong Answer C++ 3616B 2011-09-26 21:01:08 9363854 panyanyany 2528 Wrong Answer C++ 3612B 2011-09-26 20:59:25 9363846 panyanyany 2528 Compile Error C++ 3544B 2011-09-26 20:58:31 9363671 panyanyany 2528 Time Limit Exceeded C++ 3370B 2011-09-26 20:16:14 9363662 panyanyany 2528 Runtime Error C++ 3369B 2011-09-26 20:15:02 9363631 panyanyany 2528 Runtime Error C++ 3337B 2011-09-26 20:09:37 9363613 panyanyany 2528 Runtime Error C++ 3341B 2011-09-26 20:06:49 9363610 panyanyany 2528 Runtime Error C++ 3332B 2011-09-26 20:06:02 9363604 panyanyany 2528 Runtime Error C++ 3332B 2011-09-26 20:05:09 Test Data : Review : 首先感谢几位大牛的解题报告: AC_Von,http://www.cnblogs.com/vongang/archive/2011/08/10/2133869.html kuangbin,http://www.cnblogs.com/kuangbin/archive/2011/08/15/2139931.html 思路: 这题的思想,主要是离散化,当然还有一些小技巧。 离散化,大概就是: 由于不可能开1000,0000的数组,又注意到其实际有效数据才 10000 对,在最坏的情况下,将有 2000 个不同的数据。 比如: n = 5 ; 1,200,3,5000,8999,100000, 999,9999999999 若直接以上面的数字作下标,则起码要开 9999999999 大小的数组, 显然是不可能的。 若将上面的数列排序,则: 1,3,200,999,5000,8999,100000,9999999999 根据排序的顺序,映射新的下标: 1,3,200,999,5000,8999,100000,9999999999 1,2,3, 4, 5, 6, 7, 8 则我们其实只开 8 大小的数组就可以了! 血泪史: 一开始数组开小了,无限RE, 后来用一个循环去遍历整棵树,TLE, 于是将 count() 函数的查找改为递归模式,同时修改 update() 函数,正式确定 Tree[node].sum 的作用,当为 0 时,表示当前区间的海报数量不确定, 当为正整数值时,表示当前区间只有某海报 后来VC6或者VA的复制发了神经,后面截断一大片,又CE, 重新复制后,WA, 最后一次改错,是标记重复 //----------------------------------------*/ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std ; typedef __int64 LL ; int max (int lhs, int rhs) { return (lhs > rhs ? lhs : rhs) ; } int min (int lhs, int rhs) { return lhs < rhs ? lhs : rhs ; } #define MAXSIZE 10010 #define L(n) ((n) << 1) #define R(n) (((n) << 1) + 1) typedef struct { int id ; int endVal ; bool isLeft ; } TAG ; typedef struct { int id ; int left, right ; } NODE ; bool flag[MAXSIZE * 2] ; int tcase, n, cnt ; int num[MAXSIZE][2] ; TAG tag[MAXSIZE * 2] ; NODE tree[10 * (MAXSIZE)] ; int cmp (TAG ta, TAG tb) { return ta.endVal < tb.endVal ; } void build (int node, int left, int right) { tree[node].left = left ; tree[node].right = right ; // 0 表示当前区间的海报数量不确定,正整数则表示当前区间完全被某海报覆盖 tree[node].id = 0 ; if (tree[node].left == tree[node].right) return ; int mid = (left + right) / 2 ; build (L(node), left, mid) ; build (R(node), mid + 1, right) ; } void update (int node, int left, int right, int id) { // 若新的海报可以覆盖当前区间 if (left <= tree[node].left && tree[node].right <= right) { tree[node].id = id ; return ; } /* // [left, right] 与 node 所在区间无交集 if (tree[node].right < left || right < tree[node].left) return ; */ // 若当前区间已经被海报覆盖过,且新的海报只能覆盖部分区间 if (tree[node].id > 0) { tree[L(node)].id = tree[node].id ; tree[R(node)].id = tree[node].id ; // 重新将此区间的海报数量置于不确定状态 tree[node].id = 0 ; } // [left, right] 与 node 所在区间有交集 int mid = (tree[node].left + tree[node].right) / 2 ; // [left, right] 在 node 左半区间 if (right <= mid) update (L(node), left, right, id) ; // [left, right] 在 node 右半区间 else if (mid < left) update (R(node), left, right, id) ; // [left, right] 在 node 两半都有, 即在 node 中部 else { update (L(node), left, mid, id) ; update (R(node), mid + 1, right, id) ; } return ; } void count (int node) { // 表示此区间只有一张编号为 id 的海报 if (tree[node].id > 0) { // 此海报是否已经计算过 if (flag[tree[node].id] == false) { ++cnt ; flag[tree[node].id] = true ; } return ; } // 已经到达叶子,此节点仍为不确定状态,则退出 if (tree[node].left == tree[node].right) return ; // 对于不确定的树,向左右两边搜索 count (L(node)) ; count (R(node)) ; } int main () { int i, j ; while (scanf ("%d", &tcase) != EOF) { while (tcase--) { memset (flag, 0, sizeof (flag)) ; scanf ("%d", &n) ; for (i = 1 ; i <= n ; ++i) { scanf ("%d%d", &num[i][0], &num[i][1]) ; tag[2 * i - 1].id = i ; tag[2 * i - 1].isLeft = true ; tag[2 * i - 1].endVal = num[i][0] ; tag[2 * i].id = i ; tag[2 * i].isLeft = false ; tag[2 * i].endVal = num[i][1] ; } sort (tag + 1, tag + 2 * n + 1, cmp) ; int t = 1, tmp = tag[1].endVal ; for (i = 1 ; i <= 2 * n ; ++i) { // 本来以为这一句不加也没关系,结果WA了,跳过重复的值, if (tmp != tag[i].endVal) { tmp = tag[i].endVal ; ++t ; } if (tag[i].isLeft == true) num[tag[i].id][0] = t ; else num[tag[i].id][1] = t ; } build (1, 1, 2 * n) ; for (i = 1 ; i <= n ; ++i) { update (1, num[i][0], num[i][1], i) ; } cnt = 0 ; count (1) ; printf ("%d\n", cnt) ; } } return 0 ; }