解題區/解題區 - UVa

UVa 12809 - Binary Search Tree

Problem

類似 UVa 10304 - Optimal Binary Search Tree，給每個節點的拜訪頻率，建造一個二元樹，使得詢問次數最小化。

Sample Input

1
2
3
4
5
6
3
0.33 0.34 0.33
3
0.8 0.15 0.05
4
0.23 0.4 0.17 0.2

Sample Output

1
2
3
1.6600
1.2500
1.7700

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
#include <stdio.h> 
#include <string.h> 
double f[128];
double sum[128], w[128][128];
double dp[128][128];
int arg[128][128];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%lf", &f[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + f[i];
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                w[i][j] = sum[j] - sum[i - 1];
        for (int i = 0; i <= n; i++)
            dp[i][i] = 0, arg[i][i] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; i + j <= n; j++) {
                double mn = 1e+30;
                int idx = -1;
                for (int k = arg[j][i+j-1]; k <= arg[j+1][i+j]; k++) {
                    double t = dp[j][k-1] + dp[k+1][i+j] + w[j][k-1] + w[k+1][i+j];
                    if (t < mn)
                        mn = t, idx = k;
                }
                dp[j][i+j] = mn, arg[j][i+j] = idx;
            }
        }
        printf("%lf\n", dp[1][n] + 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12786 - Friendship Networks

Problem

類似 UVa 10720 - Graph Construction，給一個無向圖的每一個節點 degree，請問是否能構成圖。

Sample Input

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

Sample Output

1
2
3
1
0
1

Solution

使用公式加二分。

Erdős–Gallai theorem

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
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int n, i, k;
long long sum[1005], d[1005];
int main() {
    while(scanf("%d", &n) == 1 && n) {
        sum[0] = 0;
        for(i = 0; i < n; i++)
            scanf("%lld", &d[i]);
        sort(d, d+n, greater<int>());
        for(i = 0; i < n; i++)
            sum[i+1] = sum[i] + d[i];
        long long left = 0, right;
        int ret = 1;
        if(sum[n]&1)    ret = 0;
        for(k = 0; k < n; k++) {
            left += d[k];
            right = (long long)k * (k+1);
            int l =  lower_bound(d , d + n, k+1, greater<int>()) - d;
            if(l < k+1)
                right += sum[n] - sum[k+1];
            else
                right += sum[n] - sum[l] + (long long)(k+1)*(l - k - 1);
            if(left > right)	ret = 0;
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12776 - Query for Divisor-free Numbers

Problem

給一個序列 A，請問在 A[l:r] 中 A[i] 不被 A[j] 整除的個數為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3

Sample Output

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

Solution

首先先貪心 A[i]，找到左側最鄰近的因數、右側最鄰近的因數的位置找出 L[i], R[i]。

以下使用 binary indexed tree 進行區域操作。

然後對於詢問 [l, r] 事先讀進來，加入掃描線算法，確保能夠詢問 [l, r] 時，找尋 BIT[r] 的值為何。

掃描時，當我們遇到某個因數所展開的區間 [L[i], R[i]] 的左端點

  • 對於 BIT[i, R[i]] 範圍元素都加上 1，而在遇到區間對應的 A[i] 位置進行移除區間 (不用等到右端點，必須在中間就移除掉，確保查詢的時 A[i] 還在裡面)，BIT[i, R[i]] 範圍元素都減去 1。
  • 對於遇到詢問 [l, r] 的左端點時，詢問 BIT[r] 的值為何。

因此資料結構要維護

  • 將一個區間內的元素都加上 k
  • 詢問某個元素值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
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[32767], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    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;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    int on = n;
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v, vector<int> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    int a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
int A[131072], L[131072], R[131072];
vector<int> Af[131072], RM[131072];
vector< pair<int, int> > Q[131072], QL[131072];
int OUT[131072];
int BIT[131072];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += (x)&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= (x)&(-x);
    }
    return ret;
}
int main() {
//		freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    sieve();
    int testcase, cases = 0;
    int n, m, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            vector< pair<int, int> > f = factor(A[i]);
            Af[i].clear();
            make(0, A[i], 1, f, Af[i]);
        }
        for (int i = 0; i < n + 20; i++)
            Q[i].clear(), QL[i].clear(), RM[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            Q[x].push_back(make_pair(y, i));
        }
        map<int, int> mp;
        map<int, int>::iterator mpit;
        for (int i = 1; i <= n; i++) {
            x = 0;
            for (int j = 0; j < Af[i].size(); j++)
                x = max(x, mp[Af[i][j]]);
            mp[A[i]] = i;
            L[i] = x + 1;
        }
        mp.clear();
        for (int i = n; i >= 1; i--) {
            x = n + 1;
            for (int j = 0; j < Af[i].size(); j++) {
                mpit = mp.find(Af[i][j]);
                if (mpit != mp.end())
                    x = min(x, mpit->second);
            }
            mp[A[i]] = i;
            R[i] = x - 1;
        }
        for (int i = 1; i <= n; i++) {
            QL[L[i]].push_back(make_pair(R[i], i));
            RM[i].push_back(R[i]);
        }
        for (int i = 1; i <= n + 20; i++)
            BIT[i] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < QL[i].size(); j++) {
                modify(QL[i][j].second, 1, n + 20);
                modify(QL[i][j].first + 1, -1, n + 20);
//				printf("add [%d %d]\n", QL[i][j].second, QL[i][j].first);
            }
            if (i)
            for (int j = 0; j < RM[i-1].size(); j++) {
                modify(i-1, -1, n + 20);
                modify(RM[i-1][j] + 1, 1, n + 20);
//				printf("rm [%d %d]\n", i-1, RM[i][j]);
            }
            for (int j = 0; j < Q[i].size(); j++) {
                int v = query(Q[i][j].first);
                OUT[Q[i][j].second] = v;
//				printf("%d %d - %d\n", Q[i][j].first, Q[i][j].second, v);
            }
//			puts("--");
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < m; i++)
            printf("%d\n", OUT[i]);
    }
    return 0;
}
/*
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3
*/
Read More +
解題區/解題區 - UVa

UVa 12775 - Gift Dilemma

Problem

找到 Ax + By + Cz = P, 給定 A, B, C, P，要求 (x, y, z) 有幾組解，並且 x >= 0, y >= 0, z >= 0。

Sample Input

1
2
1
202 203 200 606

Sample Output

1
Case 1: 2

Solution

看一下數據範圍 0 < A, B, C, P <= 100000000，C / gcd(A, B, C) >= 200，後者是強而有力的條件，肯定 z 情況最多 100000000/200 = 500000 個可能，窮舉 z 的情況，用擴充歐基里德找到 Ax + By = (P - Cz) 的解個數。

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
#include <stdio.h> 
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
long long countSolution(long long n1, long long n2, long long n) {
    long long a, b, g;
    g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
    if(n%g) return 0;
    long long k = n/g, k1, k2;
    a *= k, b *= k;// a*n1 + b*n2 = n
    // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0,
    //F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
    k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
    if(a < 0) { // adjust a >= 0
        k = -(a/k1) + (a%k1 != 0);
        a += k*k1, b -= k*k2;
    }
    if(b < 0) { // adjust b >= 0
        k = -(b/k2) + (b%k2 != 0);
        a -= k*k1, b += k*k2;
    }
    if(a < 0 || b < 0) return 0;
    long long x1, x2, y1, y2;
    // minimize a, maximize b
    k = a/k1;
    a -= k*k1;
    b += k*k2;
    x1 = a, y1 = b;
    // maximize a, minimize b
    k = b/k2;
    a += k*k1;
    b -= k*k2;
    x2 = a, y2 = b;
    return (x2 - x1) / k1 + 1;
}
int main() {
    int testcase, cases = 0;
    long long A, B, C, P, ret, ta, tb;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld %lld %lld", &A, &B, &C, &P);
        long long g = exgcd(exgcd(A, B, ta, tb), C, ta, tb);
        P /= g, A /= g, B /= g, C /= g;
        ret = 0;
        for (long long i = 0; P - C * i >= 0; i++)
            ret += countSolution(A, B, P - C * i);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1
202 203 200 606
*/
Read More +
解題區/解題區 - UVa

UVa 12607 - Amazing Maze

Problem

在一個迷宮中有 M x N 個房間，每個房間有四個門，並且以逆時針的順序依次出現，每一個時間每個房間只會有一個門通往另一個地方。

必須從左上角開始，花最少時間收集到 K 個寶物後抵達右下角。

Sample Input

1
2
3
4
5
6
2 2
EE
NN
1
1 2
0 0

Sample Output

1
2

Solution

分析狀態，由於 K 不大，直接 2^K 狀態下去，而只會有四個門，因此時間論替只需要考慮 mod 4 的結果，最後 dist[x][y][4][1<<8] 抵達 (x, y) 時的門狀態、同時身上帶了多少寶物 (用 bitmask 去壓縮)。

BFS 一下就過去，記得要注意可以在同一個房間內等待下一個時刻。

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
#include <stdio.h> 
#include <algorithm>
#include <queue>
#include <assert.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0}; // N E S W 
const int dy[] = {0, 1, 0, -1};
int used[100][100][4][1<<8] = {}, testcase = 0;
int dist[100][100][4][1<<8] = {};
int main() {
    int N, M, K, x, y;
    char g[128][128];
    while (scanf("%d %d", &N, &M) == 2 && N+M) {
        int treasure[128][128] = {}, dirg[128][128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%s", g[i]);
            for (int j = 0; j < M; j++) {
                if (g[i][j] == 'N')
                    dirg[i][j] = 0;			
                if (g[i][j] == 'E')
                    dirg[i][j] = 1;	
                if (g[i][j] == 'S')
                    dirg[i][j] = 2;	
                if (g[i][j] == 'W')
                    dirg[i][j] = 3;
            }
        }
        scanf("%d", &K);
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            assert(treasure[x][y] == 0);
            treasure[x][y] = i + 1;
        }
        queue<int> X, Y, D, T;
        int x = 0, y = 0, d = 0, t = 0;
        int tx, ty, td, tt;
        if (treasure[x][y])
            t |= 1<<(treasure[x][y] - 1);
        X.push(x), Y.push(y), D.push(d), T.push(t);
        testcase++;
        used[x][y][d][t] = testcase;
        dist[x][y][d][t] = 0;
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            d = D.front(), D.pop();
            t = T.front(), T.pop();	
                    
            tx = x, ty = y, td = (d + 1)%4, tt = t;
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
            
            int dir = (dirg[x][y] + d)%4;
            tx = x + dx[dir], ty = y + dy[dir], td = (d + 1)%4, tt = t;
            if (tx < 0 || ty < 0 || tx >= N || ty >= M)
                continue;
            if (treasure[tx][ty])
                tt |= 1<<(treasure[tx][ty] - 1);
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
        }
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < 4; i++) {
            if (used[N-1][M-1][i][(1<<K)-1] == testcase)
                ret = min(ret, dist[N-1][M-1][i][(1<<K)-1]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 2
EE
NN
1
1 2
1 1
E
1
1 1
1 2
NE
1
1 2
0 0
*/
Read More +
解題區/出題解題

[ACM 題目] 最近餐館

Problem

每到吃飼料時間，某 M 正思考要去哪裡解決，雖然有很多很多地方可以去吃，由於某 M 對於美食沒有特別需求，所以只會到最近的幾個地點即可，然後再以循環輪食的方式日復一日。

某 M 現在的位置與每個餐館的位置都用一個笛卡爾坐標系中的點表示，每個點與每個點的距離為歐幾里得距離。

x = (x1,…,xn) 和 y = (y1,…,yn) 之間的距離為

test

現給出在 K 維空間中某 M 所處的位置座標，以及 N 個餐館位置，請觀察某 M 會到哪裡吃飼料。.

Input

輸入有多組測資，

每一組第一行會有兩個整數 N, K，

接下來會有 N 行，每行包含 K 個整數，表示第 i 個餐館座標。

接下來一行，包含一個整數 Q，表示某 M 的可能座標 。

接下來會有 Q 行，每一組詢問會有兩行，第一行會有 K 個整數，表示某 M 所在的座標，第二行會有一個整數 P。

(N < 8192, K < 6, Q < 10,000, P < 11, 座標值 0 < x, y < 10,000)

Output

對於每一組詢問，輸出一行 Case #:，第一個整數為 P，接下來 P 個整數按照距離由小到大輸出餐館編號，如果相同則輸出編號小的。

Sample Input

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

Sample Output

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8192
#define MAXD 8
#define INF 0x3f3f3f3f
class kdTree {
    public:	
    struct PointD {
        int d[MAXD];
        int label;
    };
    struct Node {
    	Node *lson, *rson;
    	int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
    		return x->d[sortDidx] < y->d[sortDidx];
        }
    };
    struct pQcmp {
        bool operator() (pair<int, int> &a, pair<int, int> &b) const {
        	if (a.first != b.first)	return a.first < b.first;
        	return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<int, int>, vector< pair<int, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K;
    int Q[MAXD], max_dist, qM;
    void prepare(int n) {
        bufsize = 0;
        for (int i = 0; i < n; i++)
        	A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    int dist(int idx) {
        int ret = 0;
        for(int i = 0; i < K; i++)
            ret += (pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    int h_func(int h[]) {
        int ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, int h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        int d = dist(u->label);
        if (d < max_dist) {
            pQ.push(make_pair(d, u->label));
            if (pQ.size() == qM + 1) {
                max_dist = pQ.top().first, pQ.pop();
            }
        }
        int old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
        }
    }
    void query(int p[], int M) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        int h[MAXD] = {};
        findNearest(root, 0, h);
        printf("%d", M);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = ret.size() - 1; i >= 0; i--)
        	printf(" %d", ret[i] + 1);
        puts("");
    }
};	
int kdTree::sortDidx;
kdTree tree;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, q, p[MAXD], x;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
    	tree.K = m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			scanf("%d", &tree.pt[i].d[j]);
    		tree.pt[i].label = i;
    	}
    	tree.prepare(n);
        scanf("%d", &q);
        while (q--) {
        	for (int i = 0; i < m; i++)
        		scanf("%d", &p[i]);
        	scanf("%d", &x);
        	printf("Case %d: ", ++cases);
        	tree.query(p, x);
        }
    }
    return 0;
}
/*
2 2
1 1
3 3
1
2 2
1
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
*/
Read More +
解題區/解題區 - UVa

UVa 12524 - Arranging Heaps

Problem

現在有 n 個堆，位於位置 xi 的堆重量 wi，對於每一堆可以移動到位置大的地方，移動的成本為(xj - xi) * wi，請問集中 k 堆的最少花費為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output

1
2
3
4
30
8
278
86

Solution

參考 work_freedom的专栏

dp[i][j] : 表示放入 i 堆，集中 j 堆的最少花費

1
2
3
4
dp[i][j] = dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k])
dp[k][j-1] + sumXW[k] = X[i] * sumW[k] + dp[i][j] + sumXW[i] - sumW[i] * X[i]
^^^^^^^^^^^^^^^^^^^^^   ^^^^   ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
y = a x + b, a : monotone increasing, maintain upper convex

將公式調整為上述結果，會發現我們依序帶入的 X[i] 遞增，也就是斜率會越來越高，要使後半部常數越大越好，保證此線會相交於凸包的頂點上。

凸包點 (sumW[k], dp[k][j-1] + sumXW[k])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 1024
long long dp[MAXN][MAXN], X[MAXN], W[MAXN];
long long sumW[MAXN] = {}, sumXW[MAXN] = {};
struct SlopeDP {
    int front, rear;
    long long X[MAXN], Y[MAXN];
    void init() {front = 0, rear = -1;}
    long long cross(long long x1, long long y1, long long x2, long long y2) {
        return x1 * y2 - y1 * x2;
    }
    int add(long long x, long long y) {
        while (front < rear && cross(X[rear]-X[rear-1], Y[rear]-Y[rear-1], x-X[rear-1], y-Y[rear-1]) < 0)
            rear--;
        rear++;
        X[rear] = x, Y[rear] = y;
    }
    long long get(long long m) {
        while (front < rear && Y[front+1]-Y[front] < (X[front+1]-X[front]) * m)
            front++;
        return Y[front] - m * X[front];
    }
} dpTool;
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%lld %lld", &X[i], &W[i]);
        for (int i = 1; i <= N; i++) {
            sumW[i] = sumW[i-1] + W[i];
            sumXW[i] = sumXW[i-1] + X[i] * W[i];
        }
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= M; j++) 
                dp[i][j] = 1LL<<60;
        dp[0][0] = 0;
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= M; j++) {
//				for (int k = 0; k < i; k++)
//					dp[i][j] = min(dp[i][j], dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k]));
//			}
//		}
        for (int i = 1; i <= M; i++) {
            dpTool.init();
            for (int j = i; j <= N; j++) {
                dpTool.add(sumW[j-1], dp[j-1][i-1] + sumXW[j-1]);
                long long val = dpTool.get(X[j]);
                dp[j][i] = val - (sumXW[j] - sumW[j] * X[j]);
            }
        }
        printf("%lld\n", dp[N][M]);
    }
    return 0;
}
/*
dp[i][j] = dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k])
dp[k][j-1] + sumXW[k] = X[i] * sumW[k] + dp[i][j] + sumXW[i] - sumW[i] * X[i]
^^^^^^^^^^^^^^^^^^^^^   ^^^^   ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
y = a x + b, a : monotone increasing, maintain upper convex
*/
/*
3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1
*/
Read More +
解題區/解題區 - UVa

UVa 12141 - Line Chart

Problem

給 n 個點趨勢圖，可以選擇忽略某些點，忽略的點會被剩餘點補上靠左。

請問要恰好 k 個 peak 的情況，有多少不同的趨勢圖貌。這別要求兩個相鄰的點不可以有相同 y 值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3

Sample Output

1
2
3
Case 1: 20
Case 2: 1
Case 3: 8

Solution

TLE 版本，答案是正確的。 O(n^2 m)

其實這有點接近貪心作法，狀態為 dp[i][k][3] 表示加入第 i 個點，產生 k 個 peak，並且下一次要接 y 值較高、較低、等於的點。

而考慮當前 k 個 peak y[i]，對於三種高地要求，我們只會轉移到不同的 y 值，也就是對於後面如果存有 y[p] = y[q], p < q，盡可能選擇 p 小的，否則會重複計算，要忽略 q 大的。

從下面樸素算法中，可以獲得基礎的遞迴公式。

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>
#include <map>
using namespace std;
int dp[10005][64][3] = {};
const int mod = 1000000;
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int v = 0;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = v++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(dp, 0, sizeof(dp));
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                dp[i][0][0] = 1; // =
                dp[i][0][1] = 1; // <
                dp[i][0][2] = 1; // > next time
                used[D[i].second] = 1;
            }
        }
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            ret = (ret + dp[i][m][0])%mod;
            memset(used, 0, sizeof(used));
//			for (int k = 0; k <= m; k++) 
//					printf("[%d %d] %d %d %d\n", i, k, dp[i][k][0], dp[i][k][1], dp[i][k][2]);
            for (int j = i+1; j < n; j++) {					
                if (used[D[j].second])	continue;
                used[D[j].second] = 1;
                for (int k = 0; k <= m; k++) {
                    if (D[j].second > D[i].second) { // larger
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][2])%mod;
                        dp[j][k+1][1] = (dp[j][k+1][1] + dp[i][k][2])%mod;
                        dp[j][k][2] = (dp[j][k][2] + dp[i][k][2])%mod;
                    } else if (D[j].second == D[i].second) {
//						dp[j][k][0] = (dp[j][k][0] + dp[i][k][0])%mod;
//						dp[j][k][1] = (dp[j][k][1] + dp[i][k][0])%mod;
//						dp[j][k][2] = (dp[j][k][2] + dp[i][k][0])%mod;
                    } else {
                        dp[j][k][0] = (dp[j][k][0] + dp[i][k][1])%mod;
                        dp[j][k][1] = (dp[j][k][1] + dp[i][k][1])%mod;
                        dp[j][k+1][2] = (dp[j][k+1][2] + dp[i][k][1])%mod;
                    }
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}

使用 binary indexed tree 優化 O(nm log n)

使用前綴總和來完成狀態轉移。為了防止相同 y[p] = y[q], p < q，由於會先拜訪到 p 進行狀態轉移，特別考慮 y[q] 基底的轉移狀態必須被扣除 y[p] 的結果。

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
#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
#include <assert.h>
using namespace std;
#define MAXN 10050
int dp[MAXN][64][3] = {};
int UBIT[64][3][MAXN], DBIT[64][3][MAXN];
int shift[64][3][MAXN] = {};
const int mod = 1000000;
int query(int A[], int idx) {
    int sum = 0;
    while (idx)
        sum = (sum + A[idx])%mod, idx -= idx&(-idx);
    return sum;
}
void modify(int A[], int idx, int val, int L) {
    while (idx <= L)
        A[idx] = (A[idx] + val)%mod, idx += idx&(-idx);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout);
    int testcase, n, m, x, y;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        vector< pair<int, int> > D;
        map<int, int> R;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            R[y] = 0;
            D.push_back(make_pair(x, y));
        }
        sort(D.begin(), D.end());
        int L = 1;
        for (map<int, int>::iterator it = R.begin();
            it != R.end(); it++)
            it->second = L++;
        for (int i = 0; i < n; i++)
            D[i].second = R[D[i].second];
        memset(UBIT, 0, sizeof(UBIT));
        memset(DBIT, 0, sizeof(DBIT));
        memset(shift, 0, sizeof(shift));		
        int used[10005] = {};
        for (int i = 0; i < n; i++) {
            if (used[D[i].second] == 0) {
                shift[0][0][D[i].second] = -1; // =
                used[D[i].second] = 1;
            }
        }
        modify(UBIT[0][1], 1, 1, L);
        modify(UBIT[0][2], 1, 1, L);
        int ret = 0;
        if (m == 0)
            ret++;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= m; k++) {
                int dp0 = query(UBIT[k][0], D[i].second) + query(DBIT[k][0], L - D[i].second-1) - shift[k][0][D[i].second];
                int dp1 = query(UBIT[k][1], D[i].second) + query(DBIT[k][1], L - D[i].second-1) - shift[k][1][D[i].second];
                int dp2 = query(UBIT[k][2], D[i].second) + query(DBIT[k][2], L - D[i].second-1) - shift[k][2][D[i].second];
//				printf("[%d %d] %d %d %d\n", i, k, dp0, dp1, dp2);
                dp0 %= mod, dp1 %= mod, dp2 %= mod;
                shift[k][0][D[i].second] += dp0;
                shift[k][1][D[i].second] += dp1;
                shift[k][2][D[i].second] += dp2;
                if (k == m)		ret = (ret + dp0)%mod;
                if (dp2) {
                    modify(UBIT[k][0], D[i].second+1, dp2, L);
                    modify(UBIT[k+1][1], D[i].second+1, dp2, L);
                    modify(UBIT[k][2], D[i].second+1, dp2, L);
                }
                if (dp1) {
                    modify(DBIT[k][0], L - D[i].second, dp1, L);
                    modify(DBIT[k][1], L - D[i].second, dp1, L);
                    modify(DBIT[k+1][2], L - D[i].second, dp1, L);
                }
            }
        }
        printf("Case %d: %d\n", ++cases, (ret + mod)%mod);
    }
    return 0;
}
/*
3
3 0
1 1
2 1
3 1
3 1
101 3
102 2
104 4
3
6 1
320 3
306 1
401 3
325 4
393 5
380 2
4 1
101 3
102 2
103 2
104 4
3 0
102 2
101 1
103 3
*/
Read More +
解題區/解題區 - UVa

UVa 11910 - Closest Fractions

Problem

對於每一個浮點數，找到一個最靠近的分數，分子分母限制在 [1, 1000] 的整數。

Sample Input

1
2
3
3.141592654
66.66666666
333.3333333

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
Input : 3.141592654
    1 : 3.141592920 =  355 / 113
    2 : 3.141630901 =  732 / 233
    3 : 3.141552511 =  688 / 219
Input : 66.66666666
    1 : 66.66666667 =  200 / 3
    2 : 66.64285714 =  933 / 14
    3 : 66.69230769 =  867 / 13
Input : 333.3333333
    1 : 333.3333333 = 1000 / 3
    2 : 333.5000000 =  667 / 2
    3 : 333.0000000 =  333 / 1

Solution

預先將所有分數建表，然後每一次二分搜索。

最麻煩在於輸出要保證長度 10 位，細讀 printf() 後，發現頂多限制小數點後的位數、小數點前的位數，如果要同時限制還是要自己來。

最後使用 %*.*f，* 號部分要自己帶入參數。如果用 substring 會造成四捨五入的地方消失而拿到 WA。

原本想不建表，直接用鄰近搜索，誤差害死人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
class Frac {
    public:
    int x, y;
    Frac(int a = 0, int b = 0):
        x(a), y(b) {}
    double toDouble() const {
        return (double) x/y;
    }
    bool operator<(const Frac &a) const {
        return toDouble() < a.toDouble();
    }
} D[1048576];
double DD[1048576];
double cmpv;
bool cmp(Frac a, Frac b) {
    return fabs(a.toDouble() - cmpv) < fabs(b.toDouble() - cmpv);
}
int f(double v) {
    if (v >= 1000)	return 4;
    if (v >= 100)	return 3;
    if (v >= 10)	return 2;
    return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n = 0;
    for (int y = 1; y <= 1000; y++) {
        for (int x = 1; x <= 1000; x++) {
            if (__gcd(x, y) == 1)
                D[n++] = Frac(x, y);
        }
    }
    sort(D, D + n);
    for (int i = 0; i < n; i++)
        DD[i] = D[i].toDouble();
    char s[32];
    double v;
    while (scanf("%s", s) == 1) {
        printf("Input : %s\n", s);
        sscanf(s, "%lf", &v);
        int pos = lower_bound(DD, DD + n, v) - DD;
        vector<Frac> A;
        for (int i = max(0, pos - 6); i < min(n, pos + 6); i++)
            A.push_back(D[i]);
        cmpv = v;
        sort(A.begin(), A.end(), cmp);
        for (int i = 0, j = 1; i < 3 && i < A.size(); i++, j++)
            printf("    %d : %*.*lf = %4d / %d\n", j, f(A[i].toDouble()), 10 - f(A[i].toDouble()), A[i].toDouble(), A[i].x, A[i].y);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11768 - Lattice Point or Not

Problem

給一個浮點數一位的線段，請問中間經過多少個整數點。

Sample Input

1
2
3
4
3
10.1 10.1 11.2 11.2
10.2 100.3 300.3 11.1
1.0 1.0 2.0 2.0

Sample Output

1
2
3
1
0
2

Solution

找到原本線段 ax + by = c 的線，為了使其落在整數座標上調整為 10a x + 10b y = c，在這個情況下找到符合的 (x, y) 整數解，但是其結果要被限制上線段上。

努力地做細部微調 …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
long long gcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y; 
    return y;
}
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
long long countSolution(long long n1, long long n2, long long n, 
					long long lx, long long rx, long long ly, long long ry) {
//	printf("%lld %lld %lld\n", n1, n2, n);
    if (lx > rx || ly > ry)	return 0;
    if (n1 == 0)	return rx - lx + 1;
    if (n2 == 0)	return ry - ly + 1;
    long long a, b, g;
    g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
    if(n%g) return 0;
    long long k = n/g, k1, k2;
    a *= k, b *= k;// a*n1 + b*n2 = n
    // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0, F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
    k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
    long long x1, x2, x3, x4, y1, y2, y3, y4;
    k = (a - lx)/k1;
    a -= k*k1, b += k*k2;
    while (a < lx) {
    	if (k1 < 0)	a -= k1, b += k2;
    	else		a += k1, b -= k2;
    }
    x1 = a, y1 = b;
    
    k = (b - ly)/k2;
    a += k*k1, b -= k*k2;  
    while (b < ly) {
    	if (k2 < 0)	a += k1, b -= k2;
    	else		a -= k1, b += k2;
    }
    x3 = a, y3 = b;  
    
    k = (a - rx)/k1;
    a -= k*k1, b += k*k2;
    while (a > rx) {
    	if (k1 < 0)	a += k1, b -= k2;
    	else		a -= k1, b += k2;
    }
    x2 = a, y2 = b;
    
    k = (b - ry)/k2;
    a += k*k1, b -= k*k2;
    while (b > ry) {
    	if (k2 < 0)	a -= k1, b += k2;
    	else		a += k1, b -= k2;
    }
    x4 = a, y4 = b;
    long long l1 = 0, r1 = (x2 - x1)/ k1;
    long long l2 = (x3 - x1)/k1, r2 = (x4 - x1)/k1;
    if (l2 > r2)	swap(l2, r2);
    if (x1 > x2 || y3 > y4)	return 0;
//    printf("%lld %lld %lld %lld\n", x1, y1, x2, y2);
//    printf("%lld %lld %lld %lld\n", x3, y3, x4, y4);
//    printf("%lld %lld %lld %lld\n", l1, r1, l2, r2);
    l1 = max(l1, l2), r1 = min(r1, r2);
    if (l1 <= r1)	return r1 - l1 + 1;
    return 0;
}
long long read1Float() {
    long long x, y;
    scanf("%lld.%lld", &x, &y);
    return x * 10 + y;
}
int main() {    
//	freopen("in.txt","r+t",stdin);
//  freopen("out2.txt","w+t",stdout);
    int testcase, cases = 0;
    long long sx, sy, ex, ey;
    scanf("%d", &testcase);
    while (testcase--) {
        sx = read1Float();
        sy = read1Float();
        ex = read1Float();
        ey = read1Float();
        long long minx, miny, maxx, maxy;
        minx = ceil(min(sx, ex)/10.0);
        maxx = floor(max(sx, ex)/10.0);
        miny = ceil(min(sy, ey)/10.0);
        maxy = floor(max(sy, ey)/10.0);
        long long a, b, c;
        a = (ey - sy), b = (sx - ex), c = (a * sx + b * sy);
        a = a * 10, b = b * 10;
//		printf("[%lld %lld] [%lld %lld]\n", minx, maxx, miny, maxy);
        printf("%lld\n", countSolution(a, b, c, minx, maxx, miny, maxy));
    }
    return 0;
}
/*
5
10.1 10.1 11.2 11.2
10.2 100.3 300.3 11.1
1.0 1.0 2.0 2.0
1.0 1.0 1.0 1.0
1.0 3.0 1.0 7.0
100
74779.7 170072.4 114261.9 224.6
12284.7 149345.2 89292.2 24355.6
119238.0 59748.9 153776.5 88822.9
146984.2 79235.1 116519.4 144150.1
75703.5 8776.5 147012.5 132491.5
93698.8 27585.7 137374.4 134649.2
100
142566.2 47373.1 4487.9 81130.6
122932.1 117873.7 7944.5 24862.7
164852.3 50346.6 58670.9 47341.7
140828.3 21325.9 141292.5 16763.8
144206.3 130562.5 96260.1 53203.7
100
175593.7 137910.8 151744.6 21975.7
66918.0 141841.9 170688.8 108941.3
110334.9 103217.3 145166.0 126201.0
40233.7 62521.1 116634.3 146758.8
187820.7 131930.2 69771.4 66737.3
*/
Read More +