首页 > ACM题库 > HDU-杭电 > hdu 2681 MM Programming Club-线段树-[解题报告]C++
2014
02-13

hdu 2681 MM Programming Club-线段树-[解题报告]C++

MM Programming Club

问题描述 :

ACM is popular in HDU. Many girls want to learn more about programming skills in ACM. As one of assistances of Lcy, Yifenfei is now busy preparing a new club called “MM Programming Club”. Of Course, He will be the leader of the club, and teach these girls patiently. After the news posted around the campus, as many as N girls are determined to take part in the club. However, the numbers of members are limited; Yifenfei will only select K of them. It is quite a difficult problem. Here is a list of all information about N girls. Each of them has intelligence value and prettiness value. He also wants these K members such that the difference of intelligence between any two of them must not be greater than MAXK (If K = 1, the difference is zero). Now he wants to maximize the Sum of these K girls’ prettiness value.

输入:

Many test case, please process to end of file. Each test first contains three integers N(1 <= N <= 200), K(1 <= K <= N), MAXK(1 <= MAXK <= 500). Then N lines follow. Each line contains two integers S, T (1 <= S, T <= 500). S represents the intelligence value, and T represents the prettiness value.

输出:

Many test case, please process to end of file. Each test first contains three integers N(1 <= N <= 200), K(1 <= K <= N), MAXK(1 <= MAXK <= 500). Then N lines follow. Each line contains two integers S, T (1 <= S, T <= 500). S represents the intelligence value, and T represents the prettiness value.

样例输入:

2 1 0
1 2
2 3
2 2 0
1 2
2 3
2 2 1
1 2
2 3

样例输出:

3
-1
5

  • HOJ 2037/POJ
    2528 Mayor’s posters(线段树+离散化)



传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2037

http://poj.org/problem?id=2528

题意:市长选举,候选人在墙上贴海报,互相可能覆盖,问最后能看到几张海报?

输入:每张海报覆盖的区域。

输出:最后能看到几张海报。

思路:还是一个线段树+离散化的应用,注意一下线段树的范围和题目中描述的范围不太一样。

程序

#include
<cstdio>

#include
<algorithm>

using
namespace
std;

const
int
MAX = 10240;

class
Line {
public:
    int l, r, indexl, indexr;
    void set(int a, int b) {
       
l = a, r = b;
    }
    void hash(int* a, int n) {
       
indexl = lower_bound(a, a + n, l) - a;
       
indexr = lower_bound(a, a + n, r) - a;
    }
};

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
    int cover;
    void update() {
       
if
(cover > 0) {
           
coverLen = r - l;
       
} else if (l + 1 == r) {
           
coverLen = 0;
       
} else {
           
coverLen = left->coverLen + right->coverLen;
       
}
    }
public:
    double coverLen;
    LineTree(int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != r) {
           
int
mm = (ll + rr) / 2;
           
left = new LineTree(ll, mm);
           
right = new LineTree(mm, rr);
       
} else {
           
left = NULL, right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
cover = 0, coverLen = 0;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void insert(int ll, int rr) {
       
if
(ll <= l &&
r <= rr) {
           
cover++;
       
} else {
           
int
mid = (l + r) / 2;
           
if
(ll < mid) {
               
left->insert(ll, rr);
           
}
           
if
(rr > mid) {
               
right->insert(ll, rr);
           
}
       
}
       
update();
    }
};

Line line[MAX];

int
main() {
    int x[2 * MAX], total, n;
    scanf(“%d”, &total);
    while (total) {
       
scanf(“%d”, &n);
       
LineTree tree(0, 2 * n + 1);
       
tree.init();
       
for
(int
i = 0; i < n; i++) {
           
scanf(“%d %d”, &x[2 * i], &x[2 * i + 1]);
           
line[i].set(x[2 * i], x[2 * i + 1]);
       
}
       
sort(x, x + 2 * n);
       
int
ans = 0;
       
for
(int
i = n - 1; i >= 0; i) {
           
line[i].hash(x, 2 * n);
           
int
len = tree.coverLen;
           
tree.insert(line[i].indexl, line[i].indexr + 1);
           
if
(len != tree.coverLen) {
               
ans++;
           
}
       
}
       
printf(“%d\n, ans);
    }
    return 0;
}

  • HOJ 2681
    Magic-Pen1(染色线段树基础)



传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2681

题意:初始颜色为白色,将任意一段染成黑色或者白色,求出最后纸袋上白色的段数。

输入:X Y X将x –
y段染成X颜色,X为1染成黑色,X为0染成白色。

输出:白色的段数。

思路:注意染色更新的时间。

程序

#include
<cstdio>

const
int
WHITE = 1;
const
int
BLACK = 2;
const
int
MIXED = 3;

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
public:
    int color, len;
    LineTree (int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != rr) {
           
int
mm = (ll + rr) >>
1;
           
left = new LineTree(ll, mm);
           
right = new LineTree(mm, rr);
       
} else {
           
left = NULL;
           
right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
color = WHITE, len = r - l;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void update(int ll, int rr, int cc) {
       
if
(ll <= l &&
r <= rr) {
           
color = cc;
       
} else {
           
if
(color != MIXED) {
               
left->color = color;
               
right->color = color;
               
if
(color == WHITE) {
                   
left->len = left->r - left->l;
                   
right->len = right->r - right->l;
               
} else {
                   
left->len = right->len = 0;
               
}
           
}
           
int
mm = (l + r) >>
1;
           
if
(ll < mm) {
               
left->update(ll, rr, cc);
           
}
           
if
(rr > mm) {
               
right->update(ll, rr, cc);
           
}
           
color = left->color | right->color;
       
}
       
if
(color == WHITE) {
           
len = r - l;
       
} else if (color == BLACK) {
           
len = 0;
       
} else if (color == MIXED) {
           
len = left->len + right->len;
       
}
    }
};

void
swap(int &x, int &y) {
    if (x > y) {
       
x ^= y, y ^= x, x ^= y;
    }
}

int
main() {
    int n, m;
    while (scanf(“%d %d”, &n, &m) == 2) {
       
LineTree tree(0, n);
       
tree.init();
       
while
(m) {
           
int
x, y, c;
           
scanf(“%d %d %d”, &x, &y, &c);
           
swap(x, y);
           
if
(c == 0) {
               
tree.update(x - 1, y, WHITE);
           
} else if (c == 1) {
               
tree.update(x - 1, y, BLACK);
           
}
       
}
       
printf(“%d\n, tree.len);
    }
    return 0;
}

HOJ 2685/POJ 2777 Count Color(染色线段树经典)

传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2685

http://poj.org/problem?id=2777

题意:染色问题C A B C,将A到B段染成颜色C,P A
B,统计A到B的颜色的种数。

输入:L T
O,L表示线段长度,T表示颜色个数,O表示操作个数。

输出:对每次查询输出结果。

思路:因为T最大为30,这样每一段可以用一个整数的低30位表示是否存在颜色,统计这个整数中为1的个数就是这段中颜色的个数。

程序

#include
<cstdio>

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
    bool OnlyOne(int x) { return !(x & (x - 1)); }
public:
    int color;
    LineTree(int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != rr) {
           
int
mid = (ll + rr) / 2;
           
left = new LineTree(ll, mid);
           
right = new LineTree(mid, rr);
       
} else {
           
left = NULL;
           
right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
color = 1;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void update(int ll, int rr, int cc) {
       
if
(ll <= l &&
r <= rr) {
           
color = cc;
           
return;
       
}
       
if
(OnlyOne(color)) {
           
left->color = color;
           
right->color = color;
       
}
       
int
mid = (l + r) / 2;
       
if
(ll < mid) {
           
left->update(ll, rr, cc);
       
}
       
if
(rr > mid) {
           
right->update(ll, rr, cc);
       
}
       
color = left->color | right->color;
    }
    void query(int ll, int rr, int &ans) {
       
if
((ll <= l &&
r <= rr) || OnlyOne(color)) {
           
ans |= color;
           
return;
       
}
       
int
mid = (l + r) / 2;
       
if
(ll < mid) {
           
left->query(ll, rr, ans);
       
}
       
if
(rr > mid) {
           
right->query(ll, rr, ans);
       
}
    }
};

void
swap(int &x, int &y) {
    if (x > y) {
       
x ^= y, y ^= x, x ^= y;
    }
}

int
main() {
    int n, t, o;
    while (scanf(“%d %d %d”, &n, &t, &o) == 3) {
       
LineTree tree(0, n);
       
tree.init();
       
for
(int
i = 0; i < o; i++) {
           
getchar();
           
char
op;
           
scanf(“%c”, &op);
           
if
(op == ‘C’) {
               
int
a, b, c;
               
scanf(“%d %d %d”, &a, &b, &c);
               
swap(a, b);
               
tree.update(a - 1, b, 1 <<
(c - 1));
           
} else if (op == ‘P’) {
               
int
a, b;
               
scanf(“%d %d”, &a, &b);
               
swap(a, b);
               
int
ans = 0, cnt = 0;
               
tree.query(a - 1, b, ans);
               
while
(ans) {
                   
if
(ans % 2) {
                       
cnt++;
                   
}
                   
ans >>=
1;
               
}
               
printf(“%d\n, cnt);
           
}
       
}
    }
    return 0;
}

 


解题转自:http://blog.sina.com.cn/s/blog_65f3869301011fnk.html


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的