解題區/解題區 - UVa

UVa 13057 - Prove Them All

Problem

這家公司有自動推論引擎，請問至少要證明幾個基礎定理後，剩餘的都可以藉由推論引擎得到？

Sample Input

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

Sample Output

1
Case 1: 2

Solution

把這張圖的所有 SCC 元件全部縮成一點，變成 DAG 後，計算有幾個節點的 indegree 等於零，其零的個數就是答案。

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
#include <bits/stdc++.h>
using namespace std;
// similar as UVa 11504 - Dominos 
// algorithm: SCC
const int MAXN = 32767;
class SCC {
public:
    int n;
    vector<int> g[MAXN], dag[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = scc_cnt;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    void solve() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 0;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
    }
    void make_DAG() {
        int x, y;
        for (int i = 0; i < n; i++) {
            x = contract[i];
            for (int j = 0; j < g[i].size(); j++) {
                y = contract[g[i][j]];
                if (x != y)
                    dag[x].push_back(y);
            }
        }
        for (int i = 0; i < scc_cnt; i++) {
            sort(dag[i].begin(), dag[i].end());
            dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
        }
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear(), dag[i].clear();
    }
} g;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, u, v;
        scanf("%d %d", &n, &m);
        g.init(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            u--, v--;
            g.addEdge(u, v);
        }
        g.solve();
        g.make_DAG();
        
        int indeg[MAXN] = {}, ret = 0;
        for (int i = 0; i < g.scc_cnt; i++) {
            for (auto &e : g.dag[i]) {
                indeg[e]++;
            }
        }
        for (int i = 0; i < g.scc_cnt; i++)
            ret += indeg[i] == 0;
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13015 - Promotions

Problem

有 $N$ 名員工，他們彼此之間會推薦、相互提拔對方，因此站在公司的角度來看，提拔順序不能違反這張圖的上下關係，亦即若要提拔某人，其推薦他的人全部都要被提拔。請問若要提拔 $A$ 個人，有哪些人一定會被提拔，同樣的，回答提拔 $B$ 個人的情況，最後回答，若提拔 $B$ 個人，誰一定不會被提拔？

Sample Input

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

Sample Output

1
2
3
2
4
3

Solution

一定是張 DAG，否則不能處理。對於輸入多存一張反向圖，接著每一次都去找其下屬節點有多少個，藉此構造出任何提拔方案中，最好和最差排名為多少。處理全部排名計算 $\mathcal{O}(V^2 E)$

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
#include <bits/stdc++.h>
using namespace std;
// O(VE)
const int MAXN = 5005;
int A, B, E, P;
vector<int> G[MAXN], invG[MAXN];
int used[MAXN] = {}, cases = 0;
int dfs(int u, vector<int> g[]) {
    if (used[u] == cases)	return 0;
    used[u] = cases;
    int ret = 1;
    for (auto v : g[u])
        ret += dfs(v, g);
    return ret;
}
int main() {
    int x, y;
    while (scanf("%d %d %d %d", &A, &B, &E, &P) == 4) {
        for (int i = 0; i < E; i++)
            G[i].clear(), invG[i].clear();
        // Must DAG
        for (int i = 0; i < P; i++) {
            scanf("%d %d", &x, &y);
            G[x].push_back(y), invG[y].push_back(x);
        }
        
        int retA = 0, retB = 0, retN = 0;
        for (int i = 0; i < E; i++) {
            int worst, best;
            cases++;
            worst = E - dfs(i, G) + 1;
            cases++;
            best = dfs(i, invG);
            if (worst <= A)	retA++;
            if (worst <= B)	retB++;
            if (best > B)	retN++;
        }
        printf("%d\n%d\n%d\n", retA, retB, retN);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13024 - Saint John Festival

Problem

給予 $N$ 個大天燈的所在位置，隨後有 $Q$ 個小天燈位置，施放天燈後，請問有多少小天燈處於任三個天燈構成的三角形內部？

Sample Input

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

Sample Output

1
3

Solution

由於只詢問任意三個點構成的三角形內部，貪心就能想到一定是挑選凸包上的三點，只需要判定某點是不是在凸包內部，由於所有天燈已經給定，只需要跑一次 $\mathcal{O}(N \log N)$ 凸包算法，接著詢問一點是否在凸包內，只需要 $\mathcal{O}(\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
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-10
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);
    }
};
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 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;
}
double g(Pt a, Pt b, double x) {
    Pt vab = b - a;
    return a.y + vab.y * (x - a.x) / vab.x;
}
int inside_convex(const Pt &p, Pt ch[], int n) {
    if (n < 3)
        return false;
    if (cross(ch[0], p, ch[1]) > eps)
        return false;
    if (cross(ch[0], p, ch[n-1]) < -eps)
        return false;
    
    int l = 2, r = n-1;
    int line = -1;
    while (l <= r) {
        int mid = (l + r)>>1;
        if (cross(ch[0],p, ch[mid]) > -eps) {
            line = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return cross(ch[line-1], p, ch[line]) < eps;
}
Pt D[131072], ch[262144];
int main() {
    int testcase, n, m;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        n = monotone(n, D, ch);
        scanf("%d", &m);
        int ret = 0;
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            int f = inside_convex(Pt(x, y), ch, n);
            ret += f;
        }        
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13029 - Emoticons

Problem

給一個由 ^, _ 構成的字串，請湊出最多的 ^_^ 子字串。

Sample Input

1
2
3
4
5
6
5
_^^_^^_
^__^__^
______
^^__^^
^_^^_^

Sample Output

1
2
3
4
5
Case 1: 1
Case 2: 1
Case 3: 0
Case 4: 2
Case 5: 2

Solution

從左掃瞄到右邊，貪心著手容易得到兩種狀態

  • $h1$: ^ 的個數。
  • $h2$: 湊成 ^???_ 的個數，可以從 $h1$ 合併 _ 構成。

然而有一些特殊案例 ^_^_^^，需要重新排列，他們之間有巢狀關係 (^_(^_^)^)，因此建立狀態 $h3$ 為 ^_^???_，若遇到下一個 ^ 貪心拆解成 (^_(^_^)???)。

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 <bits/stdc++.h>
using namespace std;
char s[131072];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s);
        int ret = 0;
        int h1 = 0, h2 = 0, h3 = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '^' && h2) {
                h2--, ret++;
            } else if (s[i] == '^') {
                if (h3 && ret)
                    h2++, h3--;
                else
                    h1++;
            } else if (s[i] == '_' && h1) {
                h1--, h2++;
            } else if (s[i] == '_') {
                if (ret > h3)
                    h3++;
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13017 - Canvas Painting

Problem

有 $N$ 塊畫布排成一列，並且目標將每一塊畫布變成不同顏色，每一次可以將一個區間塗成相同顏色，花費便是區間 $C_i$ 總和，請問最少花費為何。

Sample Input

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

Sample Output

1
2
29
40

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
#include <bits/stdc++.h>
using namespace std;
// Huffman Coding, Greedy
// input A[1...n]
// minimum \sum A[i]*code[i]
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, x;
        long long t;
        multiset<long long> S;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &x), S.insert(x);
            
        long long ret = 0;
        for (int i = n-2; i >= 0; i--) {
            long long a, b;
            a = *S.begin();
            S.erase(S.begin());
            b = *S.begin();
            S.erase(S.begin());
            ret += a+b;
            S.insert(a+b);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13079 - On the beach

Problem

在炎炎夏日的海邊，需要建立地下通道，把所有海岸飯店聯通在一起，請問最少地下通道個數為何？

Sample Input

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

Sample Output

1
2
3
2
2
1

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    while (scanf("%d", &N) == 1 && N) {
        vector<pair<int, int>> A;
        int L, R;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &L, &R);
            A.push_back(make_pair(L, R));
        }
        sort(A.begin(), A.end());
        
        int ret = 0;
        int PQ = INT_MAX;
        for (int i = 0; i < N; i++) {
            int line_x = A[i].first;
            if (PQ != INT_MAX && PQ <= line_x) {
                ret++;
                PQ = INT_MAX;
            }
            PQ = min(PQ, A[i].second);
        }
        if (PQ != INT_MAX)
            ret++;
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13009 - Fence the vegetables fail

Problem

給一個平行兩軸的簡單多邊形花圃以及一堆蔬菜的座標，請問有多少蔬菜在柵欄的外部，把那些在外部的蔬菜編號加總後輸出。

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
27
28
29
30
31
32
33
34
35
36
37
38
4 8
1 2
1 0
5 3
3 4
0 1
6 1
6 4
4 4
4 3
2 3
2 5
0 5
6 12
6 5
1 9
3 6
3 4
2 0
4 4
5 8
5 3
2 3
2 5
4 5
4 7
0 7
0 1
7 1
7 10
0 10
0 8
1 4
1 1
2 0
2 2
0 2
0 0

Sample Output

1
2
3
6
15
0

Solution

判斷一個點是否在簡單多邊形內部可以使用射線法，然而有很多點詢問，單筆詢問複雜度 $\mathcal{O}(N)$，這樣很明顯地會 TLE。

為了加速判斷，採用掃描線算法，依序放入平行 x 軸的線段，掃描過程中離線詢問某點往 y 軸負方向的射線交點個數為何，維護求交點個數可以利用 binary indexed tree 維護前綴和，前綴和相當於射線交點個數。就能在 $\mathcal{O}(N \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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;
struct Pt {
    int x, y, v;
    Pt(int a = 0, int b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (x != a.x)
            return x < a.x;
        if (y != a.y)
            return y < a.y;
        return false;
    }
};
struct Seg {
    int xl, xr, y;
    Seg(int a = 0, int b = 0, int c = 0):
    xl(a), xr(b), y(c) {}
    bool operator<(const Seg &u) const {
        return xl < u.xl;
    }
};
Pt P[131072], D[131072];
int BIT[262144];
void modify(int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
int query(int x) {
    int sum = 0;
    while (x)
        sum += BIT[x], x -= x&(-x);
    return sum;
}
void solve(int N, int M) {
    map<int, int> RX, RY;
    for (int i = 0; i < N; i++)
        RX[P[i].x] = RY[P[i].y] = 0;
    for (int i = 0; i < M; i++)
        RX[D[i].x] = RY[D[i].y] = 0;
    
    int label_x = 0, label_y = 0;
    
    for (auto &x : RX)
        x.second = ++label_x;
    for (auto &y : RY)
        y.second = ++label_y;
    
    memset(BIT, 0, sizeof(BIT));
    
    for (int i = 0; i < N; i++)
        P[i].x = RX[P[i].x], P[i].y = RY[P[i].y];
    for (int i = 0; i < M; i++)
        D[i].x = RX[D[i].x], D[i].y = RY[D[i].y];
    
    vector<Seg> segs;
    for (int i = 0; i < M; i++) {
        if (D[i].y == D[(i+1)%M].y) {
            int xl = min(D[i].x, D[(i+1)%M].x);
            int xr = max(D[i].x, D[(i+1)%M].x);
            segs.push_back(Seg(xl, xr, D[i].y));
        }
    }
    
    long long outer_val = 0;
    sort(P, P+N);
    sort(segs.begin(), segs.end());
    int Pidx = 0;
    set<std::pair<int, int>> PQ;
    for (int i = 0, line_x = 1; line_x <= label_x; line_x++) {
        while (Pidx < N && P[Pidx].x <= line_x) {
            int intersect = query(P[Pidx].y);
            if (intersect%2 == 0)
                outer_val += P[Pidx].v;
            Pidx++;
        }
        while (!PQ.empty() && PQ.begin()->first <= line_x)
            modify(PQ.begin()->second, -1, label_y), PQ.erase(PQ.begin());
        while (i < segs.size() && segs[i].xl == line_x) {
            modify(segs[i].y, 1, label_y);
            PQ.insert(make_pair(segs[i].xr, segs[i].y));
            i++;
        }
    }
    printf("%lld\n", outer_val);
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &P[i].x, &P[i].y);
            P[i].v = i+1;
        }
        
        for (int i = 0; i < M; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        
        solve(N, M);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13046 - Bus Collisions

Problem

給予兩個公車行駛路線，每台公車的速度都相同，分別從起始位置出發，請問第一個碰撞位置為何？

Sample Input

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

Sample Output

1
2
Case 1: 1 5
Case 2: No Collision

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
#include <bits/stdc++.h>
using namespace std;
struct Pt {
    int x, y;
    Pt(int x = 0, int y = 0): x(x), y(y) {
    }
    int dist(Pt u) {
        return abs(x - u.x) + abs(y - u.y);
    }
    bool operator==(const Pt &u) const {
        return x == u.x && y == u.y;
    }
    Pt operator-(const Pt &u) const {
        return Pt(x - u.x, y - u.y);
    }
    Pt operator+(const Pt &u) const {
        return Pt(x + u.x, y + u.y);
    }
};
int main() {
    int testcase, cases = 0;
    int N[2], x, y;
    Pt R[2][64];
    scanf("%d", &testcase);
    while (testcase--) {
        int Len[2] = {};
        for (int i = 0; i < 2; i++) {
            scanf("%d", &N[i]);
            for (int j = 0; j < N[i]; j++) {
                scanf("%d %d", &x, &y);
                R[i][j] = Pt(x, y);
            }
            for (int j = 0; j < N[i]; j++)
                Len[i] += R[i][j].dist(R[i][(j+1)%N[i]]);
        }
        
        printf("Case %d: ", ++cases);
        
        int simT = Len[0]/__gcd(Len[0], Len[1])*Len[1];
        int posIdx[2], has = 0;
        Pt posXY[2];
        for (int i = 0; i < 2; i++)
            posIdx[i] = 0, posXY[i] = R[i][0];
            
        for (int it = 0; it < simT; it++) {
            for (int i = 0; i < 2; i++) {
                // move
                if (posXY[i] == R[i][posIdx[i]])
                    posIdx[i] = (posIdx[i]+1)%N[i];
                Pt dv = R[i][posIdx[i]] - posXY[i];
                int lenDv = abs(dv.x) + abs(dv.y);
                dv.x /= lenDv, dv.y /= lenDv;
                posXY[i] = posXY[i] + dv;
            }
            if (posXY[0] == posXY[1]) {
                printf("%d %d\n", posXY[0].x, posXY[0].y);
                has = 1;
                break;
            }
        }
        if (!has)
            puts("No Collision");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1718 - Tile Cutting

Problem

請問在網格中，若頂點設置在網格邊上，構成平行四邊形的面積介於 $[l, r]$，最多的方法數和面積分別為多少。

Sample Input

1
2
3
2
4 4
2 6

Sample Output

1
2
48
620

Solution

由於是平行四邊形，假設矩形被劃分的兩個對稱三角形的底高 $a, b, c, d$，且 $a, b, c, d > 0$。

得到平行四邊形面積為

$$\begin{align*} \text{Area} &= (a + c)(b + d) - 2 \times 0.5 \times a b - 2 \times 0.5 \times c d \\ &= ad + bc \end{align*}$$

最後找到構成方法數為 ways of area = #(a, b, c, d) sat. ad + bc = Area。分別統計兩數相乘為 $x$ 的方法數 $W_x$，可以構成多項式 $W_1 x + W_2 x^2 + \cdots W_n x^n$，多項式相乘後，得到的係數就是所有的方法數。套用 FFT 的卷積計算即可。

FFT

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <complex>
using namespace std;
struct Complex {
    double x, y;
    Complex(double x = 0, double y = 0): x(x), y(y) {}
    Complex operator-(const Complex &v) const {
        return Complex(x-v.x,y-v.y);
    }
    Complex operator+(const Complex &v) const {
        return Complex(x+v.x,y+v.y);
    }
    Complex operator*(const Complex &v) const {
        return Complex(x*v.x-y*v.y,x*v.y+y*v.x);
    }
    Complex operator/(const int &v) const {
        return Complex(x/v,y/v);
    }
    double real() {
        return x;
    }
};
template<typename T> class TOOL_FFT {
public:
typedef unsigned int UINT32;
#define MAXN (1048576<<1)
    Complex p[2][MAXN];
    int pre_n;
    T PI;
    TOOL_FFT() {
        pre_n = 0;
        PI = acos(-1);
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0; ; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    
    void FFT(bool InverseTransform, vector<Complex>& In, vector<Complex>& Out) {
        // simultaneous data copy and bit-reversal ordering into outputs
        int NumSamples = In.size();
        int NumBits = NumberOfBitsNeeded(NumSamples);
        for (int i = 0; i < NumSamples; ++i) {
            Out[FastReverseBits(i, NumBits)] = In[i];
        }
        // the FFT process
        for (register int i = 1; i <= NumBits; i++) {
            int BlockSize = 1<<i, BlockEnd = BlockSize>>1, BlockCnt = NumSamples/BlockSize;
            for (register int j = 0; j < NumSamples; j += BlockSize) {
                Complex *t = p[InverseTransform];
                for (register int k = 0; k < BlockEnd; k++, t += BlockCnt) {
                    Complex a = (*t) * Out[k+j+BlockEnd];
                    Out[k+j+BlockEnd] = Out[k+j] - a;
                    Out[k+j] = Out[k+j] + a;
                }
            }
        }
        // normalize if inverse transform
        if (InverseTransform) {
            for (int i = 0; i < NumSamples; ++i) {
                Out[i] = Out[i] / NumSamples;
            }
        }
    }
    void prework(int n) {
        if (pre_n == n)
            return ;
        pre_n = n;
        p[0][0] = Complex(1, 0);
        p[1][0] = Complex(1, 0);
        for (register int i = 1; i < n; i++) {
            p[0][i] = Complex(cos(2*i*PI / n ) , sin(2*i*PI / n ));
            p[1][i] = Complex(cos(2*i*PI / n ) , -sin(2*i*PI / n ));
        }
    }
    vector<T> convolution(Complex *a, Complex *b, int n) {
        prework(n);
        vector<Complex> s(a, a+n), d1(n), d2(n), y(n);
        vector<T> ret(n);
        FFT(false, s, d1);
        s[0] = b[0];
        for (int i = 1, j = n-1; i < n; ++i, --j)
            s[i] = b[j];
        FFT(false, s, d2);
        for (int i = 0; i < n; ++i) {
            y[i] = d1[i] * d2[i];
        }
        FFT(true, y, s);
        for (int i = 0; i < n; ++i) {
            ret[i] = s[i].real();
        }
        return ret;
    }
};
TOOL_FFT<double> tool;
Complex a[MAXN], b[MAXN];
vector<double> c;
long long ret[1048576];
long long pr[1048576] = {};
int main() {
    int m;
    const int N = 500000;
    for (m = 1; m < (N<<1); m <<= 1);
    /*
		(a + c)(b + d) - 2 * 0.5 * (a b) - 2 * 0.5 * (c * d)
		= ad + bc = area
		a, b, c, d > 0,
		ways of area = #(a, b, c, d) sat. ad + bc = area
	*/
    for (int i = 1; i <= N; i++) {
    	for (int j = i; j <= N; j += i)
    		pr[j]++;
    }	
    
    memset(a, 0, sizeof(a[0]) * m);
    memset(b, 0, sizeof(b[0]) * m);
    
    for (int i = 1; i <= N; i++) {
        a[i] = Complex(pr[i], 0);
        b[m-i] = Complex(pr[i], 0);
    }	
    
    c = tool.convolution(a, b, m);
    
    for (int i = 1; i <= N; i++)
        ret[i] = (long long) (c[i] + 0.5);
        
    int testcase, L, R;
    while (scanf("%d", &testcase) == 1) {
        while (testcase--)	 {
            scanf("%d %d", &L, &R);
            assert(L <= R);
            assert(L >= 1 && R <= 500000);
            int mxA = L;
            for (int i = L; i <= R; i++) {
                if (ret[i] > ret[mxA])
                    mxA = i;
            }
            printf("%d %lld\n", mxA, ret[mxA]);
        }
    }
    return 0;
}

NTT

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 <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <complex>
using namespace std;
typedef unsigned int UINT32;
typedef long long INT64;
class TOOL_NTT {
public:
#define MAXN (1048576<<1)
    const INT64 P = (479 << 21) + 1LL; // prime m = kn+1
    const INT64 G = 3;
    INT64 wn[22];
    INT64 s[MAXN], d1[MAXN], d2[MAXN], y[MAXN];
    TOOL_NTT() {
        for (int i = 0; i < 22; i++)
            wn[i] = mod_pow(G, (P-1) / (1<<i), P);
    }
    INT64 mod_mul(INT64 a, INT64 b, INT64 mod) {
        return (a*b - (long long)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
//              INT64 ret = 0;
//              for (a = a >= mod ? a%mod : a, b = b >= mod ? b%mod : b; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) {
//                  if (b&1) {
//                      ret += a;
//                      if (ret >= mod)
//                          ret -= mod;
//                  }
//              }
//              return ret;
    }
    INT64 mod_pow(INT64 n, INT64 e, INT64 m) {
        INT64 x = 1;
        for (n = n >= m ? n%m : n; e; e >>= 1) {
            if (e&1)
                x = mod_mul(x, n, m);
            n = mod_mul(n, n, m);
        }
        return x;
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0;; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    void NTT(int on, INT64 *In, INT64 *Out, int n) {
        int NumBits = NumberOfBitsNeeded(n);
        for (int i = 0; i < n; ++i)
            Out[FastReverseBits(i, NumBits)] = In[i];
        for(int h = 2, id = 1; h <= n; h <<= 1, id++) {
            for(int j = 0; j < n; j += h) {
                INT64 w = 1, u, t;
                int block = h/2, blockEnd = j + h/2;
                for(int k = j; k < blockEnd; k++) {
                    u = Out[k], t = mod_mul(w, Out[k+block], P);
                    Out[k] = u + t;
                    Out[k + block] = u - t + P;
                    if (Out[k] >= P)        Out[k] -= P;
                    if (Out[k+block] >= P)  Out[k+block] -= P;
                    w = mod_mul(w, wn[id], P);
                }
            }
        }
        if (on == 1) {
            for (int i = 1; i < n/2; i++)
                swap(Out[i], Out[n-i]);
            INT64 invn = mod_pow(n, P-2, P);
            for (int i = 0; i < n; i++)
                Out[i] = mod_mul(Out[i], invn, P);
        }
    }
    void convolution(INT64 *a, INT64 *b, int n, INT64 *c) {
        NTT(0, a, d1, n);
        s[0] = b[0];
        for (int i = 1; i < n; ++i)
            s[i] = b[n-i];
        NTT(0, s, d2, n);
        for (int i = 0; i < n; i++)
            s[i] = mod_mul(d1[i], d2[i], P);
        NTT(1, s, c, n);
    }
} tool;
INT64 a[MAXN], b[MAXN], c[MAXN];
long long ret[1048576];
long long pr[1048576] = {};
int main() {
    int m;
    const int N = 500000;
    for (m = 1; m < (N<<1); m <<= 1);
    /*
		(a + c)(b + d) - 2 * 0.5 * (a b) - 2 * 0.5 * (c * d)
		= ad + bc = area
		a, b, c, d > 0,
		ways of area = #(a, b, c, d) sat. ad + bc = area
	*/
    for (int i = 1; i <= N; i++) {
    	for (int j = i; j <= N; j += i)
    		pr[j]++;
    }	
    
    memset(a, 0, sizeof(a[0]) * m);
    memset(b, 0, sizeof(b[0]) * m);
    
    for (int i = 1; i <= N; i++) {
        a[i] = pr[i];
        b[m-i] = pr[i];
    }	
    
    tool.convolution(a, b, m, c);
    
    for (int i = 1; i <= N; i++)
        ret[i] = c[i];
        
    int testcase, L, R;
    while (scanf("%d", &testcase) == 1) {
        while (testcase--)	 {
            scanf("%d %d", &L, &R);
            assert(L <= R);
            assert(L >= 1 && R <= 500000);
            int mxA = L;
            for (int i = L; i <= R; i++) {
                if (ret[i] > ret[mxA])
                    mxA = i;
            }
            printf("%d %lld\n", mxA, ret[mxA]);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 801 - Flight Planning

Problem

給予飛機在平流層飛行資訊，在每一種高度下維持飛行的耗油量成線性關係，以及每一段飛行旅程上的平流層的風速為何，藉由線性內插得到在某高度下的飛行速度，忽略在轉換高度時的耗油量，問從起點到終點的最少耗油量為何 (無條件進位)。

Sample Input

1
2
3
4
5
6
7
8
2
2
1500 -50 50
1000 0 0
3
1000 50 0
2000 0 20
1800 50 100

Sample Output

1
2
Flight 1: 35 30 13986
Flight 2: 20 30 30 23502

Solution

單源最短路徑，只是每一點要使用 $20$ 個狀態維護抵達那一層時在哪一種高度下飛行。必須窮舉轉移到下一層的所有高度，因為有可能飛行慢而增加耗油時間。

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Leg {
    double mile, f20, f40;
} legs[1024];
const double VCRUISE = 400;
const double AOPT = 30000;
const double GPHOPT = 2000;
const double GPHEXTRA = 10;
const double CLIMBCOST = 50;
const int MAXN = 1024;	// maximum #legs
const int MAXH = 45;	// between 20,000 and 40,000 feet
const double DINF = 1e+20;
double inter(Leg a, double h) {
    return a.f20 + (a.f40 - a.f20) * (h - 20000) / (40000 - 20000);
}
void solve(int n) {
    double dp[MAXN][MAXH];
    int from[MAXN][MAXH];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 40; j++)
            dp[i][j] = DINF;
    }
    
    dp[0][0] = 0;	// leg 0: altitude 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 40; j++) {
            if (dp[i][j] >= DINF)
                continue;
            double alti_a = j * 1000.f;
            for (int k = 20; k <= 40; k++) {
                double cc = 0, alti_b;
                alti_b = k * 1000.f;
                
                if (alti_b > alti_a)
                    cc += CLIMBCOST * (alti_b - alti_a) / 1000.f;
                double v = VCRUISE + inter(legs[i+1], alti_b);
                if (v <= 0)
                	continue;
                double c = fabs(alti_b - AOPT) * GPHEXTRA / 1000.f + GPHOPT;
                cc += c * legs[i+1].mile / v;
                if (dp[i][j] + cc < dp[i+1][k])
                    dp[i+1][k] = dp[i][j] + cc, from[i+1][k] = j;
            }
        }
    }
    
    double ret = DINF;
    int last = -1;
    vector<int> solution;
    for (int i = 20; i <= 40; i++) {
        if (dp[n][i] < ret)
            ret = dp[n][i], last = i;
    }
    for (int i = n; i > 0; i--) {
        solution.push_back(last);
        last = from[i][last];
    }
    for (int i = n-1; i >= 0; i--)
        printf(" %d", solution[i]);
    // tricky 
    printf(" %.0lf\n", ceil(ret));
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf %lf",
                  &legs[i].mile, &legs[i].f20, &legs[i].f40);
        }
        printf("Flight %d:", ++cases);
        solve(n);
    }
    return 0;
}
Read More +