解題區/解題區 - UVa

UVa 12118 - Inspector's Dilemma

Problem

將一個無向圖中，增加最少條邊，使得可以使用尤拉路徑或環道經過所有條邊。

Sample Input

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

Sample Output

1
2
Case 1: 4
Case 2: 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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int parent[1024], weight[1024];
int deg[1024];
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;
}
int main() {
    int cases = 0;
    int N, M, T, x, y;
    while (scanf("%d %d %d", &N, &M, &T) == 3 && N+M+T) {
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, deg[i] = 0;
        
        int component = N;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            deg[x]++, deg[y]++;
            if (joint(x, y))
                component--;
        }
        
        for (int i = 1; i <= N; i++) {
            if (weight[i] == 1 && findp(i) == i)
                component--;
        }
        int ret = M, odd[1024] = {};
        ret += component > 0 ? component - 1 : 0;
        for (int i = 1; i <= N; i++) {
            if (deg[i]&1)
                odd[findp(i)]++;
        }
        for (int i = 1; i <= N; i++) {
            if (odd[i] >= 4)
                ret += odd[i]/2 - 1;
        }
        printf("Case %d: %d\n", ++cases, ret * T);
    }
    return 0;
}
/*
 5 3 1
 1 2
 1 3
 4 5
 
 4 4 1
 1 2
 1 4
 2 3
 3 4
 0 0 0
 */
Read More +
解題區/解題區 - UVa

UVa 12096 - The SetStack Computer

Problem

將集合做交集、聯集、插入的操作，輸出每次操作的集合大小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
0
1
0
1
1
2
2
2
***
0
0
1
0
0
***

Solution

STL 高招解決，都有提供集合交集和聯集，但是為了方便查找，使用重新命名每一個集合為一個整數表示。

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
#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;
map< set<int>, int > R;
map<int, set<int> > mR;
int rename(set<int> s) {
    int &ret = R[s];
    if (ret == 0)
        ret = (int)R.size(), mR[ret] = s;
    return ret;
}
int main() {
    int testcase, n;
    int a, b;
    char cmd[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (!strcmp(cmd, "PUSH")) {
                stk.push(rename(set<int>()));
            } else if(!strcmp(cmd, "DUP")) {
                stk.push(stk.top());
            } else if(!strcmp(cmd, "UNION")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> &A = mR[a], &B = mR[b], C;
                set_union(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
                stk.push(rename(C));
            } else if(!strcmp(cmd, "INTERSECT")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> &A = mR[a], &B = mR[b], C;
                set_intersection(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()));
                stk.push(rename(C));
            } else if(!strcmp(cmd, "ADD")) {
                a = stk.top(), stk.pop();
                b = stk.top(), stk.pop();
                set<int> B = mR[b];
                B.insert(a);
                stk.push(rename(B));
            }
            printf("%d\n", (int)mR[stk.top()].size());
        }
        puts("***");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12092 - Paint the Roads

Problem

給一張無向圖，希望每一個點都剛好在 K 個不相交環上，如果不可能則輸出 -1，反之挑選最少花費的邊構成這一個條件。

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
25
26
27
28
29
30
31
32
33
34
35
36
4
4 8 1
0 1 1
1 0 2
2 3 1
3 2 2
0 2 5
2 0 6
1 3 5
3 1 6
4 8 1
0 1 1
1 0 10
2 3 10
3 2 1
0 2 10
2 0 1
1 3 1
3 1 10
4 8 2
0 1 1
1 0 2
2 3 1
3 2 2
0 2 5
2 0 6
1 3 5
3 1 6
3 4 1
0 1 5
1 0 6
0 2 7
2 0 8

Sample Output

1
2
3
4
6
4
28
-1

Solution

一道明顯的最小費用流，每一條邊最高流量是 1，而對於每個點都通過 K 個不相交環 (沒有共同邊)，則要將每個點拆分成出入兩點，也就是說總共會有 N K 個不相交的環，總流量會經過 N K 條邊。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 128
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[100005];
int e, head[MAXN], dis[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
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 &totflow) {
    totflow = 0;
    int mncost = 0, flow;
    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;
                    pre[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 = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = pre[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 testcase, N, M, K;
    int x, y, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        e = 0;
        memset(head, -1, sizeof(head));
        int source = 2 * N, sink = 2 * N + 1;
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &x, &y, &v);
            addEdge(2 * x, 2 * y + 1, 1, v);
        }
        
        for (int i = 0; i < N; i++) {
            addEdge(source, 2 * i, K, 0);
            addEdge(2 * i + 1, sink, K, 0);
        }
        int flow = 0;
        int cost = mincost(source, sink, flow);
        if (flow != N * K)
            puts("-1");
        else
            printf("%d\n", cost);
    }
    return 0;
}
/*
 4
 4 8 1
 0 1 1
 1 0 2
 2 3 1
 3 2 2
 0 2 5
 2 0 6
 1 3 5
 3 1 6
 
 4 8 1
 0 1 1
 1 0 10
 2 3 10
 3 2 1
 0 2 10
 2 0 1
 1 3 1
 3 1 10
 
 4 8 2
 0 1 1
 1 0 2
 2 3 1
 3 2 2
 0 2 5
 2 0 6
 1 3 5
 3 1 6
 
 3 4 1
 0 1 5
 1 0 6
 0 2 7
 2 0 8
 */
Read More +
解題區/解題區 - UVa

UVa 12048 - Inhabitants

Problem

給定一個凸包，詢問點是否在凸包內。

Sample Input

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

Sample Output

1
2
3
n
n
y

Solution

由於詢問次數相當多，必須將複雜度降到 O(log n)，採用的方式將凸包其中一個點當作基準，則如果在凸包的點而言，一定會落在某個以基點拉出的三角形內部中，為了方便計算，則可以拿外積的正負邊界上。

得到可能的三角形後，從邊界中可以藉由外積計算是否同側。

採用射線法 O(n) 肯定是吃大虧的。

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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-10
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
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 monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
double g(Pt a, Pt b, double x) {
    Pt vab = b - a;
    return a.y + vab.y * (x - a.x) / vab.x;
}
int inside_convex(const Pt &p, Pt ch[], int n) {
    if(n < 3)
        return false;
    if(cross(ch[0], p, ch[1]) > eps)
        return false;
    if(cross(ch[0], p, ch[n-1]) < -eps)
        return false;
    
    int l = 2, r = n-1;
    int line = -1;
    while(l <= r) {
        int mid = (l + r)>>1;
        if(cross(ch[0],p, ch[mid]) > -eps) {
            line = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return cross(ch[line-1], p, ch[line]) < eps;
}
Pt D[131072], ch[262144];
int main() {
    int testcase, n, m;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            ch[i] = Pt(x, y);
        }
//        n = monotone(n, D, ch);
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            int f = inside_convex(Pt(x, y), ch, n);
            puts(f ? "y" : "n");
        }
        
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12039 - Goldbach's Cardinality

Problem

求任兩個相異質數總和介於 [L, R] 之間的個數。

Sample Input

1
2
3
10 20
30 40
0 0

Sample Output

1
2
9
16

Solution

一開始使用 O(n log n) 的二分解法，但是遲遲沒有通過，最後改用 O(n) 的方式遞減 index。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (10000000>>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[1048576], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    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 g(int n) {
    long long ret = 0;
    int pos = (int)(upper_bound(P+1, P+Pt, n) - (P+1));
    for (int i = 1; i < Pt && P[i] < n; i++) {
//        int pos = (int)(upper_bound(P+1, P+Pt, n - P[i]) - (P+1));
        while (pos > 0 && P[i] + P[pos] > n)
            pos--;
        if (pos >= i)
            ret--;
        ret += pos;
    }
    return ret/2;
}
int main() {
    sieve();
    int L, R;
    while (scanf("%d %d", &L, &R) == 2 && L+R) {
        R = R/2 * 2;
        L = (L-1)/2 * 2;
        printf("%lld\n", g(R) - g(L));
    }
    return 0;
}
/*
 10 20
 30 40
 0 0
 */
Read More +
解題區/解題區 - UVa

UVa 12035 - War Map

Problem

給每個節點的度 (degree)，是否能構成二分圖？

Sample Input

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

Sample Output

1
2
3
4
Case 1: NO
Case 2: YES
Case 3: NO
Case 4: YES

Solution

劃分成兩個集合，則兩邊的 degree 總和一定會相同，因此得到了基礎的窮舉概念。

然後對於窮舉的時候，左集合的元素最大值一定要小於等於右集合大小，反之亦然。
// s 和 t 集合, max(s[i]) <= |t|

這樣窮舉只能保證基礎的條件，而事實上採用 greedy 的驗證方式，從最大度的點開始分配連線給最大度的點，如果最後能分配完成即可找到一種二分圖的解。當然，有人嘗試了 maxflow 的驗證方式也是相當靠譜，不過速度會慢了些，而且還不是很容易 coding。

而這樣的解法仍然會拉 TLE 的緊抱，因此考慮將相同 degree 的窮舉方式壓縮，例如說有 3 個 2 需要窮舉，而採用兩個集合劃分的方式 (0, 3) (1, 2) (2, 1) (3, 0) 四種方式 …，從 2^3 = 8 降到 4 次，速度會快快快很多。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n, m, A[32], B[32], totdeg;
pair<int, int> C[32];
int Ldeg[32], Rdeg[32];
int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == m)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    for (int i = idx == 0; i <= C[idx].second; i++) {
        int l = i, r = C[idx].second - i, ln = lneed, rn = rneed;
        for (int j = 0; j < l; j++)
            Ldeg[lsize+j] = C[idx].first, rn = max(rn, C[idx].first);
        for (int j = 0; j < r; j++)
            Rdeg[rsize+j] = C[idx].first, ln = max(ln, C[idx].first);
        if (dfs(idx+1, lsize+l, rsize+r, ldeg+C[idx].first*l, rdeg+C[idx].first*r, ln, rn)) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n, greater<int>());
        m = 0;
        C[m] = make_pair(A[0], 1), m++;
        for (int i = 1; i < n; i++) {
            if (A[i] == C[m-1].first)
                C[m-1].second++;
            else
                C[m] = make_pair(A[i], 1), m++;
        }
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}

接近 TLE 的版本，概率通過得 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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int n, A[32], B[32], totdeg;
int Ldeg[32], Rdeg[32];
int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == n)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    Ldeg[lsize] = A[idx];
    if (dfs(idx+1, lsize+1, rsize, ldeg+A[idx], rdeg, lneed, max(rneed, A[idx])))
        return 1;
    Rdeg[rsize] = A[idx];
    
    if (idx > 0) {
    if (dfs(idx+1, lsize, rsize+1, ldeg, rdeg+A[idx], max(lneed, A[idx]), rneed))
        return 1;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n);
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}
/*
 10000
 6
 3 0 2 2 3 0
 12
 0 0 0 0 0 0 0 0 0 0 0 0
 20
 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19
 4
 3 1 3 3
 5
 1 2 1 1 3
 4
 2 3 2 3
 7
 4 1 2 3 1 2 3
 */
Read More +
解題區/解題區 - UVa

UVa 12017 - Imitation

Problem

遞移性 a->b, b->c 則 a->c。

給定一張圖的遞移，求不改變任兩個點的遞移關係，最多可以有多少邊、最少需要多少條邊。

Sample Input

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

Sample Output

1
2
3
Case #1: 2 3
Case #2: 3 6
Case #3: 9 18

Solution

從最多條邊來說，最簡單使用 floyd 內閉包的算法 O(n^3)。

1
2
3
4
for k in n
    for i in n
        for j in n
            f[i, j] |= f[i][k] & f[k][j]

最後計算 1(true) 的個數即可，但是這一題 n 最大為 1000，必須從 O(n^3) -> O(n^2)，取而代之，採用 dfs 的方式，把每一個點 s 當作起點，則可以搜索到的點 t，都存有遞移關係 s->t。

而在處理最少條邊，採用強連通元件 (SCC)，先將數個點縮成一個元件，則一個強連通元件內的個數只需要使用一個環即可代替原先的遞移關係。縮圖完之後，會產生 DAG 圖，DAG 圖上仍然會有多餘的遞移關係，從 a->b, b->c, a->c 中，可以發現 a->c 可以不存在。

最後，採用 bfs 的方式，對於每個點 s 當作起點找到最長路徑，假使 t 距離 s 大於 1，且存在 s->t，則可以再少一條邊。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> g[1005], dag[1005];
int vfind[1005], findIdx;
int stk[1005], stkIdx;
int in_stk[1005], visited[1005];
int contract[1005], contract_cnt[1005];
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        contract_cnt[nd] = 0;
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
            contract_cnt[nd]++;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int min_edge, max_edge, mg[1024][1024];
void dfs(int u, int start) {
    mg[start][u] = 1, max_edge++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!mg[start][v]) {
            dfs(v, start);
        }
    }
}
void bfs(int st, int n) {
    queue<int> Q;
    int dist[1024] = {}, u, v;
    Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < dag[u].size(); i++) {
            v = dag[u][i];
            if (dist[v] < min(dist[u] + 1, 2)) {
                dist[v] = min(dist[u] + 1, 2);
                Q.push(v);
            }
        }
    }
    for (int i = 0; i < dag[st].size(); i++) {
        int v = dag[st][i];
//        printf("%d %d %d\n", st, v, dist[v]);
        if (dist[v] != 1) {
            if (mg[st][v]) {
                mg[st][v] = 0, min_edge--;
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear(), dag[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
        }
        min_edge = max_edge = 0;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for (int i = 1; i <= n; i++)
            dfs(i, i);
        
        // SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        for(int i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for(int i = 1; i <= n; i++) {
            int x = contract[i], y;
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y) {
                    if (!mg[x][y]) {
                        mg[x][y] = 1, dag[x].push_back(y);
                        min_edge++;
                    }
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (contract[i] == i) {
                if (contract_cnt[i] > 1)
                    min_edge += contract_cnt[i];
                bfs(i, n);
            }
        }
        printf("Case #%d: %d %d\n", ++cases, min_edge, max_edge - n);
    }
    return 0;
}
/*
 3
 3 3
 1 2
 2 3
 1 3
 3 3
 1 2
 2 3
 3 1
 9 9
 1 2
 2 3
 3 1
 4 5
 5 6
 6 4
 7 8
 8 9
 9 7
 */
Read More +
解題區/解題區 - UVa

UVa 12011 - Complete the Set

Problem

找到一個完備集合，其任兩個數字做 AND 和 OR 運算都在集合中。

給定部分集合，請問至少還需要幾個元素使得其變成完備集合。

Sample Input

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

Sample Output

1
2
3
4
Case #1: 0
Case #2: 2
Case #3: 1
Case #4: 5

Solution

這一題從傳錯題目開始已經放著很久，當時怎麼樣都沒有想法，直接著手 O(n * 2^20) 最慘運行方式，其實這種複雜度與通過的複雜度就差那麼一點的 n。 // 肯定是死在 n。

其實可以發現到，假使挑選 i-th bit 很有可能會連帶其他的 bit 一同帶上，因此對於 i-th bit 最小化攜帶的 bit (做 AND 最小化)。

最後窮舉攜帶 i-th bit 是否要挑 (OR 所有攜帶的 bit)，複雜度降至 O(2^20)

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        set<int> S;
        int A[32] = {}, all = (1<<18) - 1; // used i-th bits minimum attachment.
        memset(A, -1, sizeof(A));
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            S.insert(x);
            all &= x; // used mask = 0
            for (int j = 0; j < 18; j++) {
                if ((x>>j)&1) {
                    if (A[j] == -1)
                        A[j] = x;
                    else
                        A[j] = A[j] & x;
                }
            }
        }
        S.insert(all);
        int m = 0;
        for (int i = 0; i < 18; i++) {
            if (A[i] != -1)
                A[m++] = A[i];
        }
        for (int i = 1; i < (1<<m); i++) { // used mask
            int num = 0;
            for (int j = 0; j < m; j++) {
                if ((i>>j)&1) {
                    num |= A[j];
                }
            }
            S.insert(num);
        }
        printf("Case #%d: %d\n", ++cases, (int)S.size() - n);
    }
    return 0;
}
/*
 4
 5
 0 1 3 5 7
 2
 2 4
 3
 3 7 11
 3
 1 2 4
 */
Read More +
解題區/解題區 - UVa

UVa 11587 - Brick Game

Problem

現在有 N 個積木，兩個人輪流拿 X 個積木 (X in Set, X <= 20)，直到最後一個人拿走最後一塊積木獲勝，如果無法拿取則對方獲勝。

給定一個勝負的前 M 個積木的博弈結果，求 |Set| 最小為何，相同時則輸出字典順序最小的。

Sample Input

1
2
3
4
3
WWLWWL
WWWW
WLW

Sample Output

1
2
3
Case 1: 1 2
Case 2: 1 2 3 4
Case 3: 1

Solution

這一題很賊的地方在於 X <= 20，那麼已經可以發現可以窮舉集合情況，從最小的的集合順序開始窮舉。

窮舉的方式採用 stl 中的 next_permutation。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s + 1);
        printf("Case %d:", ++cases);
        s[0] = 'L';
        int A[20], slen = (int)strlen(s);
        for (int m = 1, n = 20; m <= 20; m++) { // C(n, m)
            int v[20] = {}; // generating combination
            for (int i = 0; i < n - m; i++)
                v[i] = 1;
            sort(v, v+n);
            do {
                int cn = 0;
                for (int i = 0; i < 20; i++) {
                    if (!v[i])
                        A[cn++] = i + 1;
                }
                // dp
                int ok = 1;
                for (int i = 1; i < slen; i++) {
                    int d = 'L';
                    for (int j = 0; j < cn && i - A[j] >= 0; j++) {
                        if (s[i - A[j]] == 'L') {
                            d = 'W';
                            break;
                        }
                    }
                    if (d != s[i]) {
                        ok = 0;
                        break;
                    }
                }
                if (ok) {
                    for (int i = 0; i < cn; i++)
                        printf(" %d", A[i]);
                    puts("");
                    m = 100; // break outer loop
                    break;
                }
            } while (next_permutation(v, v + n));
        }
    }
    return 0;
}
/*
 3
 WWLWWL
 WWWW
 WLW
 
 Case 1: 1 2
 Case 2: 1 2 3 4
 Case 3: 1
 */
Read More +
解題區/解題區 - UVa

UVa 11071 - Permutation Representation

Problem

給定一個置換群，要我們表示成以下特定的形式，1 ≤ n ≤ 200000。

由右至左看，第一次為了填5必須移動2位，第二次移動填4也是移動2位
3 2 5 1 4 -> 1 4 3 2 5 移動 2
1 4 3 2 5 -> 3 2 1 4 5 移動 2
3 2 1 4 5 -> 2 1 3 4 5 移動 2
2 1 3 4 5 -> 1 2 3 4 5移動 1

解題者：李育賢
解題日期：2008 年 3 月 21 日

Sample Input

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

Sample Output

1
2
0 1 2 2 2
0 0 0 2

Solution

李育賢他的解法使用線段樹，靜態操作 shift rotate 和 remove 的問題，仔細想想似乎也不難，但是沒想到我用了模擬的塊狀鏈表解決這一道題目。

為了解決 shift，還必須增加數字的映射，否則沒辦法再 O(sqrt(n)) 時間內完成操作。

塊狀鏈表相當暴力模擬，最簡單地盡可能讓塊差不多是 sqrt(n) 個元素，這樣再 shift 的時候，可以將 head 指標移動次數卡在 sqrt(n) 將給一個操作都限制在 O(sqrt(n))。

塊狀鏈表看看就好，還是回去寫線段樹吧！

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
169
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
// 11071 - Permutation Representation
#define MAXN 262144
int A[MAXN], B[MAXN], C[MAXN];
struct PILE {
    int v[512], size;
    PILE *next;
    int label;
    static int MAXSIZE, BUFSIZE;
    static PILE *head;
    PILE() {
        size = label = 0;
        next = NULL;
    }
};
int PILE::MAXSIZE = 512, PILE::BUFSIZE = 0;
PILE* PILE::head = NULL;
int mp[MAXN]; // map
PILE* removePileElement(PILE *where, int pos) {
    if (pos == where->size - 1) {
        where->size--;
        return where->next;
    }
    assert(pos < where->size);
    PILE::BUFSIZE++;
    PILE *m = new PILE();
    m->label = PILE::BUFSIZE;
    assert(m->size == 0);
    for (int i = pos + 1; i < where->size; i++) {
        m->v[m->size++] = where->v[i];
        assert(where->v[i] < MAXN);
        mp[where->v[i]] = m->label;
    }
    where->size = pos;
    m->next = where->next;
    where->next = m;
    return m;
}
int shrinkList() {
    for (PILE *i = PILE::head; i->next != PILE::head; ) {
        PILE *next = i->next;
        int prevsize = i->size;
        int nextsize = next->size;
        if (prevsize + nextsize <= PILE::MAXSIZE) {
            for (int j = 0; j < next->size; j++) {
                i->v[i->size++] = next->v[j];
                mp[next->v[j]] = i->label;
            }
            i->next = next->next;
            delete next;
        } else
            i = i->next;
    }
    return 0;
}
void printPile() {
    PILE *i = PILE::head;
    do {
        for (int j = 0; j < i->size; j++) {
            printf("%d -> ", i->v[j] + 1);
        }
        printf(" | ");
        i = i->next;
    } while (i != PILE::head);
    puts("\n====");
}
void solve(int n) {
//    printPile();
    for (int i = n - 1; i >= 0; i--) {
        PILE *where = NULL;
        int pos = -1;
//        printf("%d\n", i);
        for (PILE *j = PILE::head; ; j = j->next) {
            if (j->label == mp[i]) {
                where = j;
                break;
            }
        }
        assert(where != NULL);
        for (int j = 0; j < where->size; j++) {
            if (where->v[j] == i) {
                pos = j;
                break;
            }
        }
        assert(pos >= 0  && pos < where->size);
        int shift = where->size - pos - 1;
//        printf("%d %d %d\n", node[where].size, pos, shift);
        for (PILE *j = where->next; j != PILE::head; j = j->next) {
            shift += j->size;
        }
//        printf("shift %d\n", shift);
        C[i] = shift;
        PILE::head = removePileElement(where, pos);
        shrinkList();
//        printPile();
    }
    for (PILE *i = PILE::head, *j = i->next; j != PILE::head; j = i->next) {
        delete i;
        i = j;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &B[i]);
        }
//        for (int i = 0; i < n; i++) {
//            A[i] = i + 1;
//            B[i] = A[i];
//        }
//        for (int i = 0; i < n; i++) {
//            int x = rand()%n;
//            int y = rand()%n;
//            swap(B[x], B[y]);
//        }
        for (int i = 0; i < n; i++) {
            C[A[i] - 1] = B[i] - 1;
        }
        
        PILE *node = new PILE();
        PILE::MAXSIZE = (int)sqrt(n) + 1;
        PILE::head = node;
        PILE::BUFSIZE = 0;
        PILE::BUFSIZE++;
        node->label = PILE::BUFSIZE, node->next = node;
        for (int i = 0; i < n; i++) {
            node->v[node->size++] = C[i];
            mp[C[i]] = node->label;
            if (node->size == PILE::MAXSIZE) {
                PILE *tmp = new PILE();
                PILE::BUFSIZE++;
                tmp->label = PILE::BUFSIZE;
                tmp->next = node->next;
                node->next = tmp;
                node = node->next;
            }
        }
        
        solve(n);
        
        for (int i = 0; i < n; i++) {
            printf("%d%c", C[i], i == n - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 5
 1 2 3 4 5
 3 2 5 1 4
 4
 1 2 3 4
 3 4 1 2
*/
Read More +