2014
02-13

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://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（染色线段树基础）

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://poj.org/problem?id=2777

B，统计A到B的颜色的种数。

O，L表示线段长度，T表示颜色个数，O表示操作个数。

#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;
}

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
不知道题目例子是怎么得出来的