解題區/解題區 - UVa

UVa 12194 - Isosceles Triangles

Problem

A given triangle can be either equilateral (three sides of the same length), scalene (three sides of different lengths), or isosceles (two sides of the same length and a third side of a different length). It is a known fact that points with all integer coordinates cannot be the vertices of an equilateral triangle.

You are given a set of different points with integer coordinates on the XY plane, such that no three points in the set lay on the same line. Your job is to calculate how many of the possible choices of three points are the vertices of an isosceles triangle.

Input

There are several test cases. Each test case is given in several lines. The first line of each test case contains an integer N indicating the number of points in the set (3$\le$N$\le$1000). Each of the next N lines describes a different point of the set using two integers X and Y separated by a single space (1$\le$X, Y$\le$106); these values represent the coordinates of the point on the XY plane. You may assume that within each test case no two points have the same location and no three points are collinear.

The last test case is followed by a line containing a single zero.

Output

For each test case output a single line with a single integer indicating the number of subsets of three points that are the vertices of an isosceles triangle.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 
1 2 
2 1 
2 2 
1 1 
1000 1000000 
6 
1000 1000 
996 1003 
996 997 
1003 996 
1003 1004 
992 1000 
0

Sample Output

1
2
4
10

Solution

題目描述：

給平面 N 個點，任挑三個點有多少以某個節點為頂點的等腰三角形。

題目解法：

直接對單一頂點找到對於其他頂點的的所有距離，排序後找重複的長度進行組合計算，將複雜度 O(n^3) 降到 O(n^2 log 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
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int N;
    long long X[1024], Y[1024];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++)
            scanf("%lld %lld", &X[i], &Y[i]); 
        long long d[1024];
        long long ret = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                d[j] = (X[i] - X[j]) * (X[i] - X[j]) +
                        (Y[i] - Y[j]) * (Y[i] - Y[j]);
            sort(d, d+N);
            long long cnt = 1;
            d[N] = -1;
            for(int j = 1; j <= N; j++) {
                if(d[j] != d[j-1]) {
                    ret += cnt * (cnt-1) /2;
                    cnt = 1;
                } else {
                    cnt++;
                }
            } 
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12191 - File Recover

Problem

Your school has a computer that is used as a web server for hosting its institutional web site, personal pages of the staff, sites for research groups, subjects, and many others.

Recently, the hard disk table was corrupted, so the organization of all the files was lost. Sadly enough, there are no backups of that information. The only hope is to look through the entire disk data and try to find out which parts correspond to each file. Fortunately, the disk was using a file system that kept each individual file contiguous, so only contiguous pieces of data need to be inspected.

The disk data is a sequence of bytes. Each byte in this particular disk can store an English alphabet letter (distinguishing lowercase and uppercase), a decimal digit, a point or a comma, making a total of 64 different characters.

While you were thinking about how to solve the problem, you suddenly remembered that the file system also maintained multiple copies of each file, so only the pieces of contiguous bytes that are repeated had a chance of being a file. Moreover, for each repetition of the same contiguous bytes, only one copy needs to be checked. For instance, if the data is ababcabb', the contiguous subsequencesa’, b' andab’ are repeated, but nothing containing c', norba’ or `bb’ is. Therefore, we have 3 pieces of contiguous bytes that need checking in this case.

You decide to write a program that computes exactly how many sequences need checking, that is, the number of different sequences of contiguous bytes that appear at least twice in the data.

Input

There are several test cases. The input of each test case is given in exactly one line, containing a non-empty string of at most 105 characters that represents the disk data. Each character in the string is either a lowercase letter, an uppercase letter, a digit, a point or a comma.

The last test case is followed by a line containing a single asterisk.

Output

For each test case output a single line with an integer, representing the number of different contiguous subsequences that appear at least twice in the input string.

Sample Input

1
2
3
4
5
6
ababcabb 
mississippi 
aaaaaaaaaaaaaaaaaaaaaaaaaa 
012345678,abcdefg.STUVWXYZ 
say.twice,say.twice 
*

Sample Output

1
2
3
4
5
3 
9 
25 
0 
45

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct SuffixArray {
    int sa[100005], h[100005], n;
    int w[100005], ta[100005], tb[100005];
    char str[100005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
    while(scanf("%s", in.str)) {
    	if(!strcmp("*", in.str))
    		break;
        in.build();
        in.build_h();
//		for(int i = 0; i < in.n; i++)
//			printf("%s %d\n", in.str + in.sa[i], in.h[i]);
        long long ret = 0, base = 0;
        in.h[in.n] = -1;
        for(int i = 1; i <= in.n; i++) {
            if(in.h[i] < in.h[i-1])
                ret += in.h[i-1] - base, base = in.h[i];
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12176 - Bring Your Own Horse

Problem

One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.

This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.

Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.

The places are designated by consecutive integers from 1 to $N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $N$ places.

Input

The first line contains the total number of test cases that follow.

Each test case begins with a line that first holds the number $N$ of places ( $1 \le N \le 3000$ ) followed by the number $R$ of roads ( $1 \le R \le 100000$ ). Then there are $R$ lines with three integers each ($a$ , $b$ , and $l$ ), each of which defines a road connecting the places $a$ and $b$ ( $1 \le a, b \le N$ ) with length $l$ ( $1 \le l \le 1000000$ ).

Thereafter, each test case continues with the number $Q$ of queries on a line by itself ( $1 \le Q \le 1000$ ). Each of the next $Q$ lines holds two integers $k$ and $t$ , indicating a query by a knight who lives at place $k$ and needs to go to a tournament at place $t$ ( $1 \le k, t \le N$ , $k \neq t$ ).

Output

For each test case output a line containing the word ``Case’’, a single space, and its serial number (starting with $1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.

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
2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1
``` 
## Sample Output ##

Case 1
100

Case 2
2
5
3
5
```

Solution

題目描述：

騎士每天活動只會從該點移動到盡可能短的路徑到下一個點，求從起點到終點之間的最小的最長路為何。

題目解法：

由於詢問兩個點之間的路徑上的最小值最大邊，不外乎地可以先做一次最小成本樹，根據定義，拆分成 s - t 集合，最小成本樹的邊一定是 s - t 之間的最小邊。

接著詢問在樹上進行即可，因此每次詢問最慘會到 O(n)。

那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。

因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。

在同一水平下，還是需要知道 LCA 的所在高度，否則也可以水平線不斷地一步一步往上提，雖然最慘也許是 O(n) 但是經由之前的調整已經很加速很多。

本來應該套用 LCA Tarjan 的作法來加速，但是還沒有做到這樣的地步速度就很快。如果詢問次數再多一點就必須做到這一步。

有點懶惰 Orz。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[100005];
vector<E> tree[3005];
int p[3005], rank[3005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        p[i] = i, rank[i] = 1;
        tree[i].clear();
    }
    
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
        	sum += D[i].v;
        	tree[D[i].x].push_back(E(D[i].x, D[i].y, D[i].v));
        	tree[D[i].y].push_back(E(D[i].y, D[i].x, D[i].v));
//        	printf("mmm %d %d %d\n", D[i].x, D[i].y, D[i].v);
        }
    }
    return sum;
}
int dp[4096][20], dpw[4096][20];
int treeLevel[4096], treePath[4096];
void dfs(int u, int p, int level) {
    treeLevel[u] = level, treePath[level] = u;	
    for(int i = 1; (1<<i) < level; i++) {
        dp[u][i] = max(dp[u][i-1], dp[dpw[u][i-1]][i-1]);
        dpw[u][i] = treePath[level-(1<<i)];
    }
    for(int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if(v == p)	continue;		
        dp[v][0] = tree[u][i].v;
        dpw[v][0] = u;
        dfs(v, u, level + 1);
    }
}
int query(int x, int y) {
    int hx = treeLevel[x], hy = treeLevel[y];
    int ret = 0;
    while(x != y && hx != hy) {
        for(int i = 15; i >= 0; i--) {
            if(abs(hx-hy) >= (1<<i)) {
                if(hx > hy) {
                    ret = max(ret, dp[x][i]);
                    x = dpw[x][i];
                    hx -= (1<<i);
                } else {
                    ret = max(ret, dp[y][i]);
                    y = dpw[y][i];
                    hy -= (1<<i); 
                }
            }
        }
    }
    while(x != y) {
        ret = max(ret, dp[x][0]);
        x = dpw[x][0];
        hx -= (1<<0);
        ret = max(ret, dp[y][0]);
        y = dpw[y][0];
        hy -= (1<<0); 
    }
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, q, x, y;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);        	
        }
        
        int mstcost = kruscal(n, m);
        memset(dp, 0, sizeof(dp));
        memset(dpw, 0, sizeof(dpw));
        dfs(1, -1, 1);
        
//		for(int i = 1; i <= n; i++, puts("")) {
//			printf("[%2d] :", i);
//			for(int j = 0; (1<<j) <= n; j++)
//				printf("%d %d, ", dp[i][j], dpw[i][j]);
//		}
        scanf("%d", &q);
        printf("Case %d\n", ++cases);
        while(q--) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        }
        puts("");
    }
    return 0;
}
/*
5
10 45
1 2 15
1 3 11
1 4 48
1 5 24
1 6 45
1 7 18
1 8 12
1 9 40
1 10 11
2 3 4
2 4 9
2 5 44
2 6 23
2 7 39
2 8 48
2 9 48
2 10 22
3 4 42
3 5 37
3 6 10
3 7 18
3 8 29
3 9 8
3 10 47
4 5 7
4 6 17
4 7 25
4 8 23
4 9 32
4 10 27
5 6 26
5 7 21
5 8 38
5 9 40
5 10 39
6 7 35
6 8 11
6 9 39
6 10 1
7 8 15
7 9 10
7 10 47
8 9 28
8 10 11
9 10 1
30
1 6
5
10 45
1 2 9
1 3 12
1 4 21
1 5 4
1 6 32
1 7 20
1 8 14
1 9 28
1 10 16
2 3 12
2 4 23
2 5 27
2 6 34
2 7 43
2 8 2
2 9 33
2 10 35
3 4 41
3 5 26
3 6 16
3 7 39
3 8 2
3 9 49
3 10 44
4 5 24
4 6 2
4 7 17
4 8 26
4 9 20
4 10 2
5 6 23
5 7 5
5 8 41
5 9 12
5 10 15
6 7 48
6 8 45
6 9 13
6 10 28
7 8 25
7 9 12
7 10 37
8 9 4
8 10 5
9 10 41
30
5 4
1 7
8 4
*/
Read More +
解題區/解題區 - UVa

UVa 12045 - Fun with Strings

Problem

Zibon just started his courses in Computer science. After having some lectures on programming courses he fell in love with strings. He started to play with strings and experiments on them. One day he started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b’s with ab and all the a’s with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the Nth string has the length X and Mth string has the length Y. He wondered what will be length of the Kth string. Can you help him?

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Five integers N, X, M, Y and K where (0 < N, M, X, Y, K < 109 and N ≠ M).

Output

For each test case produce one line of output giving either the number which is desired length (modulo 1000000007) or the string “Impossible”. You output Impossible if the given input is not possible.

Sample Input

1
2
3
2
3 16 5 42 6
5 1 6 10 9

Sample Output

1
2
68
Impossible

Solution

題目描述：

一開始由 a, b 構成的字串，每一次操作會將 a 換成 b, 將 b 換成 ab。
在第 N 次之後長度為 X、第 M 次之後長度為 Y，求第 K 次之後長度為何？

題目解法：

看到 a 換成 b, 將 b 換成 ab，其實只考量數量關係，很明顯是一個費式數列的關係。
因此，只要假設一開始有多少個 a，有多少個 b 在一開始的字串中，利用兩條方程式求解，之後再帶入費式數列的快速運算即可。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Matrix {
    long long v[2][2];
    Matrix(long long a = 0) {
        memset(&v, 0, sizeof(v));
        for(int i = 0; i < 2; i++)
            v[i][i] = a;
    }
};
const long long mod = 1000000007LL;
Matrix multiply(Matrix x, Matrix y) {
    Matrix z;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++) {
                z.v[i][j] += x.v[i][k] * y.v[k][j] %mod;
                z.v[i][j] %= mod;
            }
    return z;
}
Matrix pow(Matrix x, long long y) {
    Matrix v(1);
    while(y) {
        if(y&1)
            v = multiply(v, x);
        y = y>>1, x = multiply(x, x); 
    }
    return v;
}
int main() {
    int testcase;
    long long N, X, M, Y, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld %lld %lld %lld", &N, &X, &M, &Y, &K);
        Matrix mm, na, nb, nc;
        mm.v[0][0] = mm.v[0][1] = mm.v[1][0] = 1;
        na = pow(mm, N);
        nb = pow(mm, M);
        nc = pow(mm, K);
        long long a1, b1, c1, a2, b2, c2;
        long long d, dx, dy;
        a1 = na.v[0][0], b1 = na.v[1][0], c1 = X;
        a2 = nb.v[0][0], b2 = nb.v[1][0], c2 = Y;
        d = a1 * b2 - a2 * b1;
        dx = X * b2 - Y * b1, dy = a1 * Y - a2 * X;
        if(d == 0 || dx%d || dy%d || dx/d < 0 || dy/d < 0)
            puts("Impossible");
        else {
            long long a = dx/d, b = dy/d;
            printf("%lld\n", (a * nc.v[0][0]%mod + b * nc.v[1][0]%mod)%mod);
        }
//		printf("%lld A + %lld B = %lld\n", na.v[0][0], na.v[1][0], X);
//		printf("%lld A + %lld B = %lld\n", nb.v[0][0], nb.v[1][0], Y);
//		printf("%lld A + %lld B = ????\n", nc.v[0][0], nc.v[1][0]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12042 - Colorful Eggs

Problem

Little Mou is very fond of eggs. She has n baskets for keeping her colorful eggs. Each basket contains eggs of different colors. The baskets are numbered from 1 to n. She has a strange hobby about these eggs. On each day, she takes each basket starting from the nth basket. When she is doing this for basket i, she counts all eggs placed in baskets 1 to i (inclusive) and takes their sum. Let this value of sum be counti. She removes all old eggs from the ith basket and keeps counti new eggs in the ith basket. After that she puts all the old eggs of the ith basket in the (i-1)th basket removing the old eggs of the (i-1)th basket. As Mou is very fond of eggs, she eats all old eggs of the (i-1)th basket. And when she has finished eating, she repeats the work for this (i-1)th basket. If she reaches the 1st basket, she stops her work and doesn’t eat any more eggs and goes to sleep!

For example let Mou has 3 baskets at day 1. 1st basket contains 1 egg, 2nd basket contains 1 egg and the 3rd basket contains 2 eggs.

So simulation for day 3 follows:

Basket Index => 3 2 1

….. 略

Now the problem is given n, d and the number of eggs in each basket eggi, your job is to find the number of eggs in each basket after d days. As the number can be very big output answer modulo 1,000,000,007.

Input

The first line of the input file contains an integer T (T ≤ 111) which denotes the total number of test cases. The description of each test case is given below:

Two integers N (1 ≤ n ≤ 60) and d (1 ≤ d ≤ 1,000,000,000), followed by n integers denoting the number of eggs in each basket starting from 1 to n.
Output

For each test case print one line of output containing the number of eggs in each basket after d days have passed separated by single spaces between them. See the sample output for more details. As the numbers can be very big output answer modulo 1,000,000,007.

Sample Input

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

Sample Output

1
2
3
129 189 277
5 9
1 10

Solution

題目描述：

一開始有 n 籃雞蛋，每一籃有各自個雞蛋數量。

每一次的操作從最右邊 (編號大的那籃開始) 進行，將所有比它小的編號的雞蛋總數加到這一籃，並且將原本的雞蛋總數指派給下一個籃。

問第 d 天後的結果。

題目解法：

建造轉移矩陣，使用 D&C 完成。

觀察一下可以發現，矩陣肯定長成這副德性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[1, 1, 1, ..., 1, 1, 1]
[1, 0, 1, ..., 1, 1, 1]
[1, 0, 0, 1, ..., 1, 1] = M
[1, 0, 0, 0, ..., 1, 1]
...
[1, 0, 0, 0, ..., 0, 0]
[an]
[an-1]
[an-2] = A(1)
...
[a1]
M x A(1) = A(2)
M x M x A(1) = A(3)
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>
const long long mod = 1000000007LL;
struct Matrix {
    long long v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, long long a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < x.col; j++)
                for(int k = 0; k < col; k++)
                    ret.v[i][j] += v[i][k] * x.v[k][j] %mod,
                    ret.v[i][j] %= mod;
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int testcase, n, d, a[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &d);
        d--;
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        Matrix x(n, n), A(n, 1);
        for(int i = 0; i < n; i++)
            A.v[i][0] = a[n-i-1];
        for(int i = 0; i < n; i++)
            x.v[0][i] = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                x.v[i][j] = 1;
            }
            x.v[i][0] = 1;
        }
        Matrix y = x ^ d;
        Matrix r = y * A;
        for(int i = r.row-1; i >= 0; i--) { 
            printf("%lld", r.v[i][0]);
            if(i)	putchar(' ');
        } 
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12040 - Again Lucky Numbers

Problem

Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. But I believe that 7 is an unlucky number and want to avoid it. So unlucky number is different for man to man. If 13 is an unlucky number and in a number there is no 13 (i.e. no ‘1’ is followed by a ‘3’) then we can call it a lucky number. For example, if we consider 13 as an unlucky number then 12345 is a lucky number. But if any number contains 13 then it is not a lucky number, such as 13254 and 21345 are not lucky numbers. Given the number of digits N in a number and the unlucky number M, you have to find out how many lucky numbers are possible with N digits considering that M is unlucky number. Note that leading 0’s are not allowed. So, 011 is not a valid three digit number.

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Two positive integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10100).

Output

For each test case print the number of lucky numbers of N digits considering that M is the unlucky number. The result may be very large. You have to output the result modulo 10000007.

Sample Input

1
2
3
4
3
1 3
2 13
2 1

Sample Output

1
2
3
9
89
72

Solution

題目描述：

找到長度為 n 的數字，並且數字中不會出現指定的數字為 substring，求符合數字的總數。

題目解法：

特別考慮以 0 開頭的情況 (n 位數字前導不可為 0，但 n = 1 位數字可以是 0)。
最後，建造一台 AC 自動機，接著對於每一個節點著手 dp 轉移。

也就是考慮再將字串進行 AC 自動機匹配時所會遇到的所有轉移情況，因此我們要避免出現指定的字符串時，在結尾處標記不可轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// http://mypaper.pchome.com.tw/zerojudge/post/1324462879
// AC 自動機 DP
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[105]; // [string length]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
const int mod = 10000007;
long long dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    long long ans, ret = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = (k == 0); i < 10; i++) { // leading 0's are not allowed
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] += nd->dp[k];
                    nd->next[i]->dp[k+1] %= mod;
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL) // error message
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                    p->dp[k+1] %= mod;
                }
            }
            ans += nd->dp[k];
            ans %= mod;
        }
        if(k == len) {
            ret += ans;
            ret %= mod;
        }
    }
    return ret;
}
int main() {
    int n, p, i;
    int cases = 0, testcase;
    char pattern[105], s[105];
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        scanf("%d %s", &n, pattern);
        insertTrie(pattern, root, 1);
        for(int i = 0; i < 10; i++) {
        	s[0] = i + '0', s[1] = '\0';
        	insertTrie(s, root, 0);
        }
        buildACautomation(root);
        long long ret = dp(root, n);
        freeTrie(root);
        if(n == 1 && strcmp("0", pattern))
        	ret++;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
1 3
2 13
2 1
*/
Read More +
解題區/解題區 - UVa

UVa 12010 - Boring Homework

Problem

Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game “Starcraft II” that she can’t finish her homework in time. She needs your help.

  • A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
    -from Wikipedia

To draw a picture of BST, you may follow the rules listed below:

  • The picture of a 1-node BST, whose size is 1*1, is a single ‘o’ (15th small Latin letter).
  • If a BST has a non-empty subtree, draw a single ‘|’ just above the subtree’s root, and a single ‘+’ just above previous drawn ‘|’. Finally, in the row of ‘+’, use the least number (including 0) of ‘-‘s to connect ‘+’ (denoting the left subtree and right subtree) and ‘o’ (denoting the parent node of the subtree)
  • The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
  • The column of the BST’s root must not contain any character from left subtree or right subtree.
  • Any column containing any characters from BST’s left subtree must not contain any characters from BST’s right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.

The sample output may give a clear clarification about the format of the picture.

Input

The first line contains T ( T$\le$2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.

Output

For each test case:

Output the case number counting from 1 in the first line. The next lines should be the image described above without any trailing spaces. See the sample for more format details.

Note: Notice that no trailing whitespaces after the last visible characters of each line are allowed.

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Case #1:
+-o
|
o+
 |
 o
Case #2:
+--o+
|   |
o-+ o+
  |  |
 +o  o
 |
 o
Case #3:
 +o+
 | |
+o o+
|   |
o   o

Solution

題目描述：

請先依序插入節點，並且建造一棵二分搜尋樹，接著打印出來。

以 o 表示節點，而用 + 表示左右子樹的存在，並且用 - 來移動其位置。盡可能用最少的 - 來完成。並且每一列 (縱向) 只會有一個 o 存在。

題目解法：

根據中序搜索，可以得到由左至右的打印節點順序，根據這個打印順序著手左右的 - 計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <string.h>
struct Node {
    int v, l, r, porder;
};
Node BST[128];
char g[256][128];
int porder = 0, mxdep;
void build(int nd, int dep) {
    if(dep > mxdep)	mxdep = dep;
    if(BST[nd].l != -1)
        build(BST[nd].l, dep+2);
    BST[nd].porder = porder++;	
    if(BST[nd].r != -1)
        build(BST[nd].r, dep+2);
        
    if(BST[nd].l != -1) {
        g[dep][BST[BST[nd].l].porder] = '+';
        g[dep+1][BST[BST[nd].l].porder] = '|';
        for(int i = BST[BST[nd].l].porder + 1; i < BST[nd].porder; i++)
            g[dep][i] = '-';
    }
    g[dep][BST[nd].porder] = 'o';
    if(BST[nd].r != -1) {
        for(int i = BST[BST[nd].r].porder - 1; i > BST[nd].porder; i--)
            g[dep][i] = '-';
        g[dep][BST[BST[nd].r].porder] = '+';
        g[dep+1][BST[BST[nd].r].porder] = '|';
    }
}
int main() {
    int testcase, cases = 0, N;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &N);
        memset(BST, -1, sizeof(BST));
        scanf("%d", &BST[0].v);
        int size = 1, x;
        for(int i = 1; i < N; i++) {
            scanf("%d", &x);
            int idx = 0;
            do {
                if(x < BST[idx].v) {
                    if(BST[idx].l != -1)
                        idx = BST[idx].l;
                    else
                        BST[idx].l = size, BST[size++].v = x, idx = 0;
                } else {
                    if(BST[idx].r != -1)
                        idx = BST[idx].r;
                    else
                        BST[idx].r = size, BST[size++].v = x, idx = 0;
                }
            } while(idx);
        }
        porder = 0, mxdep = 0;
        memset(g, ' ', sizeof(g));
        build(0, 0);
        printf("Case #%d:\n", ++cases);
        for(int i = 0; i <= mxdep; i++) {
            for(int j = N; g[i][j] == ' '; j--)
                g[i][j] = '\0';
            printf("%s\n", g[i]);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11990 - ``Dynamic'' Inversion

Problem

You are given a permutation {1,2,3,…,n}. Remove m of them one by one, and output the number of inversion pairs before each removal. The number of inversion pairs of an array A is the number of ordered pairs (i,j) such that i < j and A[i] > A[j].

Input

The input contains several test cases. The first line of each case contains two integers n and m (1<=n<=200,000, 1<=m<=100,000). After that, n lines follow, representing the initial permutation. Then m lines follow, representing the removed integers, in the order of the removals. No integer will be removed twice. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each removal, output the number of inversion pairs before it.

Sample Input

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

Output for the Sample Input

1
2
3
4
5
2
2
1

Explanation

(1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)

Solution

題目描述：

找尋一維數列的逆序對總數，每一次詢問請輸出當時的逆序對個數，隨後將該數字從數列中移除。

題目解法：

一開始可以利用傳統的 D&C 或者是線段樹之類的區間查詢來完成全部的逆序對總數。

隨後要移除某個特定的數字時，要查找該數字前面有多少比它大的數字，以及後面有多少比它小的數字。也就是說，找尋前綴大於某個數字的個數，和找尋後綴小於某個數字的個數，算出有多少對逆序對減少。

這裡使用類似歸併樹的做法，類似合併排序，將會切分成數個區間做排序。並且在每一個區間中會建立一棵離散化後的 binary indexed tree，如果一來記憶體可以在 O(n log n) 解決。

由於我們只需要前綴和後綴的操作，所以說是線段樹可能還有所不及。

每次將前綴拆分成線段樹的數個區間，利用 binary indexed tree，查找當前有多少小於該數字 x 數字被刪除，得到有多少小於 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 200005
int N, M, DEL;
int ST[20][MAXN], BIT[20][MAXN];
int MP[MAXN];
long long invPair;
void modifySUM(int BIT[], int x, int v, int L) {
    while(x <= L) {
        BIT[x] += v;
        x += x&(-x);
    }
} 
int querySUM(int BIT[], int x) {
    int ret = 0;
    while(x) {
        ret += BIT[x];
        x -= x&(-x); 
    } 
    return ret;
} 
void buildST(int k, int l, int r, int dep) {
    for(int i = l; i <= r; i++)
        ST[dep][i] = ST[dep-1][i], BIT[dep][i] = 0;
    if(l >= r)	return ;
    int m = (l + r)/2;
    buildST(k<<1, l, m, dep+1);
    buildST(k<<1|1, m+1, r, dep+1);
    sort(ST[dep] + l, ST[dep] + r+1);
}
void queryPrefix(int k, int l, int r, int dep, int x, int y, int val) {
    if(x <= l && r <= y) {
        int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
        int pre = querySUM(BIT[dep]+l-1, pos - l);
        invPair -= (r - pos + 1) - (querySUM(BIT[dep]+l-1, r-l + 1) - pre);
        return ;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        queryPrefix(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        queryPrefix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void querySuffix(int k, int l, int r, int dep, int x, int y, int val) {
    if(x <= l && r <= y) {
        int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
        int pre = querySUM(BIT[dep]+l-1, pos - l);
        invPair -= (pos - l) - pre;
        return ;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        querySuffix(k<<1, l, m, dep+1, x, y, val);
    if(y > m)
        querySuffix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void update(int k, int l, int r, int dep, int x, int val) {
    if(l == r) {
        modifySUM(BIT[dep]+l-1, 1, 1, r-l+1);
        return;
    }
    if(l >= r)	return ;
    int m = (l + r)/2;
    if(x <= m)
        update(k<<1, l, m, dep+1, x, val);
    else
        update(k<<1|1, m+1, r, dep+1, x, val);
    int pos = lower_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
    modifySUM(BIT[dep]+l-1, pos - l + 1, 1, r-l+1);
}
int main() {
    while(scanf("%d %d", &N, &M) == 2) {
        invPair = 0;
        for(int i = 1; i <= N; i++)
            BIT[0][i] = 0;
        for(int i = 1; i <= N; i++) {
            scanf("%d", &ST[0][i]);
            MP[ST[0][i]] = i;
            invPair += i - 1 - querySUM(BIT[0], ST[0][i]);
            modifySUM(BIT[0], ST[0][i], 1, N);
        }
        buildST(1, 1, N, 1);
        
        while(M--) {
            scanf("%d", &DEL);
            printf("%lld\n", invPair);
            queryPrefix(1, 1, N, 1, 1, MP[DEL] - 1, DEL);
            querySuffix(1, 1, N, 1, MP[DEL] + 1, N, DEL);
            update(1, 1, N, 1, MP[DEL], DEL);
        }
    }
    return 0;
}
/*
5 4
1
5
3
4
2
5
*/
Read More +
解題區/解題區 - UVa

UVa 11722 - Joining with Friend

Problem

You are going from Dhaka to Chittagong by train and you came to know one of your old friends is going from city Chittagong to Sylhet. You also know that both the trains will have a stoppage at junction Akhaura at almost same time. You wanted to see your friend there. But the system of the country is not that good. The times of reaching to Akhaura for both trains are not fixed. In fact your train can reach in any time within the interval [t1, t2] with equal probability. The other one will reach in any time within the interval [s1, s2] with equal probability. Each of the trains will stop for w minutes after reaching the junction. You can only see your friend, if in some time both of the trains is present in the station. Find the probability that you can see your friend.

Input

The first line of input will denote the number of cases T (T < 500). Each of the following T line will contain 5 integers t1, t2, s1, s2, w (360 ≤ t1 < t2 < 1080, 360 ≤ s1 < s2 < 1080 and 1 ≤ w ≤ 90). All inputs t1, t2, s1, s2 and w are given in minutes and t1, t2, s1, s2 are minutes since midnight 00:00.

Output

For each test case print one line of output in the format “Case #k: p” Here k is the case number and p is the probability of seeing your friend. Up to 1e-6 error in your output will be acceptable.

Sample Input

1
2
3
2
1000 1040 1000 1040 20
720 750 730 760 16

Output for Sample Input

1
2
Case #1: 0.75000000
Case #2: 0.67111111

Solution

題目描述：

有兩位朋友，分別在 [t1, t2] 和 [s1, s2] 之間內可能會抵達，並且在那邊最多停留 w 單位時間。

問兩個人碰面的機率為何。

題目解法：

將兩個人分別至於 X Y 軸，利用幾何面積找到概率。

對於面積 [t1, t2]x[s1, s2] 只要符合 |t - s| <= w 的面積比例。

由於排容上可能不好理解，直接套用凸包交集的算法，兩個凸包交一定也是凸包。

p11722.png

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>
using namespace std;
#define eps 1e-8
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);
    }
};
typedef Pt Vector;
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
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 calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*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);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        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 calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
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;
}
int main() {
    Pt a[64], b[64], ret[64], ch[64];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	int t1, t2, s1, s2, w;
    	int n = 4, m = 4, q;
    	scanf("%d %d %d %d %d", &t1, &t2, &s1, &s2, &w);
    	a[0] = Pt(t1, s1), a[1] = Pt(t2, s1);
    	a[2] = Pt(t2, s2), a[3] = Pt(t1, s2);
    	b[0] = Pt(0, w), b[1] = Pt(0, -w);
    	b[2] = Pt(t2, t2-w), b[3] = Pt(t2, t2+w);
        Seg seg1, seg2;
        int retN = 0;
        for(int i = 0, j = n-1; i < n; j = i++) {
            seg1.s = a[i], seg1.e = a[j];
            for(int p = 0, q = m-1; p < m; q = p++) {
                seg2.s = b[p], seg2.e = b[q];
                if(calcIntersection(seg1, seg2, ret[retN])) {
                    retN++;
                    /*printf("%lf %lf - %lf %lf\n", s1.s.x, s1.s.y, s1.e.x, s1.e.y);
                    printf("%lf %lf - %lf %lf +++\n", s2.s.x, s2.s.y, s2.e.x, s2.e.y);*/
                }
            }
        }
        for(int i = 0; i < n; i++)
            if(inPolygon(b, m, a[i]))
                ret[retN++] = a[i];
        for(int i = 0; i < m; i++)
            if(inPolygon(a, n, b[i]))
                ret[retN++] = b[i];
        q = monotone(retN, ret, ch);
        double area = calcArea(ch, q);
        printf("Case #%d: %.8lf\n", ++cases, area / ((t2 - t1) * (s2 - s1)));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11266 - Equations

Problem

Find the number of solutions, the equation ∑Xi = s have, if Ai≤Xi≤Bi for each i = 1…n.

For example,

X1 + X2 + X3 = 10

-1 ≤ X1 ≤ 3

2 ≤ X2 ≤ 4

6 ≤ X3 ≤ 7

The above set of equations has 6 solutions. They are: {1,4,7}, {0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.

You are given n the number of variables and the range of them. Your task is to calculate the number of solutions of that equation.

Input

First line of the Input contains T (≤50) the number of test cases. Then T test cases follow. First line of each test case contains 2 integer n (1≤n≤10) and s (-50000 ≤ s ≤ 50000). Next n lines each contain 2 integers describing the range of each variable. The ith line Ai and Bi (10000 ≤ Ai ≤ Bi ≤10000). Xi can take any integral value in the range [Ai, Bi].

Output:

For each test case output contains one integer denoting the number of solutions of the given equations. Output the value modulo 200003.

Sample Input

1
2
3
4
5
1
3 10
-1 3
2 4
6 7

Sample Output

1
6

Solution

題目描述：

對於每一個變數範圍，找到符合等式的解個數。

題目解法：

直接著手動態規劃，對於 dp[i][j] 定義為使用前 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int shift = 100000;
int dp[2][200005];
int main() {
    int testcase, n, s;
    int A[16], B[16];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &s);
        for(int i = 0; i < n; i++)
            scanf("%d %d", &A[i], &B[i]);
            
        memset(dp, 0, sizeof(dp));
        for(int i = A[0]; i <= B[0]; i++)
            dp[0][i + shift] = 1;
        int f = 1;
        for(int i = 1; i < n; i++) {
            memset(dp[f], 0, sizeof(dp[f]));
            int l = -B[i], r = -A[i], sum = 0;
            for(int j = 0 - B[i]; j <= 0 - A[i]; j++) {
                if(j < 0 || j >= 200005)
                    continue;
                sum += dp[!f][j];
                sum %= 200003;
            }
            for(int j = 0; j < 200005; j++) {
                dp[f][j] = sum;
                if(l >= 0 && l < 200005)
                    sum -= dp[!f][l];
                if(r + 1 >= 0 && r + 1 < 200005)
                    sum += dp[!f][r+1];
//				if(sum)
//					printf("%d %d %d\n", i, j - shift, sum);
                sum %= 200003;
                l++, r++;
            }
            f = !f;
        }
        printf("%d\n", (dp[!f][s + shift] + 200003)%200003);
    }
    return 0;
}
Read More +