解題區/出題解題

[ACM 題目] 動態前綴

Problem

某 M 「給一個字串 S，接著詢問操作 [l, r] 告訴區間內是否剛好為一個迴文？」
學弟 「用最長迴文的方式去想嗎？」
某 M 「我沒有標準答案哦 wwww，吾等還在想能不能離線 O(1)。」

暗自敲著 UVa 另外一題類似題說著，就算能 O(1) 檢查迴文，區間還是要窮舉 O(n)，在此宣告某 M 陣亡－ Time Limit 。

某 M 心想，假解也是不錯選擇，單純詢問迴文肯定會被 manacher’s algorithm 秒掉 (O(1) - O(n))。如果詢問 [l, r] 的子字串是否符合 pattern AA (例如 abcabc，其中 A = abc)，也會被 suffix array、suffix tree 解決 (O(log n) - O(n log n)/O(n))。

百般無奈之下，也許這題就這樣定好了：

C p x：將字串位置 p 修改成字符 x。
Q p q：求子字串 S.substr(p) 和 S.substr(q) 的最長共同前綴長度。

1
2
3
4
5
6
7
8
void change(char s[], int p, int x) {
    s[p] = x;
}
int query(char s[], int p, int q) {
    int ret = 0;
    for (; s[p] == s[q] && s[p] && s[q]; p++, q++, ret++);
    return ret;
}

Sample Input

1
2
3
4
5
abcdabcc
3
Q 0 4
C 3 c
Q 0 4

Sample Output

1
2
3
4

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const long long mod = 100000007LL;
#define MAXN (1<<17)
char S[MAXN];
long long base[MAXN];
long long tree[MAXN<<1];
long long build(int k, int l, int r) {
    assert(l <= r);
    if (l == r)
        return tree[k] = (S[l] % mod);
    int m = (l + r)/2;
    build(k<<1, l, m);
    build(k<<1|1, m+1, r);
    tree[k] = (tree[k<<1] * base[r - m] + tree[k<<1|1]) %mod;
}
void modify(int k, int l, int r, int x, int v) {
    if (l == r) {
        tree[k] = v;
        return;
    }
    int m = (l + r)/2;
    if (x <= m)
        modify(k<<1, l, m, x, v);
    else
        modify(k<<1|1, m+1, r, x, v);
    tree[k] = (tree[k<<1] * base[r - m]%mod + tree[k<<1|1]) %mod;
}
long long query(int k, int l, int r, int x, int y) {
    assert(l >= 0 && l <= r);
    if (x <= l && r <= y) {
        return tree[k];
    }
    int m = (l + r)/2;
    if (y <= m)
        return query(k<<1, l, m, x, y);
    else if(x > m)
        return query(k<<1|1, m+1, r, x, y);
    else {
        long long p, q;
        p = query(k<<1, l, m, x, y);
        q = query(k<<1|1, m+1, r, x, y);
        return (p * base[min(y, r) - m]%mod + q) %mod;
    }
}
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    base[0] = 1;
    for (int i = 1; i < MAXN; i++) 
        base[i] = (base[i-1] * 2)%mod;
    char cmd[8], s[8];
    int Q, p, q, n;
    while (scanf("%s", S) == 1) {
        n = strlen(S);
        build(1, 0, n - 1);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d %d", &p, &q);
                if (p == q) {
                    printf("%d\n", n - p);
                    continue;
                } else if (S[p] != S[q]) {
                    puts("0");
                    continue;
                }
                int l = 0, r = min(n - p, n - q) - 1, m, ret = 0;
                long long hp, hq;
                while (l <= r) {
                    m = (l + r)/2;
                    hp = query(1, 0, n-1, p, p + m);
                    hq = query(1, 0, n-1, q, q + m);
                    if (hp == hq)
                        l = m + 1, ret = m;
                    else
                        r = m - 1;
                }
                printf("%d\n", ret + 1);
            } else {
                scanf("%d %s", &p, s);
                S[p] = s[0];
                modify(1, 0, n - 1, p, s[0]);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12538 - Version Controlled IDE

Problem

題目有三種字符串的操作：

  • 1 p s: 在當前字串位置 p 後插入 s 字串。
  • 2 p c: 將當前字串位置 p 後面連續 c 個字符移除。
  • 3 v p c: 在版本號 v 的字串中，在位置 p 之後印出 c 個字元。

由於怕離線處理，因此輸入的數值會進行加密，加密的原則－每個數字會增加數值 d，其 d 為當前打印字符 c 的個數。

Sample Input

1
2
3
4
5
6
7
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6

Sample Output

1
2
3
bcdef
bcg
bxyc

Solution

代碼算法詳見 《可持久化數據結構研究》杭州外國語學校－陳立杰　那篇所寫的 Treap(樹堆)。

這題的離線作法是預先紀錄需要的版本號位置，在邊處理的時候隨時保存答案，以免造成記憶體過大儲存。既然他進行了加密，可見我們不能把每一個版本號的字串儲存，這就是其麻煩之處。

接下來說明的作法，是將每個字符當作節點，在一個二元搜尋樹上，利用中序走訪的結果表示一個字串。

可持久化 Treap

Treap 主要概念是平衡樹，也就是儲存有序的結構，支持插入、刪除、查找數字。冠上可持久化平衡樹，就是一個維護歷史版本的平衡樹。

Treap 每一個節點具有 <key, value>，仍然是一個二元搜尋樹，但同時也是一個 heap。單純看 key 呈現一個二元搜尋樹，如果看 value 則會是 heap。key 跟 value 是挺像的，我的代碼誤打了名稱。而 Treap 效率完全取決於隨機決定的 value 值進行平衡調整。

對於可持久化 Treap 而言，是一個具有平衡樹特性，但不需要做任何旋轉操作的樹。每一次將修改操作替代為一個增加節點的方式 ( 用增加替代修改 的精神)，在記憶體耗量就是 O(m log n)，m 是其操作，log n 是樹內結構的期望深度。每一次操作期望只修改 log n 個節點。

操作定義

這裡只會講到可持久化，拆分成兩個操作，而原本的插入、刪除、查找都可以利用這兩個操作完成。

$$\text{ treap merge(treap a, treap b) } \\ < \text{treap, treap} > \text{ split(treap a, int n) }$$
  • merge a b : 將兩個 Treap a, b 進行合併成一個 Treap。
  • split a n : 將 Treap a 拆成前 n 小個元素為一個 Treap，剩餘為另一個 Treap。

插入一個元素相當於 split 一次，將兩個部分中間放置一個元素後，依序將其 merge 起來。

刪除一個元素相當於 split 兩次，將中間單一元素的 Treap 忽略，將第一和第三部分的 Treap merge 起來。

merge()

$\text{ treap merge(treap a, treap b) }$
  • 若 a, b 其中一個是 null treap，回傳另一個非空樹。
  • 若$key(a) \le key(b)$
    讓 a 的左子樹不變，而 a 的右子樹變成$merge(right(a), b)$ 的 treap 結果。
  • 若$key(a) > key(b)$
    讓 b 的右子樹不變，而 b 的左子樹變成$merge(a, left(b))$ 的 treap 結果。

split()

$< \text{treap, treap} > \text{ split(treap a, int n) }$
  • 若$size(left(a)) \le n \\ \left \{ l, r \right \} = split(left(a), n)$ ，並且將 a 的左子樹改成 r。返回結果$\left \{ l, a \right \}$
  • 若$size(left(a)) > n \\ \left \{ l, r \right \} = split(right(a), n - size(left(a)) - 1)$ ，並且將 a 的右子樹改成 l。返回結果$\left \{ a, r \right \}$

另解

在 g++ 头文件中，<ext/rope>中有成型的块状链表，在 using namespace __gnu_cxx; 空间中，其操作十分方便。

不用手刻，而且歷史版本的儲存速度也是 O(1)，裡面應該進行了很多記憶體控管。沒有細讀過，但是其支持相當厲害。看到這一篇代碼被不到百行的流程搞定。不過塊狀鏈表的複雜度仍然是$O(n^{1.5})$，比起隨機的可持久化 treap 還是慢了些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN (1<<23)
#define MAXQ 65536
struct node;
node *null;
struct node {
    node *lson, *rson;
    int key, size;
    char label; // user def label
    
    node(char c = 0, int s = 1):label(c), size(s) {
        lson = rson = null;
        key = rand();
    }
    void update() {
        size = 1;
        size += lson->size + rson->size;	
    }
} nodes[MAXN], *root[MAXQ];
struct treap {
    int bufIdx = 0;
    int prob_c; // this problem need.
    node* getNode(node* u) {
        node *ret;
        if (u == null) {
            return u;
        } else {
            ret = &nodes[bufIdx++];
            *ret = *u;
            return ret;
        }
    }
    node* merge(node* a, node* b) {
        if (a == null)	return getNode(b);
        if (b == null)	return getNode(a);
        node *ret;
        if (a->key < b->key) {
            ret = getNode(a);
            ret->rson = merge(a->rson, b);
        } else {
            ret = getNode(b);
            ret->lson = merge(a, b->lson);
        }
        ret->update();
        return ret;
    }
    void split(node* a, node* &l, node* &r, int n) {
        if (n == 0) {
            l = null, r = getNode(a);
        } else if (a->size <= n) {
            l = getNode(a), r = null;
        } else if (a->lson->size >= n) {
            r = getNode(a);
            split(a->lson, l, r->lson, n);
            r->update();
        } else {
            l = getNode(a);
            split(a->rson, l->rson, r, n - (a->lson->size) - 1);
            l->update();
        }
    }
    void build(node* &a, int l, int r, char s[]) {
        if (l > r)	return ;
        int m = (l + r) /2;
        node u = node(s[m]), *p = &u, *q;
        a = getNode(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();
    }
    void insert(node* &a, node *ver, int pos, char s[]) {
        node *p, *q, *r;
        int n = strlen(s);
        split(ver, p, q, pos);
        build(r, 0, n - 1, s);
        p = merge(p, r);
        a = merge(p, q);
    }
    void remove(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 print(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        if (ver->label == 'c')	prob_c++; // this problem need
        putchar(ver->label);
        print(ver->rson);
    }
    void printdebug(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        putchar(ver->label);
        print(ver->rson);
    }
    void traversal(node *ver, int pos, int n) {
        node *p, *q, *r;
        split(ver, p, q, pos - 1);
        split(q, q, r, n);
        print(q);
    }
    void init() {
        bufIdx = 0; 
        prob_c = 0;
        null = &nodes[bufIdx++];
        null->size = 0;
    }
} tree;
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        tree.init();
        int cmd, v, p, c, verIdx;
        char s[128];
        root[verIdx = 0] = null;
        for (int i = 0; i <= n; i++)
            root[i] = null;
        for (int i = 0; i < n; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %s", &p, s);
                p -= tree.prob_c;
                tree.insert(root[verIdx + 1], root[verIdx], p, s);
                verIdx++;
            } else if (cmd == 2) {
                scanf("%d %d", &p, &c);
                p -= tree.prob_c, c -= tree.prob_c;
                tree.remove(root[verIdx + 1], root[verIdx], p, c);
                verIdx++;
            } else {
                scanf("%d %d %d", &v, &p, &c);
                v -= tree.prob_c, p -= tree.prob_c, c -= tree.prob_c;
                tree.traversal(root[v], p, c);
                puts("");
            }
        }
    }
    return 0;
}
/*
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
*/
Read More +
解題區/解題區 - UVa

UVa 12821 - Double Shortest Paths

Problem

給一張圖，點與點之間有條有向路徑，每條路徑上有兩個權重，第一次從起點到終點經過這條邊時，消耗 d，而如果在第二次經過時，將消耗 d + a。保證 d <= d+a。(第二次經過同一條邊時，困難度會增加。)

求兩條從起點到終點的路徑花費最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10

Sample Output

1
2
Case 1: 23
Case 2: 24

Solution

直接套用最少費用流，對於輸入給定的一條邊 u->v，增加兩條容量為 1，路徑花費分別為 d 和 d+a，求起點到終點流量 = 2 的最少費用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[100005];
int e, head[505], dis[505], prev[505], record[505], inq[505];
void addEdge(int x, int y, int cap, int cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t) {
    int mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        int oo = dis[0];
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    prev[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] == oo)
            break;
        flow = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int n, m, cases = 0;
    int x, y, d, a;
    while(scanf("%d %d", &n, &m) == 2) {
        e = 0;
        memset(head, -1, sizeof(head));
        int source = n + 1, sink = n + 2;
        for (int i = 0; i < m; i++) {
        	scanf("%d %d %d %d", &x, &y, &d, &a);
        	addEdge(x, y, 1, d);
        	addEdge(x, y, 1, d + a);
        }
        addEdge(source, 1, 2, 0);
        addEdge(n, sink, 2, 0);
        printf("Case %d: %d\n", ++cases, mincost(source, sink));
    }
    return 0;
}
/*
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10
*/
Read More +
解題區/解題區 - UVa

UVa 12818 - Arc and Point

Problem

用三個點表示一弧，求一點到一弧最段距離。

Sample Input

1
2
0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1

Sample Output

1
2
Case 1: 1.414
Case 2: 4.000

Solution

Imgur

Imgur

先拉 AC 一線，計算 ABC 的外心 O，判斷 ABC 張角是否大於 180 度，利用 O、B 是否在 AC 同側或異側。

接著，分配兩側開始討論，參考方式如上圖。有三角形內部問題等 …

誤差問題仍然很嚴重，用三分解法肯定過不去，倒不如說卡在要怎麼三分參數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    Pt a, b, c, p;
    int cases = 0;
    while (scanf("%lf %lf", &a.x, &a.y) == 2) {
        scanf("%lf %lf", &b.x, &b.y);
        scanf("%lf %lf", &c.x, &c.y);
        scanf("%lf %lf", &p.x, &p.y);
        double ret = min(dist(p, a), dist(p, c));
        double a1, b1, c1;
        Pt o = circle(a, b, c);
        a1 = a.y - c.y, b1 = c.x - a.x, c1 = a1 * a.x + b1 * a.y; // line ac
//        printf("%lf %lf %lf\n", a1, b1, c1);
//        printf("%lf %lf\n", a1 * b.x + b1 * b.y - c1, a1 * p.x + b1 * p.y - c1);
//        printf("%lf %lf\n", o.x, o.y);
        if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * o.x + b1 * o.y - c1 > 0)) {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                    cross(c, o, p) * cross(c, a, p) < eps &&
                    cross(o, a, p) * cross(o, c, p) < eps) {
                } else {
                    if (d > r)
                        d -= r;
                    else
                        d = r - d;
                    ret = min(ret, d);
                }
            } else {
                if (cross(o, a, p) * cross(o, c, p) > -eps) {
                    d = d - r;
                    ret = min(ret, d);
                }
            }
        } else {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
            	if (cross(o, a, p) * cross(o, c, p) < eps) {
                    if (d > r)
                        d -= r;
                    else
                        d = r - d;
                    ret = min(ret, d);
            	}
            } else {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                        cross(c, o, p) * cross(c, a, p) < eps &&
                        cross(o, a, p) * cross(o, c, p) < eps) {
                    d = r - d;
                    ret = min(ret, d);
                }
            }
        }
        assert(ret >= 0);
        printf("Case %d: %.3lf\n", ++cases, ret + eps);
    }
    return 0;
}
/*
 4 -2 -2 4 -4 -2 -1 3 
 4 -2 -2 4 -4 -2 1 3
 4 -2 -2 4 -4 -2 -3 5 
 4 -2 -2 4 -4 -2 3 5
 4 -2 -2 4 -4 -2 -3 1
 4 -2 -2 4 -4 -2 -5 1 
 4 -2 -2 4 -4 -2 -1 -1
 4 -2 -2 4 -4 -2 -1 -3 
 4 -2 -2 4 -4 -2 0 0 
 
 -4 3 0 5 4 3 9 4 
 -4 3 0 5 4 3 -9 4
 -4 3 0 5 4 3 10 3
 -4 3 0 5 4 3 -4 5
 -4 3 0 5 4 3 8 2
 -4 3 0 5 4 3 1 2
 -4 3 0 5 4 3 1 -2
 -4 3 0 5 4 3 2 1
 0 0 1 1 2 0 1 -1
 
 3 4 0 5 -3 4 0 1
 3 4 0 5 -3 4 0 4.5
 3 4 0 5 -3 4 1 3
 3 4 0 5 -3 4 -3 3
 3 4 0 5 -3 4 0 -1
 
 -1 -1 0 3 1 -1 1 1
 -1 -1 0 3 1 -1 -2 -1
 -1 -1 0 3 1 -1 0 0
 -1 -1 0 3 1 -1 0 -1
 -1 -1 0 3 1 -1 0 -2
 
 2 0 0 2 -2 0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12685 - Binary Tree

Problem

根據第一行指令，在一個二元樹中走訪節點，最後停留的位置交給第二行繼續執行。然而第二行的每一個指令可以選擇忽略或者執行，最後停留的節點共計有多少個。

Sample Input

1
2
3
4
5
2
L
LU
L
L

Sample Output

1
2
Case 1: 3
Case 2: 2

Solution

一開始會發現最後停留的點，下次可能抵達的位置為其左子樹節點個數 1、右子樹節點個樹 1。

定義：可能在下一個走到的左子節點個數 l、右子節點個數 r。

當選擇往左前往還沒有走過的左子節點時，所有左子節點各會增加可能未走到的左子節點、右子節點，而已經消耗 l 個未走過的左節點，現在增加 l 個未走過的左節點、l 個未走過的右節點。反之，走到右子節點也是。

如果選擇往上時，只會根據一開始停留點到 root 之間的距離有關。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h> 
#include <stack>
using namespace std;
char S[131072], T[131072];
const int mod = 21092013;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s %s", S, T);
        stack<char> stk;
        for (int i = 0; S[i]; i++) {
            if (S[i] == 'L' || S[i] == 'R')
                stk.push(S[i]);
            else if (!stk.empty())
                stk.pop();
        }
        int ret = 1, lson = 1, rson = 1;
        for (int i = 0; T[i]; i++) {
            if (T[i] == 'L')
                ret = (ret + lson)%mod, rson = (rson + lson)%mod;
            else if (T[i] == 'R')
                ret = (ret + rson)%mod, lson = (lson + rson)%mod;
            else {
                if (!stk.empty()) {
                    ret = (ret + 1)%mod;
                    if (stk.top() == 'L')
                        rson++;
                    else
                        lson++;
                    stk.pop();
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11964 - Equation

Problem

$x_{1} + 2 x_{2} + 4 x_{3} + 8 x_{4} + 16 x_{5} + ... + 2^{t} x_{t}= K \text{ where } x_{i} \geq 0$

找到所有組合數並且 mod M 的結果，其中 M 可以拆成數個小於 150 的質因數分解。

Sample Input

1
2
3
4
3
15 99
101 123
1234 536870912

Sample Output

1
2
3
Case 1: 26
Case 2: 111
Case 3: 176223474

Solution

其中 M 可以拆成數個小於 150 的質因數分解。

這句話可說是暗藏玄機，由於測資組數太多，對於每次 mod 情況都建表太慢。不然這題單純套用硬幣問題就能計算個數收尾。

因此，先將 M 進行質因數分解$M = \prod_{i} p_{i}^{x_{i}}$，之後用中國餘式定理求解。

由於質因數的個數可能大於 1，那其實也可以發現$\text{count mod } p_{i}$ 和$\text{count mod } p_{i - 1}$ 之間的關係$\text{count mod } p_{i-1} = \text{count mod } p_{i} \text{ mod } p_{i-1}$。

這裡可以 O(1) 算出來，而在 150 以內總共有 35 個質數，分別對這些質數計算出 mod 盡可能大$p_{i} \le 10^{15}$ 為準。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <vector>
using namespace std;
#define maxL (150>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[150], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 150;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long mulmod(long long a, long long b, long long mod) {
    long long ret = 0;
    for ( ; b != 0;b>>=1, (a<<=1) %= mod)
        if (b&1)	(ret += a) %= mod;
    return ret;
}
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
long long chinese_remainder(int n, long long m[], long long a[]) {
    long long M = 1, ret = 0;
    for(int i = 0; i < n; i++)
        M *= m[i];
    for(int i = 0; i < n; i++) {
        ret += a[i] * inv(M/m[i], m[i]) %M * (M/m[i]);
        ret %= M;
    }
    return (ret%M + M)%M;
}
vector< pair<int, int> > factor(long long n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
long long mpow(long long x, long long y) {
    long long ret = 1;
    for (int i = 0; i < y; i++)
        ret *= x;
    return ret;
}
vector<long long> dp[37];
int main() {
    sieve();
    for (int i = 0; i < Pt; i++) {
        long long m = P[i];
        int p = 0;
        for (m = P[i], p = 0; m * P[i] <= 1e+15; p++, m *= P[i]);
        dp[i].resize(100005, 0);
        dp[i][0] = 1;
        for (int j = 1; j <= 100000; j <<= 1) {
            for (int k = j; k <= 100000; k++)
                dp[i][k] = (dp[i][k] + dp[i][k - j])%m;
        }
    }
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int K;
        long long M;
        scanf("%d %lld", &K, &M);
        vector< pair<int, int> > f = factor(M);
        long long m[35], a[35];
        for (int i = 0; i < f.size(); i++) {
            for (int j = 0; j < Pt; j++)
                if (f[i].first == P[j])
                    m[i] = mpow(P[j], f[i].second), a[i] = dp[j][K] % m[i];
        }
        long long ret = chinese_remainder(f.size(), m, a);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11972 - Round Trip

Problem

給一張圖，從起點 c 出發，每一條邊最多經過一次，最後回到 c。中間可以經過哪些節點。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
6 7 1
1 2
1 3
2 6
4 6
2 5
5 3
4 2
2 1 2
1 2

Sample Output

1
2
Case 1: 2 3 4 5 6
Case 2: none

Solution

窮舉所有可能做最大流，從起點 c 到指定的點 v，如果存在最大流 maxflow >= 2 表示至少兩條，因此可以拉成一個環，表示 v 可以在環上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
#define MAXN 128
struct Node {
    int x, y;
    int cap, flow;// x->y, v
    int next;
} edge[10005];
int e, head[MAXN], prev[MAXN], record[MAXN];
int level[MAXN], visited[MAXN];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = v, edge[e].flow = 0;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].flow = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].cap > edge[i].flow && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].cap > edge[i].flow) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 0x3f3f3f3f, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].cap - edge[ri].flow);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].flow += flow;
                edge[ri^1].flow -= flow;
                if(edge[ri].cap - edge[ri].flow == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
vector<int> maxflowCut(int s, int t, int n) {
    buildLevelGraph(s, t);
    vector<int> ret;
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j != -1; j = edge[j].next) {
            if (level[edge[j].x] && !level[edge[j].y] && edge[j].cap > 0 && edge[j].cap == edge[j].flow)
                ret.push_back(j);
        }
    }
    return ret;
}
int clearflow() {
    for (int i = 0; i < e; i++)
        edge[i].flow = 0;
}
int main() {
    int n, m, c;
    int x, y, v;
    int cases = 0;
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d %d", &n, &m, &c);
        e = 0;
        memset(head, -1, sizeof(head));
        for(int i = 0; i < m; i++) {
        	scanf("%d %d", &x, &y);
        	addEdge(x, y, 1);
        	addEdge(y, x, 1);
        }
        printf("Case %d: ", ++cases);
        int f = 0;
        for (int i = 1; i <= n; i++) {
        	if (i == c)	continue;
        	clearflow();
        	int flow = maxflowDinic(c, i);
        	if (flow >= 2) {
        		if (f)	putchar(' ');
        		printf("%d", i);
        		f = 1;
        	}
        }
        if (f == 0)
        	puts("none");
        else
        	puts("");
    }
    return 0;
}
/*
2
6 7 1
1 2
1 3
2 6
4 6
2 5
5 3
4 2
2 1 2
1 2
*/
Read More +
解題區/解題區 - UVa

UVa 12812 - The Largest Diamond-Shaped Kite

Problem

找一個最大箏形於給定的地圖中。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3 3
.#.
###
.#.
8 10
..##...#..
.###..###.
..#.......
....##....
....######
...#####..
..########
.....#....

Sample Output

1
2
3
5

Solution

其實很像找一個最大正方形，可以參考 NPSC 營地的作法。而要求箏形事實上就是將地圖翻轉 45 度角。

參考 UVa 10593 - Kites 的做法可以完成。

以前寫的 代碼 真是萌哒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
char g[512][512];
int dp[512][512];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%s", g[i]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '#') {
                    int v1, v2, v3;
                    v1 = i-1 >= 0 && j-1 >= 0 ? dp[i-1][j-1] : 0;
                    v2 = i-2 >= 0 ? dp[i-2][j] : 0;
                    v3 = i-1 >= 0 && j+1 < m ? dp[i-1][j+1] : 0;
                    if (i-1 >= 0 && g[i-1][j] == '#')
                        dp[i][j] = min(v1, min(v2, v3)) + 1;
                    else
                        dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        printf("%d\n", ret * 2 - 1 < 0 ? 0 : ret * 2 - 1);
    }
    return 0;
}
/*
 2
 3 3
 .#.
 ###
 .#.
 8 10
 ..##...#..
 .###..###.
 ..#.......
 ....##....
 ....######
 ...#####..
 ..########
 .....#....
 */
Read More +
解題區/解題區 - UVa

UVa 12811 - The Turtle's Journey

Problem

  • left X
  • right X
  • forward X
  • repeat N [ INST ]

上述總共有四種指令架構，分別輸出前三個指令的 X 總和值。其中第四個為迴圈架構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end

Sample Output

1
2
360 0 40
360 0 40

Solution

由於輸入沒有迴圈，差點忘了有 repeat 指令。遞迴讀進輸入即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
const long long mod = 1000003;
char s[128];
void dfs(long long cmd[]) {
    scanf("%s", s);
    if (s[0] == 'e' || s[0] == ']')    return;
    long long x, ncmd[3] = {};
    scanf("%lld", &x);
    if (s[0] == 'l')
        cmd[0] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'i')
        cmd[1] += x, dfs(ncmd);
    else if (s[0] == 'f')
        cmd[2] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'e'){
        scanf("%*s");
        dfs(cmd);
        for (int i = 0; i < 3; i++)
            cmd[i] = (cmd[i] * x) %mod;
        dfs(ncmd);
    }
    for (int i = 0; i < 3; i++)
        cmd[i] = (cmd[i] + ncmd[i]) %mod;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%*s");
        long long cmd[3] = {};
        dfs(cmd);
        printf("%lld %lld %lld\n", cmd[0], cmd[1], cmd[2]);
    }
    return 0;
}
/*
 2
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end */
Read More +
解題區/解題區 - UVa

UVa 12810 - Sumthing

Problem

$$S(1) = \sum_{i=1}^{n} A[i] \\ S(2) = 2 \sum_{i=1}^{n} \sum_{j=i+1}^{n} A[i] A[j] \\ S(3) = 2^{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} A[i] A[j] A[k] \\ ...$$

將 S(1) … S(n) 加總後 mod 1000000009 輸出。

Sample Input

1
2
3
4
5
2
3
1 2 3
5
2 3 5 7 11

Sample Output

1
2
52
66412

Solution

特別發現到 1000000009 是質數，對於任意一個數字都存在乘法反元素，那麼將總和定義為

$(1 + 2 A[0])(1 + 2 A[1])(1 + 2 A[2]) ... (1 + 2 A[n])/2 \text{ mod } 1000000009$

/2 部分利用乘上 2 在 mod 1000000009 下的反元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h> 
const long long mod = 1000000009LL;
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
} 
int main() {
    int testcase, n;
    long long div2 = mpow(2, mod-2, mod);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long p = 1, x;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            p *= (1 + x * 2);
            p %= mod;
        }
        p = ((p - 1) * div2)%mod;
        printf("%lld\n", p);
    }
    return 0;
}
Read More +