解題區/解題區 - UVa

UVa 12812 - The Largest Diamond-Shaped Kite

Problem

找一個最大箏形於給定的地圖中。

Sample Input

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

Sample Output

1
2
3
5

Solution

其實很像找一個最大正方形，可以參考 NPSC 營地的作法。而要求箏形事實上就是將地圖翻轉 45 度角。

參考 UVa 10593 - Kites 的做法可以完成。

以前寫的 代碼 真是萌哒。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
char g[512][512];
int dp[512][512];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%s", g[i]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '#') {
                    int v1, v2, v3;
                    v1 = i-1 >= 0 && j-1 >= 0 ? dp[i-1][j-1] : 0;
                    v2 = i-2 >= 0 ? dp[i-2][j] : 0;
                    v3 = i-1 >= 0 && j+1 < m ? dp[i-1][j+1] : 0;
                    if (i-1 >= 0 && g[i-1][j] == '#')
                        dp[i][j] = min(v1, min(v2, v3)) + 1;
                    else
                        dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        printf("%d\n", ret * 2 - 1 < 0 ? 0 : ret * 2 - 1);
    }
    return 0;
}
/*
 2
 3 3
 .#.
 ###
 .#.
 8 10
 ..##...#..
 .###..###.
 ..#.......
 ....##....
 ....######
 ...#####..
 ..########
 .....#....
 */
Read More +
解題區/解題區 - UVa

UVa 12811 - The Turtle's Journey

Problem

  • left X
  • right X
  • forward X
  • repeat N [ INST ]

上述總共有四種指令架構，分別輸出前三個指令的 X 總和值。其中第四個為迴圈架構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end
begin
forward 10
left 90
forward 10
left 90
forward 10
left 90
forward 10
left 90
end

Sample Output

1
2
360 0 40
360 0 40

Solution

由於輸入沒有迴圈，差點忘了有 repeat 指令。遞迴讀進輸入即可。

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>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
const long long mod = 1000003;
char s[128];
void dfs(long long cmd[]) {
    scanf("%s", s);
    if (s[0] == 'e' || s[0] == ']')    return;
    long long x, ncmd[3] = {};
    scanf("%lld", &x);
    if (s[0] == 'l')
        cmd[0] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'i')
        cmd[1] += x, dfs(ncmd);
    else if (s[0] == 'f')
        cmd[2] += x, dfs(ncmd);
    else if (s[0] == 'r' && s[1] == 'e'){
        scanf("%*s");
        dfs(cmd);
        for (int i = 0; i < 3; i++)
            cmd[i] = (cmd[i] * x) %mod;
        dfs(ncmd);
    }
    for (int i = 0; i < 3; i++)
        cmd[i] = (cmd[i] + ncmd[i]) %mod;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%*s");
        long long cmd[3] = {};
        dfs(cmd);
        printf("%lld %lld %lld\n", cmd[0], cmd[1], cmd[2]);
    }
    return 0;
}
/*
 2
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end
 begin
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 forward 10
 left 90
 end */
Read More +
解題區/解題區 - UVa

UVa 12810 - Sumthing

Problem

$$S(1) = \sum_{i=1}^{n} A[i] \\ S(2) = 2 \sum_{i=1}^{n} \sum_{j=i+1}^{n} A[i] A[j] \\ S(3) = 2^{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} A[i] A[j] A[k] \\ ...$$

將 S(1) … S(n) 加總後 mod 1000000009 輸出。

Sample Input

1
2
3
4
5
2
3
1 2 3
5
2 3 5 7 11

Sample Output

1
2
52
66412

Solution

特別發現到 1000000009 是質數，對於任意一個數字都存在乘法反元素，那麼將總和定義為

$(1 + 2 A[0])(1 + 2 A[1])(1 + 2 A[2]) ... (1 + 2 A[n])/2 \text{ mod } 1000000009$

/2 部分利用乘上 2 在 mod 1000000009 下的反元素即可。

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
#include <stdio.h> 
const long long mod = 1000000009LL;
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
} 
int main() {
    int testcase, n;
    long long div2 = mpow(2, mod-2, mod);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long p = 1, x;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            p *= (1 + x * 2);
            p %= mod;
        }
        p = ((p - 1) * div2)%mod;
        printf("%lld\n", p);
    }
    return 0;
}
Read More +
解題區/解題區 - 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 +
解題區/解題區 - 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 +