|
|
转自: http://www.cppblog.com/Icyflame/
一、定义与定理
LCA：Least Common Ancestors（最近公共祖先），对于一棵有根树T的任意两个节点u，v，求出LCA(T, u, v)，即离跟最远的节点x，使得x同时是u和v的祖先。
在线算法：用比较长的时间做预处理，但是等信息充足以后每次回答询问只需要用比较少的时间。
离线算法：先把所有的询问读入，然后一起把所有询问回答完成。
RMQ：给出一个数组A，回答询问RMQ(A, i, j)，即A[i...j]之间的最值的下标。
二、DFS+RMQ
1）Sparse Table（ST）算法
描述：
1 //初始化
2 INIT_RMQ
3 //max[i][j]中存的是重j开始的i个数据中的最大值，最小值类似，num中存有数组的值
4 for i : 1 to n
5 max[0][i] = num[i]
6 for i : 1 to log(n)/log(2)
7 for j : 1 to n
8 max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
9 //查询
10 RMQ(i, j)
11 k = log(j-i+1) / log(2)
12 return MAX(max[k][i], max[k][j-2^k+1])
分析：初始化过程实际上是一个动态规划的思想。易知，初始化过程效率是O(nlogn)，而查询过程效率是O(1)。ST是一个在线算法。
示例：POJ 3368 解题报告
2）求解LCA问题
描述：
（1）DFS：从树T的根开始，进行深度优先遍历，并记录下每次到达的顶点。第一个的结点是root(T)，每经过一条边都记录它的端点。由于每条边恰好经过2次，因此一共记录了2n-1个结点，用E[1, ... , 2n-1]来表示。
（2）计算R：用R[i]表示E数组中第一个值为i的元素下标，即如果R[u] < R[v]时，DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代，但深度最小的还是u与v的公共祖先。
（3）RMQ：当R[u] ≥ R[v]时，LCA[T, u, v] = RMQ(L, R[v], R[u])；否则LCA[T, u, v] = RMQ(L, R[u], R[v])，计算RMQ。
由于RMQ中使用的ST算法是在线算法，所以这个算法也是在线算法。
示例：ZOJ 3195 解题报告。
三、Tarjan算法
描述：Tarjan算法是一个离线算法，也就是说只有先获得所有的查询，再按一个特定的顺序进行运算。
1 //parent为并查集，FIND为并查集的查找操作
2 Tarjan(u)
3 visit[u] = true
4 for each (u, v) in QUERY
5 if visit[v]
6 ans(u, v) = FIND(v)
7 for each (u, v) in TREE
8 if !visit[v]
9 Tarjan(v)
10 parent[v] = u
示例：HDOJ 2586 解题报告。
思路： 每次新增点a -> b的时候，union (b, a)，节点中保存的是距离的偏移量。 查询a, b的关系的时候，如果a, b不是一类，就输出-1，如果是的话，就将a，b的偏移量相加然后输出。
 #include <stdio.h>
  struct node  {
 int a, b;
struct node *next;
 };
struct node nodes[10032];
struct {
int from, to, len;
char dir;
struct node *query;
} arr[40032];
struct {
int parent, x, y;
} set[400032];
int N, M;
__inline int abs(int i)
{
return i > 0 ? i : -i;
}
int set_find(int i)
{
int r, p;
p = set[i].parent;
if (!p)
return i;
r = set_find(p);
set[i].x += set[p].x;
set[i].y += set[p].y;
set[i].parent = r;
return r;
}
void set_union(int from, int to, int x, int y)
{
int r = set_find(to);
set[r].parent = from;
set[r].x = x - set[to].x;
set[r].y = y - set[to].y;
}
int main()
{
int i, j, k, ia, ib, x, y;
char str[16];
struct node *t, **pt;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
  for (i = 1; i <= M; i++) {
scanf("%d%d%d%s", &arr[i].from, &arr[i].to, &arr[i].len, str);
arr[i].dir = str[0];
 }
scanf("%d", &k);
for (i = 0; i < k; i++) {
scanf("%d%d%d", &nodes[i].a, &nodes[i].b, &j);
for (pt = &arr[j].query; *pt; pt = &(*pt)->next);
*pt = &nodes[i];
}
for (i = 1; i <= M; i++) {
switch (arr[i].dir) {
case 'E': x = arr[i].len; y = 0; break;
case 'W': x = -arr[i].len; y = 0; break;
case 'N': x = 0; y = arr[i].len; break;
case 'S': x = 0; y = -arr[i].len; break;
}
set_union(arr[i].from, arr[i].to, x, y);
for (t = arr[i].query; t; t = t->next) {
ia = set_find(t->a);
ib = set_find(t->b);
if (ia != ib)
j = -1;
else
j = abs(set[t->a].x - set[t->b].x) + abs(set[t->a].y - set[t->b].y);
printf("%d\n", j);
}
}
return 0;
}
思路： 每个节点记录在它以下的所有孩子的数目。后序遍历就比较容易得出结果了。
#include <stdio.h>
struct node {
struct node *next;
int idx;
};
struct node *map[10032], nodes[10032*2];
int N, nodes_cnt, can[10032];
__inline void add(int a, int b)
{
struct node *p = &nodes[nodes_cnt++];
p->idx = b;
p->next = map[a];
map[a] = p;
}
int dfs(int idx, int parent)
{
struct node *p;
int sum, i, res;
sum = 1;
res = 1;
for (p = map[idx]; p; p = p->next) {
if (p->idx == parent)
continue;
i = dfs(p->idx, idx);
if (i > N/2)
res = 0;
sum += i;
}
if (N - sum > N/2)
res = 0;
can[idx] = res;
return sum;
}
int main()
{
int i, a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
for (i = 0; i < N - 1; i++) {
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1, 0);
for (i = 1; i <= N; i++)
if (can[i])
printf("%d\n", i);
return 0;
}
思路： 典型的最小生成树，Prim搞定。但是速度好慢，用堆应该好一点。
#include <stdio.h>
int N, M;
struct node {
int idx, w;
struct node *next;
};
struct node edges[40032], *map[1024], *exists[1024][1024];
int edges_cnt;
char visited[1024];
__inline void add(int a, int b, int w)
{
struct node *p;
if (exists[a][b]) {
if (exists[a][b]->w < w)
exists[a][b]->w = w;
return ;
}
p = &edges[edges_cnt++];
p->idx = b;
p->w = w;
p->next = map[a];
map[a] = p;
exists[a][b] = p;
}
int main()
{
int i, j, k, max_val, max_idx, sum;
struct node *p;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d%d%d", &i, &j, &k);
add(i, j, k);
add(j, i, k);
}
visited[1] = 1;
sum = 0;
for (k = 0; k < N - 1; k++) {
max_val = -1;
for (i = 1; i <= N; i++) {
if (!visited[i])
continue;
for (p = map[i]; p; p = p->next)
if (!visited[p->idx] && p->w > max_val) {
max_val = p->w;
max_idx = p->idx;
}
}
if (max_val == -1)
break;
sum += max_val;
visited[max_idx] = 1;
}
printf("%d\n", k == N - 1 ? sum : -1);
return 0;
}
思路： 按照每个区间[a, b]中的a来从小到大排序。 第一次，计算开头落在 [0, 0] 之间的区间[a, b]中，b的最大值 b1。 第二次，计算开头落在 [0, b1 + 1] 之间的区间[a, b]中，b的最大值 b2。 第三次，计算开头落在 [b1 + 1, b2 + 1] 之间的区间 [a, b] 中，b的最大值 b3。 。。。
#include <stdio.h>
#include <stdlib.h>
struct node {
int start, end;
};
struct node arr[25032];
int N, T;
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->start - ((struct node *)b)->start;
}
int main()
{
int i, max_val, cnt, end;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &T);
for (i = 0; i < N; i++)
scanf("%d%d", &arr[i].start, &arr[i].end);
qsort(arr, N, sizeof(arr[0]), cmp);
i = cnt = 0;
end = 1;
while (end <= T) {
max_val = 0;
while (i < N && arr[i].start <= end) {
if (arr[i].end > max_val)
max_val = arr[i].end;
i++;
}
if (!max_val)
break;
end = max_val + 1;
cnt++;
}
printf("%d\n", end == T + 1 ? cnt : -1);
}
思路：
用线段树维护所有线段的分布。
新增加一个fence的时候，将fence的范围[a, b]插入线段树，节点的值为fence的编号，即高度。
那么fence上的某一点就是树的叶子了，从叶子往上一直到根节点的路径中节点的最大值，
就是从fence上的这一点垂直掉下去后，碰到的一个fence了。
这样，我们就可以在O(lgN)时间内知道，从一个fence的端点掉下去会碰到哪个fence了。 不然从后往前一个个找就是O(N)复杂度了。同时N也很大，必然超时。 同时也可以发现，一个fence保存两个值用作动态规划就好了，向左、右走之后，掉到其他fence上面，然后回到基地所用的最短路径。 推的方法很简单，掉到其他fence上面之后，看下是向左走距离短还是向右走距离短。就行了。 这个代码跑到400ms。
#include <stdio.h>
#define MAX_N 50032
#define MAX_R 100032
struct {
int a, b;
} dp[MAX_N], fences[MAX_N];
int N, S, tree[MAX_R*16];
__inline int max(int a, int b)
{
return a > b ? a : b;
}
__inline int abs(int a)
{
return a > 0 ? a : -a;
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
void insert(int idx, int start, int end, int left, int right, int val)
{
int mid;
if (start == left && right == end) {
tree[idx] = val;
return ;
}
mid = (start + end) / 2;
if (right <= mid)
insert(idx*2, start, mid, left, right, val);
else if (left > mid)
insert(idx*2+1, mid + 1, end, left, right, val);
else {
insert(idx*2, start, mid, left, mid, val);
insert(idx*2+1, mid + 1, end, mid + 1, right, val);
}
}
int query(int idx, int start, int end, int pos)
{
int val, mid;
if (start == pos && end == pos)
return tree[idx];
mid = (start + end) / 2;
if (pos <= mid)
val = query(idx*2, start, mid, pos);
else
val = query(idx*2+1, mid + 1, end, pos);
return max(val, tree[idx]);
}
__inline int calc_min(int i, int pos)
{
if (!i)
return abs(pos - MAX_R);
return min(pos - fences[i].a + dp[i].a, fences[i].b - pos + dp[i].b);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &S);
S += MAX_R;
for (i = 1; i <= N; i++) {
scanf("%d%d", &fences[i].a, &fences[i].b);
fences[i].a += MAX_R;
fences[i].b += MAX_R;
dp[i].a = calc_min(query(1, 0, MAX_R*2, fences[i].a), fences[i].a);
dp[i].b = calc_min(query(1, 0, MAX_R*2, fences[i].b), fences[i].b);
insert(1, 0, MAX_R*2, fences[i].a, fences[i].b, i);
}
printf( "%d\n",
min(S - fences[N].a + dp[N].a, fences[N].b - S + dp[N].b)
);
return 0;
}
思路：
开一个 64*64*64 大小的数组，记录该位置是否有放置方块。
开一个 25000 大小的数组，记录每个方块的位置。
然后每放一个方块，首先看该位置能不能放，然后再看6个方向是否有其他方块，如果有的话，就要调整总面积的和。
#include <stdio.h>
char placed[64][64][64];
struct node {
int x, y, z;
} box[25032];
int main()
{
int i, j, x, y, z, sum, N;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
box[1].x = 32;
box[1].y = 32;
box[1].z = 0;
placed[32][32][0] = 1;
sum = 5;
for (i = 2; i <= N; i++) {
scanf("%d%s", &j, str);
x = box[j].x;
y = box[j].y;
z = box[j].z;
switch (str[0]) {
case 'L': x--; break;
case 'R': x++; break;
case 'F': y--; break;
case 'B': y++; break;
case 'O': z++; break;
case 'U': z--; break;
}
if (z < 0)
break;
if (placed[x][y][z])
break;
box[i].x = x;
box[i].y = y;
box[i].z = z;
placed[x][y][z] = 1;
sum += 6;
if (placed[x - 1][y][z])
sum -= 2;
if (placed[x + 1][y][z])
sum -= 2;
if (placed[x][y - 1][z])
sum -= 2;
if (placed[x][y + 1][z])
sum -= 2;
if (!z)
sum--;
else if (placed[x][y][z - 1])
sum -= 2;
if (placed[x][y][z + 1])
sum -= 2;
}
printf("%d\n", i <= N ? -1 : sum);
return 0;
}
思路： 可以把一连串数字看成多个连续的递减序列。 所有递减序列的高度和就是答案了。 最后一个数字特殊处理。
#include <stdio.h>
int main()
{
int p, i, pre, first, cur, sum;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &p, &pre);
sum = 0;
first = pre;
while (--p) {
scanf("%d", &cur);
if (p == 1) {
if (cur < pre)
sum += first;
else
sum += first - pre + cur;
} else if (cur < pre)
pre = cur;
else {
sum += first - pre;
first = pre = cur;
}
}
printf("%d\n", sum);
return 0;
}
也可以用floyd。
#include <stdio.h>
#include <string.h>
#define MAX_N 332
char conn[MAX_N][MAX_N], visited[MAX_N];
int N, M, qh, qt, min_val, val;
struct {
int step, idx;
} queue[MAX_N];
__inline void insert(int i, int s)
{
if (visited[i])
return ;
queue[qt].idx = i;
queue[qt].step = s;
val += s;
qt++;
visited[i] = 1;
}
__inline void bfs(int idx)
{
int i, step;
memset(visited, 0, N + 1);
val = qh = qt = 0;
insert(idx, 0);
while (qh != qt) {
idx = queue[qh].idx;
step = queue[qh].step;
qh++;
for (i = 1; i <= N; i++)
if (conn[idx][i])
insert(i, step + 1);
}
if (val < min_val)
min_val = val;
}
int main()
{
int i, j, cnt, arr[MAX_N], a, b;
freopen("e:\\test\\in.txt", "r", stdin);
min_val = 0x7fffffff;
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d", &cnt);
for (i = 0; i < cnt; i++) {
scanf("%d", &arr[i]);
for (j = 0; j < i; j++) {
a = arr[i];
b = arr[j];
conn[a][b] = conn[b][a] = 1;
}
}
}
for (i = 1; i <= N; i++)
bfs(i);
printf("%d\n", 100 * min_val / (N - 1));
return 0;
}
题目大意： 给出一个N*N的矩阵，要查询任意B*B子矩阵内的元素最大值和最小值之差。 思路： 这应该算是一个二维的 RMQ 问题。但是做之前还不知道有RMQ这回事，就用一个动态规划做了。 还好速度也慢不到哪里去，也过了。哈哈。
#include <stdio.h>
struct node {
unsigned char arr[254], max, min;
};
__inline void node_init(struct node *n)
{
n->max = 0;
n->min = 255;
}
__inline void node_add(struct node *n, unsigned char val)
{
n->arr[val]++;
if (val > n->max)
n->max = val;
if (val < n->min)
n->min = val;
}
__inline void node_del(struct node *n, unsigned char val)
{
n->arr[val]--;
while (!n->arr[n->max])
n->max--;
while (!n->arr[n->min])
n->min++;
}
int N, B, K;
unsigned char data[256][256];
struct node row[256], col[256];
unsigned char ans[256][256];
int main()
{
int i, j, k;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &B, &K);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
scanf("%d", &k);
data[i][j] = k;
}
}
for (i = 0; i < N; i++) {
node_init(&row[i]);
for (j = 0; j < B; j++)
node_add(&row[i], data[i][j]);
}
for (i = 0; ; i++) {
node_init(&col[i]);
for (j = 0; j < B; j++) {
node_add(&col[i], row[j].max);
node_add(&col[i], row[j].min);
}
while (1) {
ans[j - B][i] = col[i].max - col[i].min;
if (j == N)
break;
node_del(&col[i], row[j - B].max);
node_del(&col[i], row[j - B].min);
node_add(&col[i], row[j].max);
node_add(&col[i], row[j].min);
j++;
}
if (i == N - B)
break;
for (j = 0; j < N; j++) {
node_del(&row[j], data[j][i]);
node_add(&row[j], data[j][i + B]);
}
}
while (K--) {
scanf("%d%d", &i, &j);
printf("%d\n", ans[i - 1][j - 1]);
}
return 0;
}
|