解題區/解題區 - UVa

UVa 12874 - Blanket

Problem

寒冷的冬天，為街道上的人鋪設毛毯，現在有 n 個無限長毛毯，每一個毛毯都有其紋路，呈現厚薄厚薄厚薄 … 的順序，其中厚的長度為 ai，而薄的長度為 bi - ai。

現在長度為 1…m 的街道，請問蓋到 1 件、2 件、3 件、 …、n 件薄毛毯的人分別有多少人。

Sample Input

1
2
3
4
5
1
3 30
2 5
3 5
3 6

Sample Output

1
2
3
4
6
9
9
6

Solution

看到 ai, bi <= 16。

窮舉每個人，O(16) 計算蓋到幾件薄毛毯。

如果用 O(nm) 顯然太慢，由於 bi 很小，針對所有可能，預建表得到循環下累計結果。

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
#include <stdio.h> 
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int ret[131072];
int main() {
    int testcase, n, m;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        int A[20][20] = {}, a, b;
        for (int i = 0; i < n; i++) {
//			scanf("%d %d", &a, &b);
            ReadInt(&a);
            ReadInt(&b);
            A[b][a]++;
        }
        for (int i = 1; i <= 16; i++) {
            for (int j = 1; j <= 16; j++)
                A[i][j] += A[i][j-1];
        }
        for (int i = 0; i <= n; i++)
            ret[i] = 0;
        for (int i = 0; i < m; i++) {
            int cover = 0;
            for (int j = 1, t; j <= 16; j++) {
                t = i%j;
                cover += A[j][16] - A[j][t];
            }
            ret[cover]++;
        }
        for (int i = 0; i <= n; i++)
            printf("%d\n", ret[i]);
    }
    return 0;
}
/*
9999
3 30
2 5
3 5
3 6
2 15
1 2
3 4
*/
Read More +
解題區/解題區 - UVa

UVa 12846 - A Daisy Puzzle Game

Problem

有一套撥花瓣遊戲，一朵花有 n 片花瓣，每一片花瓣分別位置在 1…n，呈現環狀，首尾相連。兩個人輪流撥花瓣，每一次撥一片、或者撥相鄰的兩片，最後一個取走花瓣的人輸。

給已經撥去花瓣，請問現在她先手會不會勝利？

Sample Input

1
2
3
4
5
2
13 1
7
5 3
1 3 4

Sample Output

1
2
Case 1: yes
Case 2: no

Solution

看出是一道 SG 博奕遊戲，假設有 n 個連續花瓣，取中間一片、或連續兩片，將會變成兩段連續花瓣，藉此建造 SG 函數，求出連續 n 個連續花瓣的 SG 值，隨後統計有多少段連續花瓣，並且各自擁有多少花瓣，接著套用 nim 遊戲得到結果。

特別小心是環狀的，題目沒有描述得很清楚。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int SG[1024];
void buildSG() {
    int mex[1024] = {};
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 0; j < i; j++) {
            mex[SG[j] ^ SG[i-j-1]] = 1;
            if (i-j-2 >= 0)
                mex[SG[j] ^ SG[i-j-2]] = 1;
        }
        int sg = 0;
        for (sg; mex[sg]; sg++);
        SG[i] = sg;
    }
}
int main() {
    buildSG();
    int testcase, cases = 0, n, m, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        int used[64] = {}, last = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            x--;
            used[last = x] = 1;
        }
        
        vector<int> nim;
        for (int i = 0, tmp = 0, pos; i < n; i++) {
            pos = (last + i)%n;
            if (used[pos] == 0)
                tmp++;
            if (used[pos] || i == n-1) {
                if (tmp)
                    nim.push_back(tmp);
                tmp = 0;
            }
        }
        
        int ret = 0;
        for (int i = 0; i < nim.size(); i++)
            ret ^= SG[nim[i]];
        printf("Case %d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
/*
9999
13 1
7
5 3
1 3 4
6 2
1 5
1 1
1
1 0
*/
Read More +
解題區/解題區 - UVa

UVa 12837 - Hasmot Ali Professor

Problem

給定一個主字串 S，接著數筆詢問有多少不同的子字串以 X 開頭、Y 結尾。

Sample Input

1
2
3
4
5
6
1
abab
3
a a
a b
ba ab

Sample Output

1
2
3
4
Case 1:
2
2
1

Solution

由於題目是要找不同的子字串，必然會造成比對速度上的問題，由於主子串長度最多 1000，而詢問的 X、Y 長度都小於 10，顯然地窮舉是相當有利。但是詢問次數最多 50000，窮舉起來必須有效率地映射到答案中，因此建議離線把詢問建成一個 Trie，同時避免重複的詢問。

窮舉每個子字串，為了加速匹配，最多跑 O(len * len * 10 * 10)，當決定子字串為 [l, r] 時，遞增起頭指針、遞減結尾指針，對於每一組詢問串成 X#inv(Y)，那麼只需要循序走訪一棵 trie，如此一來速度就提升了不少。

接著考慮如何去重複，關鍵點在於窮舉每個子字串，也依序插入 trie 中，當有新增新的節點時再進行答案的驗證。

也許這類型的題目可以先建造一個 suffix tree，然後想辦法詢問，仔細想想不容易就放棄。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct TrieNode {
    int n;
    int link[27];
} Node[1048576<<2];
int TrieSize;
int rename(char c) {
    if ('a' <= c && c <= 'z')
        return c - 'a';
    return 26;
}
void insertTrie(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
}
TrieNode* getTrieNode(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
    return &Node[idx];
}
const int MAXQL = 10 - 1;
const int MAXQ = 50000;
char ms[MAXQ][32];
int main() {
    int testcase, q, cases = 0;
    char s1[32], s2[32], s[1024];
    int A[1024], B[1024];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%s", s);
        scanf("%d", &q);
        int sn = strlen(s), s1n, s2n, an, bn;
        TrieSize = 2;
        int root1 = 0, root2 = 1;
        memset(&Node[root1], 0, sizeof(Node[root1]));
        memset(&Node[root2], 0, sizeof(Node[root2]));
        for (int i = 0; i < q; i++) {
            scanf("%s %s", s1, s2);
            s1n = strlen(s1), s2n = strlen(s2);
            int m = 0;
            for (int j = 0; j < s1n; j++)
                ms[i][m++] = s1[j];
            ms[i][m++] = '#';
            for (int j = s2n - 1; j >= 0; j--)
                ms[i][m++] = s2[j];
            ms[i][m] = '\0';
            insertTrie(ms[i], root2);
        }
        
        for (int i = 0; i < sn; i++) {
            int idx = root1, idx2, c;
            for (int j = i; j < sn; j++) { // add s[l, r]
                c = rename(s[j]);
                if(Node[idx].link[c] == 0) {
                    TrieSize++;
                    memset(&Node[TrieSize], 0, sizeof(Node[0]));
                    Node[idx].link[c] = TrieSize;
                    // create new node == create distinct substring
                    int idx2 = root2;
                    int L = min(j, i + MAXQL);
                    for (int k = i; k <= L; k++) { // brute head
                        if (Node[idx2].link[rename(s[k])] == 0)	break;
                        idx2 = Node[idx2].link[rename(s[k])];
                        if (Node[idx2].link[rename('#')]) {
                            int idx3 = Node[idx2].link[rename('#')];
                            int R = max(i, j - MAXQL);
                            for (int l = j; l >= R; l--) { // brute tail
                                if (Node[idx3].link[rename(s[l])] == 0)	break;
                                idx3 = Node[idx3].link[rename(s[l])];
                                Node[idx3].n ++; // [l, r] = strA + ... + strB
                            }
                        }
                    }
                }
                idx = Node[idx].link[c];
            }
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            TrieNode *p = getTrieNode(ms[i], root2);
            printf("%d\n", p->n);
        }
    }
    return 0;
}
/*
1
abab
3
a a
a b
ba ab
*/
Read More +
解題區/解題區 - UVa

UVa 12875 - Concert Tour

Problem

現在有位歌手，要舉辦演唱會，在各地的百貨公司打算邀請歌手來演唱，藉以吸引更多的顧客來消費。每個百貨公司提供在哪一天歌手來演唱時可以得到的獲益，歌手必須自費從另一個地點到另一個地點，因此會給定兩地之間的自費費用。可以留在原地。

求歌手在 m 天內可以獲得的最大利益為何，假設第一天到任何場地都是 0 花費，沒有指派最後一天所在的位置。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3
3 4
1 3 20 40
50 20 1 2
20 50 50 1
0 10 10
10 0 10
10 10 0
3 3
20 20 20
20 20 20
20 20 20
0 20 40
20 0 40
40 10 0
2 4
10 20 10 20
20 10 20 10
0 5
5 0

Sample Output

1
2
3
170
60
65

Solution

定義狀態 dp[stores][days]，在第幾天到哪一個城鎮。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 128
#define MAXM 64
long long dp[MAXN][MAXM];
int profit[MAXN][MAXM], cost[MAXN][MAXN];
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &profit[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &cost[i][j]);
                
        memset(dp, 0, sizeof(dp));
        
        long long ret = 0;
        for (int i = 0; i < n; i++)
            dp[i][0] = profit[i][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[k][i+1] = max(dp[k][i+1], dp[j][i] + profit[k][i+1] - cost[j][k]);
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = max(ret, dp[i][m-1]);
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12887 - The Soldier's Dilemma

Problem

N 個人不同高，現在佔一排，任挑三個人的身高從左向右的相對高度，不存在矮、高、中的情況有多少種。

Sample Input

1
2
3
2
2
3

Sample Output

1
2
2
5

Solution

卡塔蘭數 (Catalan number)。

每一次考慮加入一個最高的人，窮舉最高的人應該佔在哪個位置，則其左、右側也要滿足定義，同時左側的人都要比右側的人高。最後得到公式如下，與卡塔蘭數相同。

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
#include <stdio.h> 
/*
add tallest people in position i
ways[n] = \sum ways[i] * ways[n-i-1].
			   ^^^^^^[1] ^^^^^^^^^^[2]
[1] left tree pos[0, i-1]
[2] right tree pos[i+1, n-1]
then label of right tree must small than label of left tree
=> Catalan number, an = (4n-2)/(n+1) * an-1
*/
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;
}
#define MAXN 5005
long long Catalan[MAXN];
const long long mod = 1000000007LL;
int main() {
    Catalan[0] = Catalan[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        Catalan[i] = Catalan[i-1] * (4 * i - 2) %mod;
        Catalan[i] = Catalan[i] * inv(i+1, mod) %mod;
    }
    int n, testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%lld\n", Catalan[n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12880 - Book Club

Problem

有 N 個人的愛書俱樂部，他們會喜歡某些人的書，如果相互喜歡對方的書就可以進行交換，現在要問的是否每個人都能找到能夠交換的對象，讓每個人都獲得新書。

如果 A -> B, B -> C, C -> A，那麼他們可以環狀地交換新書。

Sample Input

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

Sample Output

1
YES

Solution

每個人只能找一個對象進行交換，找二分圖的 perfect matching。

二分圖中左側是每個人，右側是想要交換的對象，兩邊的個數都是 N。匹配完會找到數個環狀，這就是最後的交換情況。然而由於點數很多，用匈牙利算法可以減枝來加快，每一次擴充路徑都必須得成功。如果使用 maxflow，則盡可能減少邊的無效使用。

當然可以使用 maxflow 貪心預流、匈牙利貪心匹配過後，再套用算法，速度有可能會快上許多，以下的模板還真好用，減少無效使用於分層圖，所以速度快上很多。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        g.Init(2 * n + 2);
        int source = 2 * n, sink = 2 * n + 1;
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, y + n, 1);
        }
        
        int matching = g.Maxflow(source, sink);
        puts(matching == n ? "YES" : "NO");
    }
    return 0;
}
/*
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
*/
Read More +
解題區/解題區 - UVa

UVa 12878 - Flowery Trails

Problem

在國家公園的步行路道上要在兩側放置花卉，而主辦單位認為只要在其中兩個重要景點的最短路徑上的道路放置即可。通常大部分人只會走最短路徑。

請問總花費為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

Sample Output

1
2
3860
18

Solution

最短路徑可能有數條，因此要窮舉每一條邊是否在最短路徑上，已知景點分別為 st 和 ed ，那麼找到 st -> u 和 ed -> v 的單源最短路徑，接下來窮舉 u -> v ，加上 st -> u 和 v -> ed ，得到 st -> u -> v -> ed 的最少花費，檢查是否等於最短路徑長即可。

這一題是雙向圖，如果是單向圖則要反轉邊，才能對 ed 進行單源最短路徑 (SSSP)。在這一題寫 SSSP 使用 SPFA 算法，也許 dijkstra 也是挺不錯的。

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
 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
#define MAXN 32767
vector< pair<int, int> > g[MAXN];
int dist1[MAXN], dist2[MAXN];
void spfa(int st, int ed, int dist[]) {
    static int inq[MAXN];
    queue<int> Q;
    int u, v, w;
    dist[st] = 0, Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v])
                    inq[v] = 1, Q.push(v);
            }
        }
    }
}
int main() {
    int n, m;
    int x, y, w;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(make_pair(y, w));
            g[y].push_back(make_pair(x, w));
        }
        
        for (int i = 0; i < n; i++)
            dist1[i] = dist2[i] = 0x3f3f3f3f;
        spfa(0, n-1, dist1);
        spfa(n-1, 0, dist2);
    
        int sp = dist1[n - 1], ret = 0;
        for (int i = 0; i < n; i++) {
            x = i;
            for (int j = 0; j < g[i].size(); j++) {
                y = g[i][j].first, w = g[i][j].second;
                if (dist1[x] + w + dist2[y] == sp)
                    ret += w;
            }
        }
        printf("%d\n", ret * 2);
    }
    return 0;
}
/*
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12876 - City

Problem

現在給定格子狀的街區，每一個街區只會與垂直、水平的相鄰街區有通行的人行道。現在已知每個街區有多少人行道，求未知的街區人行道數量情況。

Sample Input

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

Sample Output

1
1

Solution

二分圖黑白染色，知道每一個只會與相鄰上下左右的街區相鄰，那麼就像國際象棋一樣的黑白染色，相鄰的人行道一定只會連接於黑跟白之間。

分別計算黑和白的 degree 總數，差的絕對值就是未知街區的答案。

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
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
using namespace std;
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int testcase, n, m, x;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
//				scanf("%d", &x);
                ReadInt(&x);
                if (x == -1)	continue;
                if ((i+j)&1)
                    odd += x;
                else
                    even += x;
            }
        } 
        printf("%d\n", abs(odd - even));
    }
    return 0;
}
/*
1
3 3
2 2 3
1 -1 3
1 1 0
*/
Read More +
解題區/解題區 - UVa

UVa 10266 - Surveying

Problem

從隨機幾點進行觀察，可以知道其相對高度。

現在給定數組觀察的部分紀錄，求在某一點的觀察的數據，如果可以得到完整的則輸出整個地圖的相對高度，如果不齊全、或者發生矛盾，則參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
1 2
1 1 10 1 2 10
1 2 20 2 2 30 2 1 30
2 2
1 1
1 1 10 1 2 10
2 2
1 2
1 1 10 1 2 10
1 1 20 1 2 30

Sample Output

1
2
3
4
5
6
0 0
10 10
the lack of measurements
conflicting measurements

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
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
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 128
vector<int> g[MAXN][MAXN];
struct Survey {
    int x, y, h;
    Survey(int a = 0, int b = 0, int c = 0):
    x(a), y(b), h(c) {}
};
vector< vector<Survey> > D;
int n, m;
int spfa(int sx, int sy) {
    int ret[MAXN][MAXN], used[MAXN][MAXN] = {};
    vector<int> sid;
    sid.resize(D.size(), 0);
    int x, y, h, id, tx, ty;
    queue<int> X, Y, ID;
    used[sx][sy] = 1, ret[sx][sy] = 0;
    for (int i = 0; i < g[sx][sy].size(); i++) {
        int u = g[sx][sy][i];
        X.push(sx), Y.push(sy), ID.push(u);
        sid[u] = 1;
    }
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        id = ID.front(), ID.pop();
        int shift = 0;
        for (int i = 0; i < D[id].size(); i++) {
            if (D[id][i].x == x && D[id][i].y == y) {
                shift = ret[x][y] - D[id][i].h;
                break;
            }
        }
        for (int i = 0; i < D[id].size(); i++) {
            tx = D[id][i].x, ty = D[id][i].y;
            h = D[id][i].h + shift;
            if (used[tx][ty] && h != ret[tx][ty])
                return 0;
            ret[tx][ty] = h;
            if (used[tx][ty] == 0) {
                used[tx][ty] = 1;
                for (int j = 0; j < g[tx][ty].size(); j++) {
                    int u = g[tx][ty][j];
                    if (sid[u]) continue;
                    X.push(tx), Y.push(ty), ID.push(u);
                    sid[u] = 1;
                }
            }
        }
    }
    
    int ok = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ok &= used[i][j];
        }
    }
    if (ok) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%d%c", ret[i][j], j == m ? '\n' : ' ');
            }
        }
    } else {
        puts("the lack of measurements");
    }
    return 1;
}
char line[1048576 * 8];
int main() {
    int testcase, bx, by;
    int x, y, h;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        scanf("%d %d", &bx, &by);
        while (getchar() != '\n');
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                g[i][j].clear();
        D.clear();
        while (gets(line)) {
            if (line[0] == '\0')   break;
            stringstream sin(line);
            int id = (int) D.size();
            vector<Survey> item;
            while (sin >> x >> y >> h) {
                item.push_back(Survey(x, y, h));
                g[x][y].push_back(id);
            }
            D.push_back(item);
        }
        int f = spfa(bx, by);
        if (!f) {
            puts("conflicting measurements");
        }
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 3
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 2 2 30 2 1 30
 
 2 2
 1 1
 1 1 10 1 2 10
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 1 2 30
 */
Read More +
解題區/解題區 - UVa

UVa 10253 - Series-Parallel Networks

Problem

給定 N 條邊，去除掉同構的情況，請問有多少個不同的串并連網路。

Sample Input

1
2
3
4
1
4
15
0

Sample Output

1
2
3
1
10
1399068

Solution

首先，拆分結果可以依序按照串－并－串－并 … 或者并－串－并－串 …

這樣會形成樹圖，其中奇數層是串/并，而偶數層是并/串，如此一來，要找到 N 個葉節點的樹有多少不同種的。根據兩種不同的分層方式，隨後乘上 2 就是答案。

定義 dp[i][j] 表示總共有 j 個葉節點的樹，並且每個子樹的葉節點最多 i 個 (至少)。這麼定義有它的好處，而不去直接定義 恰好 。

接著組合其具有 k 個樹－其子樹最多 i 個葉節點，剩下不足的葉節點，弄成一個樹，使用重複排列防止重複的計算。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
long long dp[32][32] = {};
/*
parallel/series
consider parallel/series operation -> node, 
n-edge == counting number of tree with n-leaf node.
dp[i][j]: at most i-leaves in subtree, total j-leaves.
dp[i][j] = \sum C(ret[i] + k - 1, k) \times dp[i-1][j - i*k]
				^^^^^^^^^^^^^^^^^^^^[1]		^^^^^^^^^^^^^^^[2]
[1]: pick k subtree with at most (i-1)-leaves, total i-leaves
[2]: a subtree with at most (i-1)-leaves, total (j-i*k)-leaves
*/
long long C(long long n, long long m) {
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++)
        ret = ret * (n + 1 - i) / i;
    return ret;
}
int main() {
    
    long long ret[32] = {};
    ret[1] = 1;
    for (int i = 1; i <= 30; i++)
        dp[0][i] = 0, dp[i][1] = 1;
    for (int i = 0; i <= 30; i++)
        dp[i][0] = 1;
    for (int i = 1; i <= 30; i++) {
        for (int j = 2; j <= 30; j++) {
            for (int k = 0; i * k <= j; k++) {
                dp[i][j] += C(ret[i] + k - 1, k) * dp[i-1][j - i*k];
            }
        }
        ret[i+1] = dp[i][i+1];
    }
    
    int n;
    while (scanf("%d", &n) == 1 && n)
        printf("%lld\n", n == 1 ? 1 : ret[n] * 2);
    return 0;
}
Read More +