2015-06-22

b411. 記憶中的序列 2

Problem

動態區間 K 小，有四種操作

插入元素
刪除元素
修改元素
版本回溯
詢問某個區間的第 K 小元素

Sample Input

Sample Output

1
2
3

2
1
2

Solution

每次操作最多增加 $O(\sqrt{n})$ 記憶體，需要針對節點作抽象化，修改節點時再進行實體化，如此一來不用針對搜索路徑上的每一節點都進行複製，一般持久化平衡樹進行時，會直接複製整個節點，但塊狀鏈表若是複製下去會退化成時間、空間都是 $O(n)$ 的情況。

詢問時仍然需要二分搜索答案，看答案是否符合 K 小元素，也就是說要得到某個元素在區間中的排名。

塊狀鏈表代碼很醜，看看就好。如果需要支持修改、增加元素的區間 K 小，雖然複雜度高，但常數小、記憶體快取優勢，速度不比二元樹類型的資料結構來得慢，不管需不需要持久化塊狀鏈表都是這類型不錯的選擇。

另解

假設詢問為 $Q$ 個，聽說可以用區間 $[1, 2NQ]$ 的線段樹之類的超大區間線段樹，必要的探訪時進行開花 (將子節點打開)，利用標記計算相對位置來進行查詢。相對位置計算大概會在邊緣情況崩潰。

至於柳柳州提到的替罪羊樹是樹套樹下去持久化，每一個節點表示一個區間，接著在節點中建造一個平衡樹來查找區間 K 小元素。這樣的做法一樣需要二分搜索答案。但塊狀鏈表在速度跟記憶體都贏了，因為樹套樹的常數比較大，增加的記憶體也多。

#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
const int MAXQ = 131072;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
        Node* p = new Node();
        p->alias = t, p->next = u->next, mem.push(p);
        return p;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100000, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        	
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v, cmd;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) {			// back version v
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) { 	// insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x, v);
            } else if (cmd == 2) {	// delete A[x]
                scanf("%d", &x);
                x ^= encrypt;
                ver[i] = dream.erase(ver[i-1], x);
            } else if (cmd == 3) {	// make A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            } else if (cmd == 4) {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else {
                puts("WTF");
                return 0;
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}

Read More +

2015-06-16

解題區/解題區 - Zerojudge

b405. 記憶中的序列

Problem

給一個序列，支持插入元素、刪除元素、反轉區間、區間極值、區間總和、區間修改以及最重要的 版本回溯 。

題目輸入會拿上一個答案進行 XOR 的加密，

Sample Input

10
9 81 28 6 40 68 74 50 82 62 
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
85 82 89
14 13 13
56 61
57 57 40
58 61
59 61 63
60 57 59 4
61 58 49
137 139 136
37 38 42

decrypt input

10
9 81 28 6 40 68 74 50 82 62
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
6 1 10
7 4 4
0 5
1 1 16
2 5
3 5 7
4 1 3 60
5 2 9
6 4 7
7 4 8

Sample Output

Solution

持久化 treap，區間反轉，區間最大值，區間最小值，區間總和，插入元素，刪除元素，操作回溯。

這坑爹的題目描述擺明就是拖人下水，只好含淚地寫下去。持久化類型的題目應該是告一段落，就差一個 LCP + HASH 的維護了吧。麻煩的地方在於持久化的懶操作標記傳遞時都要新增加一個節點，這項舉動導致記憶體量非常多，1 秒處理的資訊吃掉 512 MB。二分記憶體上限，終於找到內存池的最多元素個數，中間不小心把多項資訊的 int 型態宣告成 long long，導致內存池一直不夠大。

如果不考慮回溯操作，速度上沒有比暴力算法來得快上很多，treap 基於隨機數的調整，而且每一次修改元素都要增加很多記憶體來補，導致速度上無法領先太多。但如果用暴力法，會造成版本回溯問題，空間會到 $O(
n^2)$，不允許的狀態，持久化造就的平均空間使用$O(Q log N \times sizeof(Node))$，看起來仍然是很巨大的。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 7100000
#define MAXQ 60005
class PersistentTreap {
public:
    struct Node;
    static Node *null;
    struct Node {
        Node *lson, *rson;
        int key, size;
        long long val, mnval, mxval, sumval;
        long long adel; // delivery
        int rdel;
        
        Node(long long c = 0, int s = 1): size(s) {
            lson = rson = null;
            key = rand();
            val = mnval = mxval = sumval = c;
            adel = rdel = 0;
        }
        void update() {
            size = 1;
            size += lson->size + rson->size;
        }
        void pushUp() {
            mnval = mxval = sumval = val;
            if (lson != null) {
                mnval = min(mnval, lson->mnval + lson->adel);
                mxval = max(mxval, lson->mxval + lson->adel);
                sumval += lson->sumval + lson->adel * lson->size;
            }
            if (rson != null) {
                mnval = min(mnval, rson->mnval + rson->adel);
                mxval = max(mxval, rson->mxval + rson->adel);
                sumval += rson->sumval + rson->adel * rson->size;
            }
        }
        void pushDown(PersistentTreap &treap) {
            if (adel) {
                val += adel, mnval += adel, mxval += adel;
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->adel += adel;
                }
                if (rson != null) {
                	rson = treap.cloneNode(rson);
                    rson->adel += adel;
                }
                adel = 0;
            }
            if (rdel&1) {
                if (lson == null)
                    lson = rson, rson = null;
                else if (rson == null)
                    rson = lson, lson = null;
                else
                    swap(lson, rson);
                
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->rdel += rdel;
                } 
                if (rson != null) {
                    rson = treap.cloneNode(rson);
                    rson->rdel += rdel;
                }
                rdel = 0;
            }
            pushUp();
        }
    } nodes[MAXN], *root[MAXQ];
    int bufIdx, verIdx;
    
    Node* merge(Node* a, Node* b) {
        if (a == null)	return cloneNode(b);
        if (b == null)	return cloneNode(a);
        if (a != null)	a->pushDown(*this);
    	if (b != null)	b->pushDown(*this);
        Node *ret;
        if (a->key < b->key) {
            ret = cloneNode(a);
            ret->rson = merge(a->rson, b);
        } else {
            ret = cloneNode(b);
            ret->lson = merge(a, b->lson);
        }
        ret->update();
        ret->pushUp();
        return ret;
    }
    void split(Node* a, Node* &l, Node* &r, int n) {
        if (n == 0) {
            l = null, r = cloneNode(a);
            return ;
        } 
        if (a->size <= n) {
            l = cloneNode(a), r = null;
            return ;
        }         
        if (a != null)
            a->pushDown(*this);
        if (a->lson->size >= n) {
            r = cloneNode(a);
            split(a->lson, l, r->lson, n);
            r->update();
            r->pushUp();
        } else {
            l = cloneNode(a);
            split(a->rson, l->rson, r, n - (a->lson->size) - 1);
            l->update();
            l->pushUp();
        }
    }
    
    void insert(Node* &a, Node *ver, int pos, long long s[], int sn) {
        Node *p, *q, *r;
        int n = sn;
        split(ver, p, q, pos);
        build(r, 0, n - 1, s);
        p = merge(p, r);
        a = merge(p, q);
    }
    void erase(Node* &a, Node *ver, int pos, int n) {
        Node *p, *q, *r;
        split(ver, p, q, pos - 1);
        split(q, q, r, n);
        a = merge(p, r);
    }
    void reverse(Node* &a, Node *ver, int left, int right) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->rdel++;
        a = merge(p, q);
        a = merge(a, r);
    }
    void add(Node* &a, Node *ver, int left, int right, long long val) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->adel += val;
        a = merge(p, q);
        a = merge(a, r);
    }
    long long q_sum, q_max, q_min;
    void q_dfs(Node *u, int left, int right) {
        left = max(left, 1);
        right = min(right, u->size);
        if (left > right)
            return;        
        if (u != null)
            u->pushDown(*this);
        int lsz = u->lson != null ? u->lson->size : 0;
        int rsz = u->rson != null ? u->rson->size : 0;
        if (left == 1 && right == lsz + rsz + 1) {
            q_sum += u->sumval;
            q_max = max(q_max, u->mxval);
            q_min = min(q_min, u->mnval);
            return ;
        }
        if (left <= lsz+1 && lsz+1 <= right) {
            q_sum += u->val;
            q_max = max(q_max, u->val);
            q_min = min(q_min, u->val);
        }
        
        if (u->lson != null && left <= lsz)
            q_dfs(u->lson, left, right);
        if (u->rson != null && right > lsz+1)
            q_dfs(u->rson, left - lsz - 1, right - lsz - 1);
    }
    void q_init() {
        q_max = LONG_LONG_MIN;
        q_min = LONG_LONG_MAX;
        q_sum = 0;
    }
    long long findMax(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_max;
    }
    long long findMin(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_min;
    }
    long long findSum(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_sum;
    }
    void print(Node *ver) {
        if (ver == null)	return;
        ver->pushDown(*this);
        print(ver->lson);
        printf("[%3lld]", ver->val);
        print(ver->rson);
    }
    void init() {
        bufIdx = verIdx = 0;
        root[verIdx] = null;
    }
private:
    Node* cloneNode(Node* u) {
        Node *ret;
        if (u == null) {
            return u;
        } else {
        	if (bufIdx >= MAXN)
        		exit(0);
            assert(bufIdx < MAXN);
            ret = &nodes[bufIdx++];
            *ret = *u;
            return ret;
        }
    }
    void build(Node* &a, int l, int r, long long s[]) {
        if (l > r)	return ;
        int m = (l + r) /2;
        Node u = Node(s[m]), *p = &u, *q;
        a = cloneNode(p), p = null, q = null;
        build(p, l, m-1, s);
        build(q, m+1, r, s);
        p = merge(p, a);
        a = merge(p, q);
        a->update();
        a->pushUp();
    }
} tree;
PersistentTreap::Node t(0, 0);
PersistentTreap::Node *PersistentTreap::null = &t;
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        tree.init();
        tree.insert(tree.root[0], tree.null, 0, A+1, N);
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            cmd ^= encrypt;
            if (cmd == 1) { 		// insert
                scanf("%lld %lld", &x, &v);
                x ^= encrypt, v ^= encrypt;
                long long B[] = {v};
                tree.insert(tree.root[i], tree.root[verIdx], (int) x, B, 1);
                verIdx = i;
            } else if (cmd == 2) { 	// erase
                scanf("%lld", &x);
                x ^= encrypt;
                tree.erase(tree.root[i], tree.root[verIdx], (int) x, 1);
                verIdx = i;
            } else if (cmd == 3) { 	// reverse
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                tree.reverse(tree.root[i], tree.root[verIdx], (int) x, (int) y);
                verIdx = i;
            } else if (cmd == 4) { 	// [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                tree.add(tree.root[i], tree.root[verIdx], (int) x, (int) y, v);
                verIdx = i;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMax(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMin(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ret = tree.findSum(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                x ^= encrypt;
                tree.root[i] = tree.root[x];
                verIdx = i;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}

Test Code

暴力法驗證用，不支持加密的輸入運行，用一個 vector 完成。

#include <bits/stdc++.h>
using namespace std;
#define MAXN (1<<19)
#define MAXQ 65536
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        vector< vector<long long> > L;
        L.push_back(vector<long long>(A+1, A+1+N));
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            vector<long long> TA = L[verIdx];
            if (cmd == 1) {         // insert
                scanf("%lld %lld", &x, &v);
                TA.insert(TA.begin()+x, v);
            } else if (cmd == 2) {  // erase
                scanf("%lld", &x);
                TA.erase(TA.begin()+x-1);
            } else if (cmd == 3) {  // reverse
                scanf("%lld %lld", &x, &y);
                reverse(TA.begin()+x-1, TA.begin()+y);
            } else if (cmd == 4) {  // [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                for (int i = (int) x-1; i < y; i++)
                    TA[i] += v;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MIN;
                for (int i = (int) x-1; i < y; i++)
                    ret = max(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MAX;
                for (int i = (int) x-1; i < y; i++)
                    ret = min(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = 0;
                for (int i = (int) x-1; i < y; i++)
                    ret += TA[i];
                printf("%lld\n", ret);
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                TA = L[x];
            } else {
                puts("WTF");
                return 0;
            }
            L.push_back(TA), verIdx = i;
            printf("version %d\n", i);
            for (auto &x: TA)
                printf("[%3lld]", x);
            puts("");
        }
    }
    return 0;
}

Test Generator

小測資檢驗用

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
     srand (time(NULL));
    int testcase, n, m, x, y;
    int A[100];
    testcase = 1;
    freopen("in.txt", "w+t", stdout);
//    printf("%d\n", testcase);
    while (testcase--) {
        n = 32;
        printf("%d\n", n);
        for (int i = 0; i < n; i++) {
            printf("%d%c", rand(), i == n-1 ? '\n' : ' ');
        }
        m = 1000;
        printf("%d\n", m);
        vector<int> L;
        L.push_back(n);
        for (int i = 1; i <= m; i++) {
            while (true) {
                int cmd = rand()%8;
                if (n == 1 && cmd == 2)
                    continue;
                if (cmd == 0) {
                	int x = rand()%i;
                	printf("%d %d\n", cmd, x);
                	n = L[x];
                }
                if (cmd == 1)
                    printf("%d %d %d\n", cmd, rand()%(n+1), rand()), n++;
                if (cmd == 2)
                    printf("%d %d\n", cmd, rand()%n+1), n--;
                if (cmd == 3) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                if (cmd == 4) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d %d\n", cmd, x, y, rand());
                }
                if (cmd == 5 || cmd == 6 || cmd == 7) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                break;
            }
            L.push_back(n);
        }
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b327. 學姊日談

內容：

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

輸入說明：

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

輸出說明：

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行，保證總和可以在 signed 32 bits 內。

範例輸入：

範例輸出：

Solution 1

先將一棵樹壓平，壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後，每個節點對應一個左右括弧位置，當我們增加節點 v 權重時，相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

操作 [l, r]：將區間內的所有數字加上 k
詢問 x：詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整，單點詢問。

對於 ADD [l, r] k 時，相當於 BIT[l] += k, BIT[r+1] -= k，單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
    bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
    for (int i = 0; i < tree.g[u].size(); i++) {
        int v = tree.g[u][i];
        if (v == p)	continue;
        prepare(v, u);
    }
    ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
    while (x <= N) {
        bitTree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += bitTree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        inIdx = 0;
        prepare(tree.root = 0, -1);
        memset(bitTree, 0, sizeof(bitTree));
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(bPos[x], inIdx, y);
            modify(ePos[x] + 1, inIdx, -y);
            printf("%d\n", query(bPos[x]));
        }
        puts("");
    }
    return 0;
}

Solution 2

這個解法直接使用樹鏈剖分，樹鏈剖分將子樹節點數量最大的當作重邊，其餘皆為輕邊。將以重邊相連的所有節點，看似一個鏈狀，當作一個 1D Array 看待。

保證每個點爬到 root，只會經過 log n 的輕邊，而中間鏈狀處理，可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法，詢問效率 O(log^2 n)，調整 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
    int p, pPos;
    vector<int> A;
    vector<int> BIT;
    void init() {
        A.clear(), BIT.clear();
        p = -1;
    }
} nodes[262144];
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int prepare(int u, int p) {
    int sz = 1, mx = 0, hedge = -1;
    int v, t;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i], t;
        if (v == p)	continue;
        sz += (t = prepare(v, u));
        if (mx < t)
            mx = t, hedge = v;
    }
    hNext[u] = hedge;
    return sz;
}
void build(int u, int p) {	
    if (used[u] == 0) {
        Node &nd = nodes[++nodesize];
        nd.init();
        for (int i = u; i != -1; i = hNext[i]) {
            used[i] = 1;
            iNode[i] = nodesize, aPos[i] = nd.A.size();
            nd.A.push_back(i);
        }
        nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
        if (p != -1)	nd.p = iNode[p], nd.pPos = aPos[p];
    }
    int v;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i];
        if (v == p)	continue;
        build(v, u);
    }
}
int queryBIT(vector<int> &BIT, int x) {
    int ret = 0;
    while (x)
        ret += BIT[x], x -= x&(-x);
    return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
void search(int u) {
    int sum = 0;
    set< pair<int, int> >::iterator it, jt;
    for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
        sum += queryBIT(nodes[i].BIT, in + 1);
    printf("%d", sum);
    puts("");
}
void modify(int u, int val) {
    Node &nd = nodes[iNode[u]];
    int pos = aPos[u];
    modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        prepare(tree.root = 0, -1);
        memset(used, 0, sizeof(used));
        nodesize = 0;
        build(tree.root = 0, -1);
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(x, y);
            search(x);
        }
        puts("");
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b322. 樹形鎖頭

內容：

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

輸入說明：

輸入有多組測資。

每一組測資第一行會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

輸出說明：

每組測資輸出一行，分別將節點權重輸出。

範例輸入：

範例輸出：

1	5 3 5 3 2 4 8

Solution

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
int visited[32767];
vector<int> tree[32767];
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
    	if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
    int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
    	if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int n, m, x, y, u, v, k;
    int X[32767], Y[32767], K[32767];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            tree[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        
        int weight[32767] = {}, extra[32767] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &X[i], &Y[i], &K[i]);
            Q[X[i]].push_back(make_pair(i, Y[i]));
        	Q[Y[i]].push_back(make_pair(i, X[i]));
        }
        tarjan(0, -1);
        for (int i = 0; i < m; i++) {
            extra[LCA[i]] += K[i];
            weight[X[i]] += K[i];
            weight[Y[i]] += K[i];
            weight[LCA[i]] -= 2 * K[i];
        }
        dfs(0, -1, weight);
        for (int i = 0; i < n; i++)
            printf("%d%s", weight[i] + extra[i], i == n-1 ? "" : " ");
        puts("");
    }
    return 0;
}

Read More +

2014-10-17

解題區/解題區 - Zerojudge

b321. 河道分界

內容：

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

輸入說明：

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

輸出說明：

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

範例輸入：

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

範例輸出：

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

Solution

建造一個 BST，這裡使用內建 std::set 的紅黑樹，查找 lower_bound 即可。如果是靜態的河道，一開始對其排序即可，然後二分查找 lower_bound。

如果測資有錯，歡迎打我。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct seg {
    Pt s, e;
    int label;
    seg(Pt a, Pt b):s(a), e(b) {}
};
struct CMP {
    static double y;
    
    double interpolate(const Pt& p1, const Pt& p2, double& y) {
        if (p1.y == p2.y) return p1.x;
        return p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (y - p1.y);
    }
    
    bool operator()(const seg &i, const seg &j) {
        double v1 = interpolate(i.s, i.e, y), v2 = interpolate(j.s, j.e, y);
        if (fabs(v1 - v2) > eps)
            return v1 < v2;
        return false;
    }
};
double CMP::y = 0;
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n;
    double x, y, up, down;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        set<seg, CMP> S;
        for (int i = 0, k = 1; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'A') {
                scanf("%lf %lf", &up, &down);
                seg tmp = seg(Pt(up, 1), Pt(down, 0));
                tmp.label = k;
                S.insert(tmp), k++;
            } else {
                scanf("%lf %lf", &x, &y);
                CMP::y = y;
                set<seg>::iterator it = S.lower_bound(seg(Pt(x, 1), Pt(x, 1))), jt;
                if (it != S.end()) {
                    if (onSeg(it->s, it->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                int l = -1, r = -1;
                if (it != S.begin()) {
                    jt = it, jt--;
                    l = jt->label;
                    if (onSeg(jt->s, jt->e, Pt(x, y))) {
                        puts("[?, ?]");
                        continue;
                    }
                }
                if (it != S.end())
                    r = it->label;
                if (l == -1)
                    printf("[S, ");
                else
                    printf("[%d, ", l);
                if (r == -1)
                    printf("M]");
                else
                    printf("%d]", r);
                puts("");
            }
        }
    }
    return 0;
}

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b317. 紅圓茵可的野望

內容：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

N<=100
N<=100
N<=100
N<=100000
N<=100000

輸出說明：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入：

範例輸出：

提示：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log n)，套用當前最佳解剪枝應該快上很多。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
    int ret = 0;
    for (; x; x -= x&(-x))
        ret += BIT[x];
    return ret;
}
void modify(int x, int L) {
    for (; x <= L; x += x&(-x))
        BIT[x]++;
}
int main() {
    int N, K, r, h, w;
    while (scanf("%d %d", &N, &K) == 2) {
        vector<pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &r, &h);
            assert(r <= 100 && h <= 100 && r > 0 && h > 0);
            D.push_back(make_pair(r * 2, h));
        }
        int ret = 0x3f3f3f3f;
        sort(D.begin(), D.end());
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < N; i++) {
            modify(D[i].second, 255);
            for (int j = D[i].second; j <= 100; j++) {
                int q = query(j);
                w = D[i].first, h = j;
                if (q >= K)
                    ret = min(ret, w*w*h);
            }
        }
        if (K == 0)	ret = 0;
        printf("%d\n", ret);
    }
    return 0;
}

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b316. 紅圓茵可的消失

內容：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

N<=10,K<=100
N<=10,K<=100
N<=1000,K<=1000
N<=1000,K<=1000000000，整張圖為一棵樹
N<=1000,K<=1000000000

輸出說明：

輸出第K天時茵可會走到哪個點。

範例輸入：

範例輸出：

提示：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式$cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
    int N, M, K;
    int x, y;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            if (x > y)	swap(x, y);
            g[x].push_back(y);
        }
        for (int i = 0; i < N; i++)
            sort(g[i].begin(), g[i].end());
        int pass[1024] = {};
        int now = 0, x, sum = 0;
        pass[0] = --K;
        for (int i = 0; i < N; i++) {
            if (g[i].size() == 0)	continue;
            int u = i, v, div = pass[u] % g[i].size();
            for (int j = 0; j < g[i].size(); j++) {
                v = g[i][j];
                pass[v] += pass[u] / g[i].size();
                if (j < div)
                    pass[v]++;
            } 
        }
        for (; g[now].size(); ) {
            x = pass[now]%g[now].size();
            now = g[now][x];
//			printf("-> %d\n", now);
        }
        printf("%d\n", now);
    }
    return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/

Read More +

2014-10-06

解題區/解題區 - Zerojudge

b315. 紅圓茵可的考驗

內容：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

N<=10，K<=N*(N-1)/2
N<=1,000，K<=N*(N-1)/2
N<=10,000，K<=10,000
N<=100,000，K<=100,000
N<=100,000，K<=1,000,000,000

輸出說明：

輸出第K大數字差

範例輸入：

1 2	4 5 1 5 8 10

範例輸出：

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n log n)，因為中間的索引值肯定是單調的，不過要考慮組合問題，特別要小心同一個元素自減的結果。由於懶得判斷，複雜度高了點還是過了。

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
    int mx = A[0], mn = A[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, A[i]), mn = min(mn, A[i]);
    int l = 0, r = mx - mn, mid, ret;
    m = (long long) n * (n-1)/2 - m + 1;
    long long cnt;
    sort(A, A+n);
    while (l <= r) {
        mid = (l + r)/2;
        cnt = 0;
        for (int i = 0; i < n; i++) {
            int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
            cnt += pos - i - 1;
        }
        if (cnt >= m)
            r = mid - 1, ret = mid;
        else
            l = mid + 1;
    } 
    return ret;
}
int main() {
    int n, m, A[131072];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("%d\n", kThDiff(A, n, m));
    }
    return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/

Read More +

2014-10-05

解題區/解題區 - Zerojudge

b314. 紅圓茵可的煩惱

內容：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

N,M<=10
N,M<=50
N,M<=100
N,M<=1000
N,M<=1000

輸出說明：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入：

範例輸出：

<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

Solution

這一題相當活用并查集的概念，雖然題目問說是否能左右相連，但是反過來則是上下邊界是否會從不相連變成相連。

多設兩個虛點，我們假想所有上界點都與虛上點相連，下界點都與虛下點相連，每次一次加入一個障礙物時，檢查九宮格內是否會造成上下虛點相連，這裡必須先偷看并查集的結果，隨後在考慮是否將其相連。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
    return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
    p = findp(p), q = findp(q);
    if (weight[p] > weight[q])
        weight[p] += weight[q], parent[q] = p;
    else
        weight[q] += weight[p], parent[p] = q;
    return 1;
}
int main() {
    int n, m, Q, cases = 0;
    int x, y, tx, ty;
    while (scanf("%d %d %d", &n, &m, &Q) == 3) {
        cases++;
        int N = n * m + 10, up = n * m + 1, down = n * m + 2;
        int p, q, A[8];
        for (int i = 0; i < N; i++)
            parent[i] = i, weight[i] = 1;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d", &x, &y);
            p = x * m + y;
            up = findp(up), down = findp(down);
            int s = 0;
            for (int j = 0; j < 8; j++)	{
                tx = x + dx[j], ty = y + dy[j];
                if (ty < 0 || ty >= m)	{
                    A[j] = p;
                    continue;
                }
                if (tx < 0)			q = up;
                else if(tx >= n)	q = down;
                else {
                    if (used[tx][ty] != cases) {
                        A[j] = p;
                        continue;
                    }
                    q = tx * m + ty;
                }
                if (findp(q) == up)		s |= 1;
                if (findp(q) == down)	s |= 2;
                A[j] = q;
            }
            if (s != 3) {
                puts("<(_ _)>");
                for (int j = 0; j < 8; j++) {
                    joint(p, A[j]);
                }
                used[x][y] = cases;
            } else {
                puts(">_<");
            }
        }
    }
    return 0;
}

Read More +

2014-08-30

解題區/解題區 - Zerojudge

a577. 高精度乘法

Problem

這題十分直接，就是要你計算兩個很大的數字的乘積。

Sample Input

Sample Output

1
2

0
132

Solution

快速傅立葉 FFT 對我來說也是一知半解，但是我能知道他計算旋積可以在 O(n log n) 完成 n 個答案結果。

旋積計算就是對於維度為 n 的兩個向量，相互作內積，其中一個向量不斷地作 rotate shift right 的操作，因此會有 n 個內積結果。

如果要套用在這一題，相當於操作多項式乘法的計算，舉個例子來說

123 x 456

相當於下面兩個向量作旋積

(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 4, 5, 6)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 4, 5, 6, 0)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 4, 5, 6, 0, 0)
dot = 0
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 0, 4, 5, 6, 0, 0, 0)
dot = 4
(3, 2, 1, 0, 0, 0, 0, 0)
(0, 4, 5, 6, 0, 0, 0, 0)
dot = 13

如此類推，不過 FFT 只能使用 double 運算，因此在儲存精度上不是很好拿捏，誤差大概在 1e-1 ~ 1e-2 之間。

感謝 liouzhou_101 的誤差指導

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
#include <complex>
#include <cmath>
using namespace std;
#define for if (0); else for
using namespace std;
const int MaxFastBits = 16;
int **gFFTBitTable = 0;
int NumberOfBitsNeeded(int PowerOfTwo) {
    for (int i = 0;; ++i) {
        if (PowerOfTwo & (1 << i)) {
            return i;
        }
    }
}
int ReverseBits(int index, int NumBits) {
    int ret = 0;
    for (int i = 0; i < NumBits; ++i, index >>= 1) {
        ret = (ret << 1) | (index & 1);
    }
    return ret;
}
void InitFFT() {
    gFFTBitTable = new int *[MaxFastBits];
    for (int i = 1, length = 2; i <= MaxFastBits; ++i, length <<= 1) {
        gFFTBitTable[i - 1] = new int[length];
        for (int j = 0; j < length; ++j) {
            gFFTBitTable[i - 1][j] = ReverseBits(j, i);
        }
    }
}
inline int FastReverseBits(int i, int NumBits) {
    return NumBits <= MaxFastBits ? gFFTBitTable[NumBits - 1][i] : ReverseBits(i, NumBits);
}
void FFT(bool InverseTransform, vector<complex<double> >& In, vector<complex<double> >& Out) {
    if (!gFFTBitTable) { InitFFT(); }
    // simultaneous data copy and bit-reversal ordering into outputs
    int NumSamples = In.size();
    int NumBits = NumberOfBitsNeeded(NumSamples);
    for (int i = 0; i < NumSamples; ++i) {
        Out[FastReverseBits(i, NumBits)] = In[i];
    }
    // the FFT process
    double angle_numerator = acos(-1.) * (InverseTransform ? -2 : 2);
    for (int BlockEnd = 1, BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1) {
        double delta_angle = angle_numerator / BlockSize;
        double sin1 = sin(-delta_angle);
        double cos1 = cos(-delta_angle);
        double sin2 = sin(-delta_angle * 2);
        double cos2 = cos(-delta_angle * 2);
        for (int i = 0; i < NumSamples; i += BlockSize) {
            complex<double> a1(cos1, sin1), a2(cos2, sin2);
            for (int j = i, n = 0; n < BlockEnd; ++j, ++n) {
                complex<double> a0(2 * cos1 * a1.real() - a2.real(), 2 * cos1 * a1.imag() - a2.imag());
                a2 = a1;
                a1 = a0;
                complex<double> a = a0 * Out[j + BlockEnd];
                Out[j + BlockEnd] = Out[j] - a;
                Out[j] += a;
            }
        }
        BlockEnd = BlockSize;
    }
    // normalize if inverse transform
    if (InverseTransform) {
        for (int i = 0; i < NumSamples; ++i) {
            Out[i] /= NumSamples;
        }
    }
}
vector<double> convolution(vector<double> a, vector<double> b) {
    int n = a.size();
    vector<complex<double> > s(n), d1(n), d2(n), y(n);
    for (int i = 0; i < n; ++i) {
        s[i] = complex<double>(a[i], 0);
    }
    FFT(false, s, d1);
    s[0] = complex<double>(b[0], 0);
    for (int i = 1; i < n; ++i) {
        s[i] = complex<double>(b[n - i], 0);
    }
    FFT(false, s, d2);
    for (int i = 0; i < n; ++i) {
        y[i] = d1[i] * d2[i];
    }
    FFT(true, y, s);
    vector<double> ret(n);
    for (int i = 0; i < n; ++i) {
        ret[i] = s[i].real();
    }
    return ret;
}
struct Polynomial {
    vector<double> v;
    Polynomial operator*(const Polynomial &other) const {
        int n = (int) max(v.size(), other.v.size()) * 2, m;
        for (m = 2; m < n; m <<= 1);
        vector<double> na, nb;
        na.resize(m, 0), nb.resize(m, 0);
        for (int i = 0; i < v.size(); i++)
            na[i] = v[i];
        for (int i = 0, j = m - 1; i < other.v.size(); i++, j--)
            nb[j] = other.v[i];
        Polynomial ret;
        ret.v = convolution(na, nb);
        for (int i = 1; i < ret.v.size(); i++)
            ret.v[i - 1] = ret.v[i];
        ret.v[ret.v.size() - 1] = 0;
        return ret;
    }
};
char sa[1<<18], sb[1<<18];
long long ret[1<<19];
int main() {
    while (scanf("%s %s", sa, sb) == 2) {
        Polynomial a, b, c;
        for (int i = (int)strlen(sa) - 1; i >= 0; i--)
            a.v.push_back(sa[i] - '0');
        
        for (int i = (int)strlen(sb) - 1; i >= 0; i--)
            b.v.push_back(sb[i] - '0');
        c = a * b;
        
        memset(ret, 0, sizeof(ret));
        int f = 0;
        double eps = 1.5e-1;
        for (int i = 0; i < c.v.size(); i++)
            ret[i] = (long long) (c.v[i] + eps);
        int n = (int)c.v.size();
        for (int i = 0; i < n; i++) {
            if (ret[i] >= 10) {
                ret[i + 1] += ret[i]/10;
                ret[i] %= 10;
            }
        }
        for (int i = n; i >= 0; i--) {
            if (ret[i])
                f = 1;
            if (f)
                printf("%lld", ret[i]);
        }
        if (!f)
            printf("0");
        puts("");
    }
    return 0;
}
/*
 0
 5
 
 11
 12
 */

Read More +

Problem

Sample Input

Sample Output

Solution

另解

Problem

Sample Input

Sample Output

Solution

Test Code

Test Generator

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution 1

Solution 2

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

Problem

Sample Input

Sample Output

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：