解題區/解題區 - UVa

UVa 11123 - Counting Trapizoid

Problem

給平面上 N 個不重複的點，有多少梯形可以由這幾個點構成？

  • 有四條邊
  • 一對平行、一對不平行
  • 面積為正

Sample Input

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

Sample Output

1
2
Case 1: 0
Case 2: 1

Solution

先窮舉任兩個點拉起的線段 (let N = n*(n-1)/2)。

針對線段斜率排序，接著將相同斜率放置在同一個 group。

對於每一個 group 的每一個元素計算有多少可以配對成梯形。

  • 防止共線
  • 防止線段具有相同長度 (防止兩對邊平行)

斜率相同，按照交 y 軸的大小由小到大排序。(左側到右側)，由左側掃描到右側，依序把非共線的線段丟入，並且紀錄線段長度資訊。每一個能匹配的組合為 當前線段數 - 相同長度線段數。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define eps 1e-9
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > eps)
            return true;
        return false;
    }
};
struct DOUBLE {
    double v;
    DOUBLE(double a = 0):
        v(a) {}
    bool operator<(const DOUBLE &other) const {
        if (fabs(v - other.v) > eps)
            return v < other.v;
        return false;
    }
};
Pt D[256];
Seg segs[65536], buf[65536];
int main() {
    int cases = 0;
    int n, m;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        sort(D, D + n);
        
        m = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                segs[m++] = Seg(D[i], D[j]);
        
        sort(segs, segs + m);
        long long ret = 0;
        for (int i = 0; i < m; ) {
            int j = i, tn = 0;
            while (j < m && fabs(segs[i].angle - segs[j].angle) < eps)
                buf[tn++] = segs[j], j++;
            i = j;
            
            map<DOUBLE, int> LEN; // LEN[len] = count.
            queue<Seg> Q;
            int tmp = 0;
//			for (int k = 0; k < tn; k++)
//				printf("(%lf %lf) - (%lf %lf)\n", buf[k].s.x, buf[k].s.y, buf[k].e.x, buf[k].e.y);
//			puts("--- same slope");
            for (int k = 0; k < tn; k++) {
                while (!Q.empty() && fabs(cross(buf[k].s, buf[k].e, Q.front().s)) > eps) {
                    Seg t = Q.front();
                    Q.pop();
                    tmp++, LEN[DOUBLE(dist(t.s, t.e))]++;
                }
                int comb = tmp - LEN[DOUBLE(dist(buf[k].s, buf[k].e))]; // remove same length
                ret += comb;
                Q.push(buf[k]);
            }
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
4
0 0
1 0
0 1
1 1
4
0 0
1 1
2 0
0 1
6
5 1
3 1
5 0
3 3
2 4
0 8
0
*/
Read More +
解題區/解題區 - UVa

UVa 12452 - Plants vs. Zombies HD SP

Problem

給一個 N 個點的樹圖，在點上放置植物保護所有的邊，每個點上最多放置一個植物，請問最少花費為何？

  • 綠豆槍手：花費 100 元，保護相鄰一條邊。
  • 分裂碗豆：花費 175 元，保護相鄰兩條邊。
  • 楊桃：花費 500 元，保護相鄰所有邊。

Sample Input

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

Sample Output

1
2
$100
$175

Solution

將樹轉換成有根樹，對於每一個 node 當成 tree 去做考慮。

狀態 dp[node][1:protect edge from parent, 0:none]

以 node 以下作為一個 subtree 的最少花費，並且是否已經保護通往父親的邊。

效率 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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 32767
vector<int> g[MAXN];
long long dp[MAXN][2]; // [node][1:protect edge from parent, 0:none]
#define INF (1LL<<50)
void dfs(int u, int p) {
    
    dp[u][0] = dp[u][1] = INF;
    
    long long cost[3] = {};
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)	continue;
        dfs(v, u);
        cost[0] += dp[v][0];
        cost[1] += dp[v][1];
        cost[2] += min(dp[v][0], dp[v][1]);
    }
    dp[u][0] = min(dp[u][0], cost[1]);
    dp[u][1] = min(dp[u][1], cost[1] + 100);
    dp[u][1] = min(dp[u][1], cost[2] + 500);
    
    long long c[2] = {INF, INF};
    for (int i = 0; i < g[u].size(); i++) {// two edge with subnode and parent.
        int v = g[u][i];
        if (v == p)	continue;
        dp[u][1] = min(dp[u][1], cost[1] - dp[v][1] + dp[v][0] + 175);
        if (-dp[v][1] + dp[v][0] < c[1]) {
            c[1] = -dp[v][1] + dp[v][0];
            if (c[0] > c[1])	swap(c[0], c[1]);
        }
    }
    // two two edge with two subnodes
    dp[u][0] = min(dp[u][0], cost[1] + c[0] + c[1] + 175);
}
int main() {
    int testcase, n;
    int u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(0, -1);
        printf("$%lld\n", min(dp[0][0], dp[0][1]));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12440 - Save the Trees

Problem

有一排樹，每個樹分別有 type 和 height，現在要將其分團，

  • 每一團內不允許有相同的 type
  • 每一團的花費是最高的 height

計算總花費最小為何？

Sample Input

1
2
3
4
5
6
7
1
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
Case 1: 26

Solution

藉由掃描線的思路，可以得知每一個樹的位置 i，往左延伸最大多少內不會有重複的 type。詳見 12890 - Easy Peasy 的技巧。

因此會得到公式$dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$

dp[i]：將前 i 個樹分團的最少費用。

計算這個公式需要 O(n^2)，由於 n 很大，必須找一個優化將其降下來。

首先知道 f(i) 是非遞減函數 (會一直增加)，單純看 i 時，dp[j - 1] 是固定的，但
max(height[k]) 會逐漸增加，如果能在 O(log n) 時間進行更新、詢問，複雜度將可以降至 O(n log n)。

每個元素有兩個屬性 (a, b)

  • query(f(i), i) : return min(A[k].a + A[k].b), f(i) <= k <= i
  • update(f(i), i, height[i]) : A[k].b = max(A[k].b, height[i])

左思右想仍然沒有辦法用線段樹完成它，至少是一個很 tricky 的花費計算。

有一個貪心的思路，考慮區間內的計算時，只需要找到嚴格遞減的高度進行更新即可，並非所有的可能進行嘗試。用一個單調隊列，只記錄 [f(i), i] 之間的嚴格遞減的高度資訊，接著每次需要窮舉單調隊列內的所有元素。

複雜度最慘還是 O(n^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
92
93
94
#include <stdio.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int type[MAXN], height[MAXN];
long long dp[MAXN];
int dQ[MAXN];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &type[i], &height[i]);
        map<int, int> R;
        int L = 0;
        dp[0] = 0;
        int head = 0, rear = -1;
        for (int i = 1; i <= n; i++) {
            int &y = R[type[i]];
            L = max(L, y);
            y = i;
            while (head <= rear && dQ[head] <= L)
                head++;
            while (head <= rear && height[dQ[rear]] <= height[i])
                rear--;
            dQ[++rear] = i;
            
            dp[i] = 1LL<<60;
            for (int j = head; j <= rear; j++) {
                if (j != head)
                    dp[i] = min(dp[i], dp[dQ[j-1]] + height[dQ[j]]);
                else
                    dp[i] = min(dp[i], dp[L] + height[dQ[j]]);
            }
        }
        printf("Case %d: %lld\n", ++cases, dp[n]);
    }
    return 0;
}
/*
1
5
3 11
2 13
1 12
2 9
3 13
30
10
4 13
2 18
7 20
1 16
1 14
10 5
5 11
7 19
8 12
2 16
9999
10
10 16
3 5
8 11
8 2
5 3
6 2
10 19
6 10
6 16
6 4
9999
10
3 6
10 5
2 9
5 2
9 3
3 8
6 10
4 17
7 10
6 11
*/
Read More +
解題區/解題區 - UVa

UVa 1382 - Distant Galaxy

Problem

給平面上 N 個點，找一個最大矩形，使得矩形邊上有最多點個數。

Sample Input

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

Sample Output

1
Case 1: 7

Solution

UVa 1382

先離散化處理，將所有點放置在 grid[100][100] 內。

接著窮舉上下兩條平行線，由左而右開始掃描，邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L]，掃描時維護 V[U3] + V[U4] - H[L] 的最小值。

特別小心矩形的四個頂點的排容，上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形，必須考慮共線上最多的點個數。

效率 O(n^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
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n, x[128], y[128];
    int cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        map<int, int> Rx, Ry;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x[i], &y[i]);
            Rx[x[i]] = 0, Ry[y[i]] = 0;
        }
        
        int size, R, C;
        size = 0;
        for (map<int, int>::iterator it = Rx.begin();
            it != Rx.end(); it++) {
            it->second = size++;
        }
        R = size;
        size = 0;
        for (map<int, int>::iterator it = Ry.begin();
            it != Ry.end(); it++) {
            it->second = size++;
        }
        C = size;
        
        int g[128][128] = {}, ret = 0;
        for (int i = 0; i < n; i++) {
            int r, c;
            r = Rx[x[i]], c = Ry[y[i]];
            g[r][c]++;
        }
        
        for (int i = 0; i < R; i++) {
            int sum[128] = {}, s1, s2, mn;
            for (int j = i; j < R; j++) {
                s1 = s2 = 0, mn = 0;
                for (int k = 0; k < C; k++) {
//					printf("[%d %d] %d\n", i, j, k);
                    sum[k] += g[j][k];
                    s1 += g[i][k], s2 += g[j][k];
                    if (i != j) {
//						printf("%d %d %d %d = %d\n", s1, s2, mn, sum[k], s1 + s2 - mn + sum[k]);
                        ret = max(ret, s1 + s2 - mn + sum[k] - g[i][k] - g[j][k]);
                        mn = min(mn, s1 + s2 - sum[k]);
                    }
                }
            }
        }
        
        for (int i = 0; i < R; i++) {
            int sum = 0;
            for (int j = 0; j < C; j++)
                sum += g[i][j];
            ret = max(ret, sum);
        }
        
        for (int i = 0; i < C; i++) {
            int sum = 0;
            for (int j = 0; j < R; j++)
                sum += g[j][i];
            ret = max(ret, sum);
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
3
1 1
2 1
3 1
3
1 1
1 2
1 3
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/
Read More +
解題區/解題區 - UVa

UVa 12873 - The Programmers

Problem

給 P 個隊伍、S 個賽區，每隊分別都有可以去的賽區，而每一個賽區最多容納 C 個隊伍。

請問參加的總隊伍數量最大為何？

Sample Input

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

Sample Output

1
2
2
3

Solution

建造 maxflow 模型，source - team - site - sink 即可完成。

不是說好 maxflow 不太會考的嗎？結果還是在泰國賽區出來了，雖然之前也噴過 mincost 最少費用流 …

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
#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 testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int P, S, C, m, x, y;
        scanf("%d %d %d %d", &P, &S, &C, &m);
        g.Init(P + S + 2);
        int source = 0, sink = P + S + 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, P + y, 1);
        }
        for (int i = 1; i <= P; i++)
            g.Addedge(source, i, 1);
        for (int i = 1; i <= S; i++)
            g.Addedge(P + i, sink, C);
        int ret = g.Maxflow(source, sink);
        printf("%d\n", ret);
    }
    return 0;
}
/*
 2
 2 2 1 4
 1 1
 1 2
 2 1
 2 2
 4 3 1 12
 1 1
 1 2
 1 3
 2 1
 2 2
 2 3
 3 1
 3 2
 3 3
 4 1
 4 2
 4 3
*/
Read More +
解題區/解題區 - UVa

UVa 12872 - Hidden Plus Signs

Problem

盤面上放置許多 + 展開，保證寬高相同並且不會超出格子外部，同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋，每一格會顯示被覆蓋幾次。

找到一種放置方法，復原盤面結果，如果有種放置方法，選擇一種字典順序最小的輸出。

Sample Input

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

Sample Output

1
2
3
4
2
3 3
9
8 10

Solution

論窮舉順序的重要性，將會導致速度的快慢。

原則上先把所有 1 的位置挑出，依序窮舉每一個 1 是否可以進行放置。每一次選擇放置時，先從最大的寬高開始嘗試，先塞掉大多數的盤面結果，否則速度會被拉下。

不確定這一題是否有很正統的作法，求指導。

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 <algorithm>
using namespace std;
int g[32][32], n, m;
int A[900][2], N, SUM = 0;
int isEmpty() {
    return SUM == 0;
}
void remove(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        g[i][y]--, SUM--;
    for (int i = y - w; i <= y + w; i++)
        g[x][i]--, SUM--;
    g[x][y]++, SUM++;
}
void resume(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        g[i][y]++, SUM++;
    for (int i = y - w; i <= y + w; i++)
        g[x][i]++, SUM++;
    g[x][y]--, SUM--;
}
int place(int x, int y, int w) {
    for (int i = x - w; i <= x + w; i++)
        if (!g[i][y])
            return 0;
    for (int i = y - w; i <= y + w; i++)
        if (!g[x][i])
            return 0;
    return 1;
}
int dfs(int idx, int used, int LX, int LY) {
    if (isEmpty()) {
        printf("%d\n%d %d\n", used, LX + 1, LY + 1);
        return 1;
    }
    if (idx == N)
        return 0;
    int t = min(min(A[idx][0], A[idx][1]), min(n - 1 - A[idx][0], m - 1 - A[idx][1]));
    for (int i = t; i >= 1; i--) {
        if (place(A[idx][0], A[idx][1], i)) {
            remove(A[idx][0], A[idx][1], i);
            if (dfs(idx+1, used + 1, A[idx][0], A[idx][1]))
                return 1;
            resume(A[idx][0], A[idx][1], i);
        }
    }
    if (dfs(idx+1, used, LX, LY))
        return 1;
    return 0;
}
int main() {
    int testcase;
    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", &g[i][j]), SUM += g[i][j];
        N = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 1)
                    A[N][0] = i, A[N][1] = j, N++;
        dfs(0, 0, -1, -1);
    }
    return 0;
}
/*
2
5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0
10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12871 - Landmine Cleaner

Problem

給予每一個格子的得分，分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分)，因此最低 0 分，最高 12 分。

保證只有唯一解。

Sample Input

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

Sample Output

1
2
3
-L--
L-LL
LL--

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024
int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
    int v = A[x][y], tx, ty;
    int unknown = 0, score = 0;
    for (int i = 0; i < 8; i++) {
        tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx >= n || ty >= m)
            continue;
        if (solv[tx][ty])	score += g[tx][ty];
        else				unknown++;
    }
    if (v < 3)					return -1;
    if (v > 8)					return 1;
    if (score + unknown < v)	return 1;
    if (score + 4 > v)			return -1;
    return 0; // not sure.
}
int main() {
    int testcase;
    int t;
    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", &A[i][j]);
            }
        }
        memset(solv, 0, sizeof(solv));
        int test = n * m;
        while (test) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (solv[i][j])	continue;
                    int t = isplace(i, j);
                    if (t) {
                        test--;
                        g[i][j] = t > 0;
                        solv[i][j] = 1;
                    }
                }
            }
            
        }
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (solv[i][j])
                    putchar(g[i][j] ? 'L' : '-');
                else {
                    assert(false);
                }
            }
        }
    }
    return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2
3 3
7 9 7
9 12 9
7 9 7
3 1
0
0
0
*/
Read More +
解題區/解題區 - UVa

UVa 12431 - Happy 10/9 Day

Problem

計算 base B 下，每一個 digit 都是 d 的情況，長度為 N，mod M 的結果為何？

Sample Input

1
2
1
3 10 2 10

Sample Output

1
Case 1: 2

Solution

找到

$$d B^{0} + d B^{1} + ... + d B^{N-1} \text{ mod } M \\ \Rightarrow d \frac{B - 1}{B^{N} - 1} \text{ mod } M$$

由於 M 超過 int，運算起來仍有機會 overflow，因此要使用模乘法，也就是相當於直式乘法的運算，防止 (a*b) mod M 溢位。

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
#include <stdio.h> 
long long mul(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 mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret;
}
long long solve(long long n, long long b, long long d, long long m) {
    // d * (b^n - 1) / (b - 1) mod m
    long long ret;
    ret = mpow(b, n, (b - 1) * m); // b^n mod (b-1) * m
    ret = (ret + (b - 1) * m - 1)/ (b - 1);
    ret = mul(ret, d, m);
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n, b, d, m, ret;
        scanf("%lld %lld %lld %lld", &n, &b, &d, &m);
        ret = solve(n, b, d, m);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12425 - Best Friend

Problem

給一個整數 N，接著詢問 x，有多少 gcd(i, N) <= x。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
Case 1
8
16
28
Case 2
10
10

Solution

先把 N 的因數 f 全部找出，原則上不超過 2000 個，然後建出 phi(N/f[i])。

當要知道 gcd(i, N) = x 時，相當於找到 gcd(i/x, N/x) = 1，任何與 N/x 互質的個數。建造完後，對於每次詢問二分答案即可。

很多地方忘記用 long long，吃了不少 Runtime error。

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 <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (1000000>>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[100000], Pt = 0;
int phi[1048576];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for (i = 1; i <= n; i++)
    	phi[i] = i;
    for (i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            for (j = i; j <= n; j += i)
            	phi[j] = phi[j]/i * (i-1);
            P[Pt++] = i;
        }
    }
}
vector< pair<long long, int> > factor(long long n) {
    long long on = n;
    vector< pair<long long, int> > R;
    
    for(int i = 0, j; i < Pt && (long long)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((long long)P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, long long m, vector< pair<long long, int> > &v, vector<long long> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    long long a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
long long getPhi(long long n) {
    if (n < 1000000)	return phi[n];
    vector< pair<long long, int> > f = factor(n);
    for (int i = 0; i < f.size(); i++)
        n = n / f[i].first * (f[i].first - 1);
    return n;
}
int main() {
    sieve();
    int testcase, cases = 0, Q;
    long long N, X;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %d", &N, &Q);
        vector< pair<long long, int> > f = factor(N);
        vector<long long> fa;
        vector<long long> sum;
        make(0, N, 1, f, fa);
        sum.resize(fa.size(), 0);
        sort(fa.begin(), fa.end());
        for (int i = 0; i < fa.size(); i++) {
            if (i)
                sum[i] = sum[i-1] + getPhi(N / fa[i]);
            else
                sum[i] = getPhi(N / fa[i]);
        }
        printf("Case %d\n", ++cases);
        for (int i = 0; i < Q; i++) {
            scanf("%lld", &X);
            if (X <= 0) {
                puts("0");
                continue;
            }
            long long ret = 0;
            int pos = (int)(lower_bound(fa.begin(), fa.end(), X) - fa.begin());
            if (pos >= fa.size() || fa[pos] > X)	pos--;
            ret = sum[pos];
            printf("%lld\n", ret);
        }
    }
    return 0;
}
/*
2
30 3
1
2
10
11 5
0
1
2
11
15
*/
Read More +
解題區/解題區 - UVa

UVa 12404 - Trapezium Drawing

Problem

給予梯形兩點座標、四個邊長。找到另外兩點座標。

Sample Input

1
2
1
0 0 20 0 10 14 8

Sample Output

1
2
Case 1:
14.00000000 8.00000000 0.00000000 8.00000000

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    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);
    }
    Pt operator/(const double a) const {
        return Pt(x / a, y / a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
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);
}
double solve(double a, double b, double c, double d) {
    // d^2 - x^2 = b^2 - (a - x - c)^2
    // d^2 - x^2 = b^2 - (a-c - x)^2
    // d^2 - x^2 = b^2 - ((a-c)^2 - 2(a-c)x + x^2)
    // d^2 - x^2 = b^2 - (a-c)^2 + 2(a-c)x - x^2
    // d^2 - b^2 + (a-c)^2 = 2(a-c)x
    double x;
    x = (pow(d, 2) - pow(b, 2) + pow(a-c, 2))/(2 * (a-c));
    return x;
}
int main() {
    int testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        Pt A, B, C, D;
        double a, b, c, d;
        scanf("%lf %lf", &x, &y);
        A = Pt(x, y);
        scanf("%lf %lf", &x, &y);
        B = Pt(x, y);
        scanf("%lf %lf %lf", &b, &c, &d);
        a = dist(A, B);
        x = solve(a, b, c, d);
        
        Pt vAB = (B - A) / a;
        double theta = atan2(sqrt(d*d - x*x), x);
        D = rotateRadian(vAB, theta) * d + A;
        C = D + vAB * c;
        printf("Case %d:\n", ++cases);
        printf("%.8lf %.8lf %.8lf %.8lf\n", C.x, C.y, D.x, D.y);
    }
    return 0;
}
/*
1
0 0 20 0 10 14 8
8
0 0 20 0 10 14 8
0 0 20 0 8 14 10
20 0 0 0 10 14 8
20 0 0 0 8 14 10
8 0 8 20 10 14 8
8 0 8 20 8 14 10
0 20 0 0 10 14 8
0 20 0 0 8 14 10
*/
Read More +