解題區/解題區 - UVa

UVa 11476 - Factorizing Larget Integers

Problem

給你一個正整數 $N$ ($1 < N \le10^{18}$)，請你把 $N$ 質因數分解。

注意：大整數分解

Sample Input

1
2
3
4
3
60
36
10007

Sample Output

1
2
3
60 = 2^2 * 3 * 5
36 = 2^2 * 3^2
10007 = 10007

Solution

2015/07/11 第二版，加速三倍，加快模乘法運算，減少模數利用減法。

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 <bits/stdc++.h> 
using namespace std;
#define MAXL (50000>>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[50000], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 46340;
    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 mul(unsigned long long a, unsigned long long b, unsigned long long mod) { 
    long long ret = 0; 
    for (a %= mod, b %= mod; b != 0; b >>= 1, a <<= 1, a = a >= mod ? a - mod : a) {
        if (b&1) {
            ret += a;
            if (ret >= mod)	ret -= mod;
        }
    } 
    return ret; 
}
void exgcd(long long x, long long y, long long &g, long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long llgcd(long long x, long long y) {
    if (x < 0)    x = -x;
    if (y < 0)    y = -y;
    if (!x || !y)    return x + y;
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
long long inverse(long long x, long long p) {
    long long g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)	r = -r;
    return (r%p + p)%p;
}
long long mpow(long long x, long long y, long long mod) { // mod < 2^32 
    long long ret = 1;
    while (y) {
        if (y&1) 
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret % mod;
}
long long mpow2(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 % mod;
}
int isPrime(long long p) { // implements by miller-babin
    if (p < 2 || !(p&1))	return 0;
    if (p == 2)				return 1;
    long long q = p-1, a, t;
    int k = 0, b = 0;
    while (!(q&1))	q >>= 1, k++;
    for (int it = 0; it < 2; it++) {
        a = rand()%(p-4) + 2;
        t = mpow2(a, q, p);
        b = (t == 1) || (t == p-1);
        for (int i = 1; i < k && !b; i++) {
            t = mul(t, t, p);
            if (t == p-1)
                b = 1;
        }
        if (b == 0)
            return 0;
    }
    return 1;
}
long long pollard_rho(long long n, long long c) {
    long long x = 2, y = 2, i = 1, k = 2, d;
    while (true) {
        x = (mul(x, x, n) + c);
        if (x >= n)	x -= n;
        d = llgcd(x - y, n);
        if (d > 1) return d;
        if (++i == k) y = x, k <<= 1;
    }
    return n;
}
void factorize(int n, vector<long long> &f) {
    for (int i = 0; i < Pt && P[i]*P[i] <= n; i++) {
    	if (n%P[i] == 0) {
    		while (n%P[i] == 0)
    			f.push_back(P[i]), n /= P[i];
    	}
    }
    if (n != 1)	f.push_back(n);
}
void llfactorize(long long n, vector<long long> &f) {
    if (n == 1)	
        return ;	
    if (n < 1e+9) {
        factorize(n, f);
        return ;
    }
    if (isPrime(n)) {
        f.push_back(n);
        return ;
    }
    long long d = n;
    for (int i = 2; d == n; i++)
        d = pollard_rho(n, i);
    llfactorize(d, f);
    llfactorize(n/d, f);
}
int main() {
    sieve();
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        
        vector<long long> f;
        map<long long, int> r;
            
        llfactorize(n, f);
        for (auto &x : f)
            r[x]++;
            
        printf("%lld =", n);
        for (auto it = r.begin(); it != r.end(); it++) {
            if (it != r.begin())
                printf(" *");
            printf(" %lld", it->first);
            if (it->second > 1)
                printf("^%d", it->second);
        }
        puts("");
        
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1402 - Robotic Sort

Problem

機器人要排序序列，每一次會將第 i 小元素放置到正確位置，機器人每一次操作都會翻轉一個區間。請問每一步運行時，要翻轉的元素位置分別在哪裡。

Sample Input

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

Sample Output

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

Solution

我想這一題的做法偏向 treap、splay tree 來維護區間反轉。

這裡用 塊狀鏈表 來試試，為了解決元素查找位置，紀錄該元素所在的堆、該堆的哪個位置。再利用 $O(\sqrt{n})$ 的時間去計算實際位置。還好速度沒有卡很緊，勉強能拿到 AC。弄個內存池說不定可以更快一點。但是常常需要刪除跟增加，必須寫額外的記憶體管理部分 (用一個 set 維護)。

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// Unrolled Linked List
const int MAXPILE = 512;
const int MAXN = 131072;
class UnrolledLinkedList{
public:
    struct Node {
        int v[MAXPILE], vn;
        int rev_label, pid;
        Node *next;
        Node() {
            vn = rev_label = 0;
            next = NULL;
        }
        void relax() {
            if (rev_label) {
                for(int i = 0, j = vn-1; i < j; i++, j--)
        			swap(v[i], v[j]);
        		rev_label = 0;
        	}
        }
    };
    Node *head;
    int PSIZE, pid;
    int e_pos[MAXN], e_id[MAXN];
    void init() {
        free();
        head = NULL, PSIZE = MAXPILE /2;
        pid = 0;
    }
    Node* getNode() {
        Node* p = new Node();
        p->pid = pid++;
        return p;
    }
    void remap(Node *u) {
        for (int i = 0; i < u->vn; i++) 
            e_pos[u->v[i]] = i, e_id[u->v[i]] = u->pid;
    }
    int find(int e_val) {
        int pid = e_id[e_val];
        int sum_element = 0;
        Node *u, *v;
        
        for (u = head; u != NULL && u->pid != pid; u = u->next)
            sum_element += u->vn;
            
//		printf("find %d - %d\n", e_val, pid);
        assert(u != NULL);
        if (u->rev_label)
            return sum_element + u->vn - 1 - e_pos[e_val];
        else
            return sum_element + e_pos[e_val];
    }
    void set(int A[], int n) {
        init();
        Node *u, *v;
        
        head = getNode();
        u = head, v = NULL;
        PSIZE = min(PSIZE, (int) sqrt(n));
        for (int i = 0; i < n; i++) {
            if (u->vn == PSIZE) {
                u->next = getNode();
                v = u, u = u->next;
            }
            u->v[u->vn++] = A[i];
        }
        for (u = head; u != NULL; u = u->next)
            remap(u);
    }
    void shrinkList() {
        Node *u, *v;
        u = head;
        for (u = head; u != NULL && u->next != NULL; u = u->next) {
            if (u->vn + u->next->vn <= 2 * PSIZE) { // merge
                v = u->next;
                u->relax(), v->relax();
                for (int i = u->vn, j = 0; j < v->vn; i++, j++)
                    u->v[i] = v->v[j];
                u->vn += v->vn;
                remap(u);
                u->next = v->next;
                delete v;
            }
        }
    }
    void splitNode(Node *u, int left_size) { // length(left) = v
        Node *v = getNode();
        u->relax();
        v->next = u->next;
        u->next = v;
        v->vn = u->vn - left_size;
        for(int i = left_size, j = 0; i < u->vn; i++, j++)
            v->v[j] = u->v[i];
        u->vn = left_size;
        remap(u), remap(v);
    }
    void reverse(int l, int r) { // [l, r] = [0, n-1]
        Node *lptr, *rptr, *u, *v;
    	Node *lpre, *rpre, *rnext;
    	int sum_element = 0;
    	
    	u = head, v = NULL;
    	for (u = head, v = NULL; u != NULL; v = u, u = u->next) {
    		if (sum_element < l && l < sum_element + u->vn) 
            	splitNode(u, l - sum_element); // left[...l-1], right[l...]
        	if (sum_element <= r && r < sum_element + u->vn)
            	splitNode(u, r - sum_element + 1);
            	
            if (sum_element == l)
        		lptr = u, lpre = v;
            if (sum_element + u->vn - 1 == r)
        		rptr = u, rpre = v;
        	
        	sum_element += u->vn;
    	}
    	    	
//    	debug();
    	
    	rnext = rptr->next;
    	stack<Node*> stk;
    	for (u = lptr; u != rnext; u = u->next) {
    		u->rev_label = !u->rev_label;
    		stk.push(u);
    	}
    	
    	if (lpre == NULL) {
    		head = stk.top();
        	u = head, stk.pop();
        	while (!stk.empty()) {
            	u->next = stk.top(), stk.pop();
            	u = u->next;
        	}
        	u->next = rnext;
    	} else {
    		u = lpre;
    		while (!stk.empty()) {
    			u->next = stk.top(), stk.pop();
            	u = u->next;
        	}
        	u->next = rnext;
    	}
    	
    	shrinkList();
    }
    void debug() {
        Node *u = head;
    	while (u != NULL) {
        	printf("%d : %d, ", u->pid, u->rev_label);
        	for(int i = 0; i < u->vn; i++)
            	printf("%d ", u->v[i]);
        	puts("");
        	u = u->next;
    	}
    	puts("====");
    }
    void free() {
        Node *u = head, *v = NULL;
    	while(u != NULL) {
        	v = u, u = u->next;
        	delete v;
    	}
    }
} g;
int A[MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        vector< pair<int, int> > B;
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            B.push_back(make_pair(A[i], i));
        }
        
        sort(B.begin(), B.end());
        
        map< pair<int, int>, int > C;
        for (int i = 0; i < B.size(); i++)
            C[B[i]] = i;
        
        for (int i = 0; i < n; i++)
            A[i] = C[make_pair(A[i], i)];
        
        g.set(A, n);
//		g.debug();
        
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            int pos = g.find(i);
            g.reverse(i, pos);
            ret.push_back(pos);
//			g.debug();
        }
        
        for (int i = 0; i < n; i++)
            printf("%d%c", ret[i] + 1, i == n-1 ? '\n' : ' ');
        
    }
    return 0;
}
/*
6 
3 4 5 1 6 2 
4 
3 3 2 1 
0
10
5 18 19 12 7 12 0 2 11 9
1
4
19
5 17 8 10 13 18 10 5 3 15 2 19 12 10 2 14 18 0 6
12
15 13 7 14 15 7 12 15 4 10 6 3
15
18 7 5 6 5 5 10 9 2 4 9 10 7 13 19
5
3 4 1 1 3
6
8 0 6 2 6 16
7
17 5 12 1 3 9 13
1
8
10
15 19 17 19 17 18 2 12 0 10
10
5 1 14 6 7 12 15 17 5 11
0
*/
Read More +
解題區/解題區 - UVa

UVa 1438 - Asteroids

Problem

兩個行星碰撞，請問質量中心能夠距離最近為何。

兩個行星會呈現凸多面體的形式，給予行星多面體上的頂點。

Sample Input

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

Sample Output

1
0.75

Solution

題目雖然已經給定所有在凸面體上的頂點，應該是要做一次三維凸包。

質心之間能多近，就是兩質心連線的最短距離，連線後不保證線上每一點都在其中一個凸多面體內部。因此找到凸面體的質心後，窮舉每一個表面拉出的平面，求點到面的最短距離。兩個答案相加即可。

複習下三維凸包算法，維護 conflict graph 去玩的那個，參照網路上的模板繞過一圈，代碼還真是相當簡潔有力 (雖然時間跟空間使用上都沒有辦法好計算，基於期望值 …)！利用空間共平面的順逆時針，來維護外部點判定，解決了之前上課中的困擾。

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <stdio.h> 
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const int MAXN = 1024;
int cmpZero(double x) {
    if (fabs(x) < eps)	return 0;
    return x < 0 ? -1 : 1;
}
class ConvexHull3D {
public:
    struct Point3D {
        double x, y, z;
        Point3D(double a = 0, double b = 0, double c = 0):
            x(a), y(b), z(c) {}
        Point3D operator+(const Point3D &a) const {
            return Point3D(x + a.x, y + a.y, z + a.z);
        }
        Point3D operator-(const Point3D &a) const {
            return Point3D(x - a.x, y - a.y, z - a.z);
        }
        Point3D operator/(double a) const {
            return Point3D(x/a, y/a, z/a);
        }
        Point3D operator*(double a) const {
            return Point3D(x*a, y*a, z*a);
        }
        bool operator!=(const Point3D &a) const {
            return cmpZero(x - a.x) || cmpZero(y - a.y) || cmpZero(z - a.z);
        }
        Point3D cross(const Point3D &a) const { // outer product
            return Point3D(y*a.z - z*a.y, z*a.x - x*a.z, x*a.y - y*a.x);
        }
        double dot(const Point3D &a) const {
            return x*a.x + y*a.y + z*a.z;
        }
        double length() {
            return sqrt(x*x+y*y+z*z);
        }
        void read() {
            scanf("%lf %lf %lf", &x, &y, &z);
        }
    };
    struct Face {
        int a, b, c; 	// point3d id
        bool flag; 		// on Convex Hull
    };
    
    int n, tri_num;
    Point3D pt[MAXN];
    Face faces[MAXN*8];
    Face* g[MAXN][MAXN];
    
    double tri_area(Point3D a, Point3D b, Point3D c) { 	// value >= 0
        return ((a - c).cross(b - c)).length()/2;
    }
    double volume(Point3D a, Point3D b, Point3D c, Point3D d) { // directed
        return ((b - a).cross(c - a)).dot(d - a)/6;
    }
    double pt2Face(Point3D a, Point3D b, Point3D c, Point3D p) {
        Point3D n = (b - a).cross(c - a);
        Point3D t = p - a;
        double v = n.dot(t) / n.length();
        return fabs(v);
    }
    double ptWithFace(Point3D &p, Face &f) { // 0: p in f, <0, >0: above or below
        Point3D a, b, c;
        a = pt[f.b] - pt[f.a];
        b = pt[f.c] - pt[f.a];
        c = p - pt[f.a];
        return (a.cross(b)).dot(c);
    }
    bool samePlane(Face &s, Face &t) {
        Point3D a, b, c;
        bool ret = true;
        a = pt[s.a], b = pt[s.b], c = pt[s.c];
        ret = cmpZero(volume(a, b, c, pt[t.a])) == 0 &&
                cmpZero(volume(a, b, c, pt[t.b])) == 0 &&
                cmpZero(volume(a, b, c, pt[t.c])) == 0;
        return ret;
    }
    void deal(int a, int b, int p) {
        Face *f = g[a][b];
        if (f->flag) {
            if (cmpZero(ptWithFace(pt[p], *f)) > 0) {
                dfs(p, f);
            } else {
                Face &add = faces[tri_num++];
                add.a = b, add.b = a, add.c = p;
                add.flag = 1;
                g[b][a] = g[a][p] = g[p][b] = &add;
            }
        }
    }
    void dfs(int p, Face *f) {
        f->flag = 0;	// remove this face.
        deal(f->b, f->a, p);
        deal(f->a, f->c, p);
        deal(f->c, f->b, p);
    }
    
    int make() {
        if (n < 4)
            return 0;		
        // find a tetrahedron
        bool ok;
        ok = false;
        for (int i = 1; i < n; i++) {
            if (pt[0] != pt[i]) {
                swap(pt[1], pt[i]);
                ok = true;
                break;
            }
        }
        if (!ok)	return 0;
        ok = false;
        for (int i = 2; i < n; i++) {
            if (cmpZero(tri_area(pt[0], pt[1], pt[i]))) {
                swap(pt[2], pt[i]);
                ok = true;
                break;
            }
        }
        if (!ok)	return 0;
        ok = false;
        for (int i = 3; i < n; i++) {
            if (cmpZero(volume(pt[0], pt[1], pt[2], pt[i]))) {
                swap(pt[3], pt[i]);
                ok = true;
                break;
            }
        }
        if (!ok)	return 0;
        
        tri_num = 0;
        for (int i = 0; i < 4; i++) { // init 4 faces. 
            Face &f = faces[tri_num++];
            f.a = (i+1)%4, f.b = (i+2)%4, f.c = (i+3)%4;
            f.flag = 1;
            if (cmpZero(ptWithFace(pt[i], f)) > 0)
                swap(f.b, f.c);
            g[f.a][f.b] = g[f.b][f.c] = g[f.c][f.a] = &f;
        }
        // add point into convex hull
        for (int i = 4; i < n; i++) {
            for (int j = 0; j < tri_num; j++) {
                if (faces[j].flag && cmpZero(ptWithFace(pt[i], faces[j])) > 0) {
                    dfs(i, &faces[j]);
                    break;
                }
            }
        }
        // remove unused face, trash g[][]
        int tri_n = 0;
        for (int i = 0; i < tri_num; i++) {
            if (faces[i].flag)
                faces[tri_n++] = faces[i];
        }
        tri_num = tri_n; 
        return 1;
    }
    double area() { // surface
        double ret = 0;
        if (n == 3)
            return tri_area(pt[0], pt[1], pt[2]);
        for (int i = 0; i < tri_num; i++)
            ret += tri_area(pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
        return ret;
    }
    double volume() {
        double ret = 0;
        Point3D o(0, 0, 0);
        for (int i = 0; i < tri_num; i++)
            ret += volume(o, pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
        return fabs(ret);
    }
    Point3D getCenter() {
        Point3D ret(0, 0, 0), o = pt[faces[0].a], p;
        double sum, v;
        sum = 0;
        for (int i = 0; i < tri_num; i++) {
            v = volume(o, pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
            p = (pt[faces[i].a] + pt[faces[i].b] + pt[faces[i].c] + o)/4.0;
            if (cmpZero(v) > 0) {
                p = p * v;
                ret = ret + p, sum += v;
            }
        }
        ret = ret / sum;
        return ret;
    }
    int getFaceCount() {
        int ret = 0;
        for (int i = 0; i < tri_num; i++) {
            int ok = 1;
            for (int j = 0; j < i && ok; j++) {
                if (samePlane(faces[i], faces[j]))
                    ok = 0;
            }
            if (ok)
                ret++;
        }
        return ret;
    }
    double getInnerClosestDist(Point3D p) { // p in Conver Hull
        double ret = -1;
        for (int i = 0; i < tri_num; i++) {
            Point3D a, b, c;
            a = pt[faces[i].a], b = pt[faces[i].b], c = pt[faces[i].c];
            
            double t = tri_area(a, b, c);
            double v = fabs(volume(a, b, c, p));
            
            if (ret < 0 || v*3/t < ret)
                ret = v*3/t;
        }
        return ret;
    } 
} A, B;
int main() {
    while (scanf("%d", &A.n) == 1) {
        for (int i = 0; i < A.n; i++)
            A.pt[i].read();
        
        scanf("%d", &B.n);
        for (int i = 0; i < B.n; i++)
            B.pt[i].read();
            
        A.make();
        B.make();
        
        double d1, d2;
        d1 = A.getInnerClosestDist(A.getCenter());
        d2 = B.getInnerClosestDist(B.getCenter());
        printf("%lf\n", d1 + d2);
    }
    return 0;
}
/*
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
5
0 0 5
1 0 6
-1 0 6
0 1 6
0 -1 6
*/
Read More +
解題區/解題區 - UVa

UVa 1581 - Pollution Solution

Problem

計算簡單多邊形與半圓的交集面積

Sample Input

1
2
3
4
5
6
7
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14

Sample Output

1
101.576437872

Solution

Version 1

之前針對簡單多邊形三角剖分，然後去求三角形與圓的關係，還要拆分好幾種可能，考慮共線 … 等複雜操作。

由於最麻煩的地方在於圓與線段之間的關係，想到之前使用 Partition Slab Map，針對 x 座標進行切割，那麼簡單多邊形就會是很多的梯形構成，即便是這樣，梯形還要弄成三角形去跟圓做計算。那換個方式想，直接極角剖分，保證相鄰區間的線段不與圓周相交，接著按照線段中點由遠到近排序，相鄰兩個線段構成梯形，要不全都在內部、外部或者是切一半，切一半也相當好求，拿一個扇形去扣掉一個三角形即可。

算法參考用圖示

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.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);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Pt &a) const {
    	return !(a == *this);
    }
    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 length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
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;
}
struct Seg {
    Pt s, e;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
        return 1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
int inPolygon(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// 
vector<Pt> circleInterectSeg(Pt a, Pt b, double r) {
    vector<Pt> ret;
    Pt c, vab, p;
    double v, lab;
    c = projectLine(a, b, Pt(0, 0));
    vab = a - b, lab = (a - b).length();
    if (cmpZero(c.x * c.x + c.y * c.y - r * r) > 0)
        return ret;
    v = sqrt(r * r - (c.x * c.x + c.y * c.y));
    vab = vab * (v / lab);
    p = c + vab;
    if (onSeg(a, b, p))
        ret.push_back(p);
    p = c - vab;
    if (onSeg(a, b, p))
        ret.push_back(p);
    if (ret.size() == 2 && ret[0] == ret[1])
        ret.pop_back();
    return ret;
}
bool cmp(pair<double, Pt> a, pair<double, Pt> b) {
    return a.first < b.first;
}
bool cmp2(pair<double, Seg> a, pair<double, Seg> b) {
    return a.first < b.first;
}
double scan(vector<Pt> poly, double r) {
    int n = poly.size();
    vector<Pt> all;
    
    for (int i = 0, j = n-1; i < n; j = i++) {
        all.push_back(poly[i]);
        all.push_back(poly[j]);
        vector<Pt> inter = circleInterectSeg(poly[i], poly[j], r);
        for (int k = 0; k < inter.size(); k++)
            all.push_back(inter[k]);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    
    vector< pair<double, Pt> > polar;
    for (int i = 0; i < all.size(); i++) {
        Pt p = all[i];
        polar.push_back(make_pair(atan2(p.y, p.x), p));
    }
    sort(polar.begin(), polar.end(), cmp);
    
    double ret = 0;
    
    for (int i = 0; i < polar.size(); ) {
        vector<Pt> A, B;
        int idx1, idx2;
        double ltheta, rtheta;
        idx1 = i, ltheta = polar[i].first;
        while (idx1 < polar.size() && cmpZero(polar[i].first - polar[idx1].first) == 0)
            A.push_back(polar[idx1].second), idx1++;
        if (idx1 == polar.size()) // end
            break;
        idx2 = idx1, rtheta = polar[idx1].first;
        while (idx2 < polar.size() && cmpZero(polar[idx1].first - polar[idx2].first) == 0)
            B.push_back(polar[idx2].second), idx2++;
        i = idx1;
        
        if (A.size() == 0 || B.size() == 0)
            assert(false);
        
        for (int j = 0, k = n-1; j < n; k = j++) {
            if (cmpZero(cross(Pt(0, 0), A[0], poly[j])) * cmpZero(cross(Pt(0, 0), A[0], poly[k])) < 0)
                A.push_back(getIntersect(Seg(Pt(0, 0), A[0]), Seg(poly[j], poly[k])));
            if (cmpZero(cross(Pt(0, 0), B[0], poly[j])) * cmpZero(cross(Pt(0, 0), B[0], poly[k])) < 0)
                B.push_back(getIntersect(Seg(Pt(0, 0), B[0]), Seg(poly[j], poly[k])));
        }
        
        A.push_back(Pt(0, 0));
        B.push_back(Pt(0, 0));
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        A.resize(unique(A.begin(), A.end()) - A.begin());
        B.resize(unique(B.begin(), B.end()) - B.begin());
        
        vector< pair<double, Seg> > crossEdge;
        for (int p = 0; p < A.size(); p++) {
            for (int q = 0; q < B.size(); q++) {
                if (A[p] == B[q] || A[p] == Pt(0, 0) || B[q] == Pt(0, 0))
                    continue;
                for (int j = 0, k = n-1; j < n; k = j++) {
                    if (onSeg(poly[j], poly[k], A[p]) && onSeg(poly[j], poly[k], B[q])) {
                        Pt mid = (A[p] + B[q]) * 0.5;
                        crossEdge.push_back(make_pair((mid - Pt(0, 0)).length(), Seg(A[p], B[q])));
                    }
                }
            }
        }
        crossEdge.push_back(make_pair(0.0, Seg(Pt(0, 0), Pt(0, 0))));
        sort(crossEdge.begin(), crossEdge.end(), cmp2);
        for (int j = 0; j < crossEdge.size() - 1; j++) {
            Seg a = crossEdge[j].second;
            Seg b = crossEdge[j+1].second;
            Pt ma = (a.s + a.e) * 0.5;
            Pt mb = (b.s + b.e) * 0.5;
            Pt mab = (ma + mb) * 0.5;
            if (!inPolygon(poly, mab))
                continue;
            double area = (fabs(cross(b.s, b.e, a.e)) + fabs(cross(a.s, a.e, b.s))) /2;
            
            int inout[4] = {}, all_in, all_out;
            inout[0] = cmpZero((a.s - Pt(0, 0)).length() - r) <= 0;
            inout[1] = cmpZero((a.e - Pt(0, 0)).length() - r) <= 0;
            inout[2] = cmpZero((b.s - Pt(0, 0)).length() - r) <= 0;
            inout[3] = cmpZero((b.e - Pt(0, 0)).length() - r) <= 0;
            all_in = inout[0] & inout[1] & inout[2] & inout[3];
            all_out = (!inout[0]) & (!inout[1]) & (!inout[2]) & (!inout[3]);			
//			printf("area %lf\n", area);
//			printf("%lf %lf, %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
//			printf("%lf %lf, %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
            if (all_out) {
//				printf("no %lf\n", 0);
                continue;
            }
            if (all_in) {
//				printf("all %lf\n", area);
                ret += area;
                continue;
            }
            if (inout[0] == 1 && inout[1] == 1) {
//				printf("part %lf\n", r * r * (rtheta - ltheta)/2 - fabs(cross(Pt(0, 0), a.s, a.e)) /2);
                ret += r * r * (rtheta - ltheta)/2 - fabs(cross(Pt(0, 0), a.s, a.e)) /2;
            } else {
//				printf("no %lf\n", 0);
            }
        }
//		puts("---");
    }
    
    return ret;
}
int main() {
    int n;
    double r, x, y;
    while (scanf("%d %lf", &n, &r) == 2) {
        vector<Pt> poly;
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            poly.push_back(Pt(x, y));
        }
        
        double ret = scan(poly, r);
        printf("%.9lf\n", ret);
    }
    return 0;
}
/*
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
4 10
10 0
10 10
-10 10
-10 0
6 10
2 2
12 2
6 4
12 4
8 8
-2 8
5 10
-4 6
-2 2
0 4
4 2
8 4
*/

Version 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
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.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);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Pt &a) const {
    	return !(a == *this);
    }
    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 length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
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;
}
struct Seg {
    Pt s, e;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
        return 1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
int inPolygon(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// 
vector<Pt> circleInterectSeg(Pt a, Pt b, double r) { // maybe return same point
    vector<Pt> ret;
    Pt c, vab, p;
    double v, lab;
    c = projectLine(a, b, Pt(0, 0));
    if (cmpZero(c.x*c.x + c.y*c.y - r*r) > 0)
        return ret;
    vab = a - b, lab = (a - b).length();
    v = sqrt(r * r - (c.x * c.x + c.y * c.y));
    vab = vab * (v / lab);
    if (onSeg(a, b, c + vab))
        ret.push_back(c + vab);
    if (onSeg(a, b, c - vab))
        ret.push_back(c - vab);
    return ret;
}
double circleWithTriangle(double r, Pt a, Pt b) { // get intersect area
    Pt o = Pt(0, 0);
    double la = (a - Pt(0, 0)).length();
    double lb = (b - Pt(0, 0)).length();
    
    if (cmpZero(cross(o, a, b)) == 0)
        return 0;
    
    if (cmpZero(la - r) <= 0 && cmpZero(lb - r) <= 0)
        return fabs(cross(o, a, b))/2;
    
    if (cmpZero(la - r) <= 0 || cmpZero(lb - r) <= 0) {
        if (cmpZero(la - r) > 0)
            swap(a, b), swap(la, lb);
        // a in circle, b not in circle
        vector<Pt> c = circleInterectSeg(a, b, r);
        assert(c.size() > 0);
        
        if (c.size() > 1 && c[0] == a)
            swap(c[0], c[1]);
        double theta = getAngle(c[0], b);
        double ret = 0;
        
        ret += fabs(cross(o, a, c[0]))/2;
        ret += r * r * theta/2;
        
        return ret;
    }
    // a not in circle, b not in circle
    vector<Pt> c = circleInterectSeg(a, b, r);
    if (c.size() == 0) {
        double theta = getAngle(a, b);
        return r * r * theta/2;
    } else {
        assert(c.size() == 2);
        if (dot(c[0] - a, b - a) > dot(c[1] - a, b - a))
            swap(c[0], c[1]);
        double theta1 = getAngle(a, c[0]);
        double theta2 = getAngle(c[1], b);
        double ret = 0;
        
        ret += r * r * (theta1+theta2)/2;
        ret += fabs(cross(o, c[0], c[1]))/2;
        return ret;
    }
    return 0;
}
int main() {
    int n;
    double r, x, y;
    while (scanf("%d %lf", &n, &r) == 2) {
        vector<Pt> poly;
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            poly.push_back(Pt(x, y));
        }
        
        double ret = 0;
        for (int i = 0; i < n; i++) {
            double area = circleWithTriangle(r, poly[i], poly[(i+1)%n]);
            
            if (cmpZero(cross(Pt(0, 0), poly[i], poly[(i+1)%n])) > 0)
                ret += area;
            else
                ret -= area;
        }
        printf("%.9lf\n", fabs(ret));
    }
    return 0;
}
/*
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
4 10
10 0
10 10
-10 10
-10 0
6 10
2 2
12 2
6 4
12 4
8 8
-2 8
5 10
-4 6
-2 2
0 4
4 2
8 4
*/
Read More +
解題區/解題區 - UVa

UVa 1566 - John

Problem

撿石子遊戲，但是相反地拿走最後一個的人輸。

(通常 Nim 遊戲都是無法進行操作的人輸)

Sample Input

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

Sample Output

1
2
John
Brother

Solution

上網搜索一下 Sprague Grundy - Jia Zhihao，簡單地說曾經有個大陸人在選訓隊講這個，所以不太算是定理名稱。

有興趣的人可以上網搜尋，主要細分四種狀態，是否每一堆大小都為 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
// Anti-SG, Sprague Grundy - Jia Zhihao
#include <stdio.h> 
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int sg = 0, s1 = 1;
        int x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            sg ^= x;
            s1 &= x <= 1;
        }
        if (s1)
            printf("%s\n", sg == 0 ? "John" : "Brother");
        else
            printf("%s\n", sg ? "John" : "Brother");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1558 - Number Game

Problem

給予 2 到 20 的內數字，兩名玩家輪流挑一個數字 x，並且將 x 的倍數遮蔽、x 倍數和已經被遮蔽的數字和也應該被遮蔽。

被遮蔽的數字將無法被使用。無法選擇任何數字的人輸。給定盤面上剩餘可選的數字，請問先手在第一步可以選擇哪幾個數字獲得勝利。

Sample Input

1
2
3
4
5
2
1
2
2
2 3

Sample Output

1
2
3
4
5
Scenario #1:
The winning moves are: 2.
Scenario #2:
There is no winning move.

Solution

由於數字量很小，可以進行 bitmask 壓縮，來得知數字的使用情況。接著套用博弈 dp 的思路，來得知必勝狀態！

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1<<20];
int pick(int state, int x) {
    for (int i = x; i <= 20; i += x)
        if ((state>>(i-2))&1)
            state ^= 1<<(i-2);
    
    for (int i = x; i <= 20; i++) {
        if ((state>>(i-2))&1) {
            if (i - x >= 2) {
                if (((state>>(i - x -2))&1) == 0)
                    state ^= 1<<(i-2);
            }
        }
    }
    return state;
}
int dfs(int state) {
    if (state == 0)	
        return 0;
    if (dp[state] != -1)	
        return dp[state];
    int &ret = dp[state];
    ret = 0;
    for (int i = 2; i <= 20; i++) {
        if ((state>>(i-2))&1) {
            int v = dfs(pick(state, i));
            ret |= !v;
            if (ret) break;
        }
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        int mask = 0, x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            mask |= 1<<(x-2);
        }
        
        printf("Scenario #%d:\n", ++cases);
        vector<int> ret;
        for (int i = 2; i <= 20; i++) {
            if ((mask>>(i-2))&1) {
                int v = dfs(pick(mask, i));
                if (v == 0)
                    ret.push_back(i);
            }
        }
        if (ret.size() == 0)
            puts("There is no winning move.");
        else {
            printf("The winning moves are:");
            for (int i = 0; i < ret.size(); i++)
                printf(" %d", ret[i]);
            puts(".");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1557 - Calendar Game

Problem

給一個起始日期，兩名玩家輪流操作，操作方式有兩種，將日期往後延一天，將月份往後延一個月，抵達 November 4, 2001 的人獲勝，如果發生移動到不合法的日期則視為無效。

必須考慮閏年變化。

Sample Input

1
2
3
4
3
2001 11 3
2001 11 2
2001 10 3

Sample Output

1
2
3
YES
NO
NO

Solution

由於年份差最多 100，可以直接根據年月日做狀態搜索。要處理移動時，發生跨年、跨月，這方面會稍微麻煩一點。閏年要額外處理對 2/29 的日期判斷，並且移動時不可超出指定的日期之後。

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 <string.h>
#include <algorithm>
using namespace std;
const int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dp[128][16][32], used[128][16][32], dcases = 0;
int validDate(int yyyy, int mm, int dd) {
    if (mm < 1 || mm > 12)	
        return 0;
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0) {
        if (mm == 2) {
            if (dd < 1 || dd > 29)	
                return 0;
        } else {
            if (dd < 1 || dd > mday[mm])
                return 0;
        }			
    } else {
        if (dd < 1 || dd > mday[mm])
            return 0;
    }
    return 1;
}
int complete(int yyyy, int mm, int dd) {
    return yyyy == 2001 && mm == 11 && dd == 4;
}
int fail(int yyyy, int mm, int dd) {
    if (!validDate(yyyy, mm, dd))
        return 1;
    if (yyyy > 2001)	return 1;
    if (yyyy < 2001)	return 0;
    if (mm > 11)		return 1;
    if (mm < 11)		return 0;
    if (dd > 4)			return 1;
    if (dd < 4)			return 0;
    return 0;
}
void nextMonth(int &yyyy, int &mm, int &dd) {
    mm++;
    if (mm == 13)	yyyy++, mm = 1;
}
void nextDay(int &yyyy, int &mm, int &dd) {
    int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0)
        mday[2] = 29;
    dd++;
    if (dd > mday[mm])
        mm++, dd = 1;
    if (mm == 13)	yyyy++, mm = 1;
}
int dfs(int yyyy, int mm, int dd) {
    if (fail(yyyy, mm, dd))
        return 0;
    if (complete(yyyy, mm, dd))
        return 1;
    if (used[yyyy-1900][mm][dd] == dcases)
        return dp[yyyy-1900][mm][dd];
    int &ret = dp[yyyy-1900][mm][dd];
    int y, m ,d;	
    ret = 0, used[yyyy-1900][mm][dd] = dcases;
    
    y = yyyy, m = mm, d = dd;
    nextMonth(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    
    y = yyyy, m = mm, d = dd;
    nextDay(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    return ret;
}
int main() {
    int testcase;
    int yyyy, mm, dd;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &yyyy, &mm, &dd);
        dcases ++;
        printf("%s\n", dfs(yyyy, mm, dd) ? "YES" : "NO");
    }
    return 0;
}
/*
3
2001 11 3
2001 11 2
2001 10 3
*/
Read More +
解題區/解題區 - UVa

UVa 1534 - Taekwondo

Problem

題目模型與 Zerojudge a192 接線問題 一樣。

題目背景在跆拳道選手，有兩團人馬，希望兩兩配對，體重差的絕對值總和越小越好。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2  
2 3
44.9 
50.0 
77.2 
86.4 
59.8 
4 2  
44.9 
50.0 
77.2 
86.4 
59.8 
58.9

Sample Output

1
2
42.1 
23.8

Solution

按照以前的思路來看，維護的是前一個最後匹配到的人是誰，這樣的效率保證是 $O(N^2)$，這樣的效能已經相當快，中間運用到維護最小值的技巧，由於前 i-1 個人匹配到前 j 個人的最小值，那麼 i 匹配到 k 時，需要的是 min(dp[i-1][0 <= j < k])，邊掃描邊維護。

看到網路上有一個不錯的定義，採用失匹配幾個人，較多人數的那一方，將會有幾個人無法匹配，也因此紀錄第 i 個人時，另一團人有 j 個人沒匹配到，那麼當前第 i 個人，必然要與編號 i + j 的人匹配。

忘了提及，一定要先排序，轉換到接線問題時，交錯匹配的距離會比較長，這部分屬於貪心。

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
#include <stdio.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
int dp[512][512]; // dp[i-th match in A][#miss match in B]
void solve(vector<int> A, vector<int> B) {
    assert(A.size() <= B.size());
    int n1 = A.size(), n2 = B.size();
    int diff = n2 - n1;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    for (int i = 0; i < n1; i++) {
        int mn = 0x3f3f3f3f;
        for (int j = 0; j <= diff; j++) {
            if (i == 0)
                mn = 0;
            else
                mn = min(mn, dp[i-1][j]);
            dp[i][j] = mn + abs(A[i] - B[i + j]);
        }
    }
    
    int ret = 0x3f3f3f3f;
    for (int i = 0; i <= diff; i++)
        ret = min(ret, dp[n1-1][i]);
    printf("%d.%d\n", ret/10, ret%10);
}
int main() {
    int testcase;
    int n1, n2, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n1, &n2);
        vector<int> A, B;
        for (int i = 0; i < n1; i++) {
            scanf("%d.%d", &x, &y);
            A.push_back(x * 10 + y);
        } 
        for (int i = 0; i < n2; i++) {
            scanf("%d.%d", &x, &y);
            B.push_back(x * 10 + y);
        } 
        
        if (n1 < n2)
            solve(A, B);
        else
            solve(B, A);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 996 - Find the Sequence

Problem

這一題是 UVa 997 - Show the Sequence 的反運算，給定序列找到操作的產生方法。

Sample Input

1
2
3 10 30 30 -30 90 -450 3150
2 2 6 36 360 5400 113400

Sample Output

1
2
[2*[5+[-2]]]
[0]

Solution

由於每一個數字不算大，而且從操作方法中得知，數字大小的增長速度非常快，對於累加的部分可以 O(1) 窮舉，但是對於乘積部分需要窮舉因數來得知。

由於題目不是 special judge 也擔心就算找到答案是不是唯一解，按著 Dfs 搜索的順序就 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
#include <stdio.h>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
string num2str(int x) {
    string s;
    stringstream sin(s);
    sin << x;
    return sin.str();
}
int dfs(vector<int> A, int M, string &solution) {
//    printf("[");
//    for (int i = 0; i < A.size(); i++)
//        printf("%d ", A[i]);
//    puts("]");
    int same = 1;
    for (int i = 1; i < A.size(); i++)
        same &= A[i] == A[0];
    if (same == 1) {
        solution = "[" + num2str(A[0]) + "]";
        return 1;
    }
    if (M <= 0)  return 0;
    int g = A[0];
    for (int i = 0; i < A.size(); i++) {
        if (A[i] == 0) {
            g = 0;
            break;
        }
        g = __gcd(g, A[i]);
    }
    for (int i = 1; i < A.size(); i++) {
        if (A[i-1] != 0 && A[i]%A[i-1] != 0)
            g = 0;
        if (A[i-1] == 0 && A[i] != 0)
            g = 0;
    }
    if (g < 0)  g = -g;
    if (g > 0) {
        for (int m = 1; m <= g; m++) {
            if (g%m == 0) {
                vector<int> nA;
                nA.push_back(A[0] / m);
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(m) + "*" + solution + "]";
                    return 1;
                }
                nA.clear();
                nA.push_back(A[0] / (-m));
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(-m) + "*" + solution + "]";
                    return 1;
                }
            }
        }
    }
    vector<int> nA;
    for (int i = 1; i < A.size(); i++)
        nA.push_back(A[i] - A[i-1]);
    if (dfs(nA, M-1, solution)) {
        solution = "[" + num2str(A[0]) + "+" + solution + "]";
        return 1;
    }
    return 0;
}
int main() {
    int M, x;
    string line;
    while (getline(cin, line)) {
        stringstream sin(line);
        sin >> M;
        vector<int> A;
        while (sin >> x)
            A.push_back(x);
        string solution;
        int f = dfs(A, M, solution);
        if (f == 0)
            puts("[0]");
        else
            puts(solution.c_str());
    }
    return 0;
}
/*
 3 10 30 30 -30 90 -450 3150
 2 2 6 36 360 5400 113400
*/
Read More +
解題區/解題區 - UVa

UVa 953 - The Incredible Pile Machine

Problem

現在有 N 堆，總共有 N 種物品，希望移動最少次，使得每一堆只具有單一種物品。

輸出最小的組合方案。按照第 i 種物品放置在第 j 堆的字典順序最小。

Sample Input

1
2
3
4
5
6
7
4
3 2 3 4 0 0 2 1 3 1
3 66 66 0 66 66 0 66 66 66
6 476 357 874 50 594 394 320 803 817 348 252 940 453 500 647 299
94 143 800 947 561 885 389 172 301 276 612 130 540 731 774 306 96
239 227 907
2 99 1 1 99

Sample Output

1
2
3
4
021 9
012 264
251340 12741
01 2

Solution

很明顯地答案會是在某一堆 X 指派給 A 物品，那麼可以減少的移動次數是 X 原本具有 A 的數量。因此答案會是物品述兩總和扣除最大權匹配。

但是答案特別要求輸出字典順序要最小，所以用 KM 算法、最少費用流會稍微麻煩一點，也許多做 $O(N^2)$ 次的窮舉也可以完成。這裡使用 bitmask 的方式去找到最順序最小的最大權匹配。

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 <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10;
int dp[MAXN][1<<MAXN], used[MAXN][1<<MAXN];
int main() {
    int testcase, N;
    int type[20][20];
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	
    	int sum = 0;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++)
    			scanf("%d", &type[i][j]), sum += type[i][j];
    	}
    	    	
    	memset(dp, 0, sizeof(dp));
    	memset(used, 0, sizeof(used));
    	for (int i = 0; i < N; i++)
    		dp[0][1<<i] = type[0][i];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    dp[i+1][j|(1<<k)] = max(dp[i+1][j|(1<<k)], dp[i][j] + type[i+1][k]);
                }
            }
        }
        
        used[N-1][(1<<N) - 1] = 1;
        for (int i = N-2; i >= 0; i--) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    if (used[i+1][j|(1<<k)] && dp[i+1][j|(1<<k)] == dp[i][j] + type[i+1][k])
                        used[i][j] = 1;
                }
            }
        }
        int ret = dp[N-1][(1<<N)-1];
        for (int i = 0, p, q = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((q>>j)&1)
                    continue;
                if (used[i][q|(1<<j)]) {
                    p = j, q |= 1<<j;
                    break;
                }
            }
            printf("%d", p);
        }
        printf(" %d\n", sum - ret);
    }
    return 0;
}
Read More +