|
|
轉自: http://www.shnenglu.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;
}
|