【題解】HDU 3974 Assign the task

【範例】樹壓平 (樹的DFS序)
【題目敘述】https://vjudge.net/problem/HDU-3974
【解題想法】線段樹(Segment Tree) + 樹壓平

做法(I) 線段樹 + 樹壓平

  • 題目是一棵樹:
    • 讀入測資時,先用p[ ] 和 vector<int> g[ ] 把樹狀圖存下來。
    • Line-74:找出原始樹狀圖的根節點 (下圖例 rt = 2)。
    • 從 rt 開始進行樹上的 DFS,找出每位員工 x 在樹上的序位編號。此處的DFS是前序遍歷(preorder traversal):根 -> 左子樹 -> 右子樹。
    • 進出樹狀圖的每個節點時,都有時間戳記(Line-17和Line-21),進入的時候紀錄一次(in[x]),出來的時候也要紀錄一次(out[x])。
    • 每個 in[x] ~ out[x] 區間,代表員工 x 轄下的組織圖(包含 x 及其所有直接/間接部屬)。
  • 樹壓平:
    • 當樹上的一個節點跟其子樹(subtree)擁有共同性質時(這題是進行相同任務),把所有人視為同一個群組 (把他們安置在一個「連續區間」)。
    • 當原始的樹不是平衡架構,特別是含有長鍊時,利用線段樹來維護資料 (二元樹),會比較有效率。(但這題的測資太弱分辨不出來。)
  • 建立線段樹:
    • 查詢員工 x 的任務時,在線段樹上 query(1, 1, N, in[x])。
    • 指派任務 y 給員工 x 時,進行線段樹的區間修改 update(1, 1, N, in[x], out[x], y)。
    • sum[i]:線段樹上節點 i 的任務編號。
    • lz[i]:線段樹上節點 i 尚未往下傳遞的任務編號。
    • query( )和update( )之前,都須先做一次 push( ),處理之前留下來的 lazy tag。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=50005;

int T, N, u, v, M;
int Case = 1;
char op;
int x, y;
int root, time_stamp;
vector<int> g[maxn];
int p[maxn], in[maxn], out[maxn];
int sum[maxn<<2], lz[maxn<<2];

void dfs(int x){
    in[x] = ++time_stamp;
    for (auto i: g[x]){
        dfs(i);
    }
    out[x] = time_stamp;
}

void push(int x){
    if (lz[x] == -1) return;
    sum[x<<1] = sum[x<<1|1] = lz[x];
    lz[x<<1] = lz[x<<1|1] = lz[x];
    lz[x] = -1;
}

void update(int x, int l, int r, int ql, int qr, int val){
    if (ql <= l && r <= qr){
        sum[x] = val;
        lz[x] = val;
        return;
    }
    push(x);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(x<<1, l, mid, ql, qr, val);
    if (mid+1 <= qr) update(x<<1|1, mid+1, r, ql, qr, val);
}

int query(int x, int l, int r, int pos){
    if (l == r){
        return sum[x];
    }
    push(x);
    int mid = (l + r) >> 1;
    if (pos <= mid) return query(x<<1, l, mid, pos);
    else return query(x<<1|1, mid+1, r, pos);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--){
        cin >> N;
        memset(p, 0, sizeof(p));
        memset(sum, -1, sizeof(sum));
        memset(lz, -1, sizeof(lz));
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        for (int i=0; i<maxn; i++){
            g[i].clear();
        }
        
        for (int i=0; i<N-1; i++){
            cin >> u >> v;
            p[u] = v;
            g[v].push_back(u);
        }
        for (int i=1; i<=N; i++){
            if (!p[i]) root = i;
        }
        time_stamp = 0;
        dfs(root);
        
        cout << "Case #" << Case++ << ":\n";
        cin >> M;
        while (M--){
            cin >> op;
            if (op == 'C'){
                cin >> x;
                cout << query(1, 1, N, in[x]) << '\n';
            } else {
                cin >> x >> y;
                update(1, 1, N, in[x], out[x], y);
            }
        }
    }
    return 0;
}

做法(II) 只有lazy tag

  • pa[a] = b:員工 a 的直屬主管是 b。
  • vector<int> kid[b]:紀錄主管 b 的屬下們。
  • job[x] = y:指派「任務 y」給 「員工 x」。(初始值 -1)
  • lazy[x] = y:表示「員工 x」肩負的「任務 y」尚未傳給屬下。(初始值 -1)
  • 查詢「員工 x」的任務時,先一層一層回溯(update)其主管的狀態,若主管的lazy tag不是 -1,則先把主管的工作往下傳遞(push)。最後 job[x] 即為正確答案。
  • 指派新的「任務 y」給 「員工 x」時,也要先進行update (處理所有上層的lazy tag),確保未來讀取「員工 x 的屬下們」的狀態時,答案會正確。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int maxn = 50005;
int t, n, m, a, b, pa[maxn], job[maxn], lazy[maxn];
char C;
vector <int> kid[maxn];

void push(int x){
    if (lazy[x] == -1) return;
    for (int k:kid[x]){
        job[k] = lazy[x];
        lazy[k] = lazy[x];
    }
    lazy[x] = -1;
}

void update(int x){
    if (pa[x] != 0){
        update(pa[x]);
    }
    push(x);
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    for (int iter = 1; iter <= t; iter++){
        cout << "Case #" << iter << ":\n";
        memset(pa, 0, sizeof(pa));
        memset(job, -1, sizeof(job));
        memset(lazy, -1, sizeof(lazy));
        cin >> n;
        for (int i = 1; i <= n; i++){
            kid[i].clear();
        }
        for (int i = 1; i < n; i++){
            cin >> a >> b;
            pa[a] = b;
            kid[b].push_back(a);
        }

        cin >> m;
        for (int i = 0; i < m; i++){
            cin >> C;
            if (C == 'C'){
                cin >> a;
                update(pa[a]);
                cout << job[a] << "\n";
            }else{
                cin >> a >> b;
                update(pa[a]);
                job[a] = b;
                lazy[a] = b;
            }
        }
    }
}

做法(III) 普通的樹

  • Credit: Amy Chou
  • p[ ]: 紀錄每位員工的直屬主管。
  • {t, task}: 紀錄每位員工被指派的任務及該任務被指派的時間。
  • 查詢時,找出員工自己及其所有上層老闆們接受的任務和時間,其中時間最大的任務即是答案。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=50005;

int T, N, u, v, M;
int Case = 1;
char op;
int x, y;

struct Employee{
    int t, task;
} e[maxn];

int p[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--){
        cin >> N;
        memset(p, 0, sizeof(p));
        for (int i=1; i<=N; i++){
            e[i].t = 0;
            e[i].task = 0;
        }
        for (int i=0; i<N-1; i++){
            cin >> u >> v;
            p[u] = v;
        }
        cout << "Case #" << Case++ << ":\n";
        cin >> M;
        int time = 0;
        while (M--){
            cin >> op;
            if (op == 'C'){
                cin >> x;
                int now_t = e[x].t;
                int now_task = e[x].task;
                while (p[x]){
                    x = p[x];
                    if (e[x].t > now_t){
                        now_t = e[x].t;
                        now_task = e[x].task;
                    }
                }
                if (now_task) cout << now_task << '\n';
                else cout << "-1\n";
            } else {
                cin >> x >> y;
                e[x].task = y;
                e[x].t = ++time;
            }
        }
    }
    return 0;
}
分享本文 Share with friends