解題區/解題區 - 其他題目

2015 Google Code Jam Round 2

超過凌晨的競賽，隔天起床有一種說不出的疲累感，坑了一個早上，仍然沒想到最後幾題。看來已經玩不下去！圍觀到這裡。

A. Pegman

在谷歌地圖上放置一個小人，小人會根據當前給予的方向指標持續地移動，直到碰到下一個方向指標，請問至少要改變幾個方向指標所指引的方向，滿足在任何一個小人位置都不會走到邊界外部。

由於放在非指標位置就不能移動，只需要考慮小人放在指標上，考慮每一個方向指標都指向另一個指標，這樣就能保證有數個循環，盡可能地挑選原方向。

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 <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
char sg[128][128];
int ig[128][128];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dd[] = "><v^";
int main() {
    int testcase, n, m, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", sg[i]);
        
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (sg[i][j] != '.') {
                    ig[i][j] = idx++;
                }
            }
        }
        
        int match = 0, ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (sg[i][j] != '.') {
                    int odd = 0;
                    for (int k = 0; k < 4; k++)
                        if (dd[k] == sg[i][j])
                            odd = k;
                    int cost = 1, mm = 0;
                    for (int k = 0; k < 4; k++) {
                        int x = i, y = j;
                        x += dx[k], y += dy[k];
                        while (x < n && x >= 0 && y < m && y >= 0) {
                            if (sg[x][y] != '.') {
                                if (k == odd)
                                    cost = 0;
                                mm = 1;
                                break;
                            }
                            x += dx[k], y += dy[k];
                        }
                    }
                    match += mm, ret += cost;
                }
            }
        }
        
        printf("Case #%d: ", ++cases);
        if (match != idx)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ret);
    }
    return 0;
}

B. Kiddie Pool

放滿游泳池的水，目標容積 $V$ 溫度 $X$，有 $N$ 種水源，每一種水源有各自的流速 $R$、溫度 $C$，水源可以同時放水，請問達到目標容積、溫度的最少時間為何。

當下直觀地沒考慮水源可以同時使用，卡了一陣子。

Linear Programming

發現可以同時運作，考慮二分最少時間，其中一種最簡單的應用線性規劃，判斷線性規劃方程式是否有解，python 內建 LP 也許很過分。自己曾經寫過 simplex，不過調校上相當痛苦，判斷有沒有解有困難。以下為 LP 模型，二分時間 $\text{limit_time}$。

  1. $x_i \le \text{limit_time} * R[i]$
  2. $\sum{C_i x_i} = V X$
  3. $\sum x_i = V$
  4. $x_i \ge 0$

帶入 simplex algorithm，判斷四條方程式是否有解。代碼就不附，解不出來。

Greedy

另外一種方式，考慮限制 t 時間內能調配的最高溫 high_t、最低溫 low_t，這兩種溫度可以貪心法求得，接著考慮目標溫度 low_t <= X <= high_t，因為中間的溫度一定可解，具有連續性。

複雜度 $O(N \log X)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
const double eps = 1e-10;
double R[MAXN], C[MAXN], V, X;
int N;
vector< pair<double, double> > A;
int checkTime(double limitT) {
    double v, t, low_t, high_t;
    double mxV, teC;
    
    v = t = 0;
    for (int i = 0; i < N; i++) {
        mxV = A[i].second * limitT; // flow in limit time
        teC = A[i].first;
        
        mxV = min(mxV, V - v);
        t = (t * v + mxV * teC) / (v + mxV);
        v += mxV;
        if (v >= V - eps)
            break;
    }
    if (v < V - eps)
        return 0;
    low_t = t;
    
    v = t = 0;
    for (int i = N-1; i >= 0; i--) {
        mxV = A[i].second * limitT; // flow in limit time
        teC = A[i].first;
        
        mxV = min(mxV, V - v);
        t = (t * v + mxV * teC) / (v + mxV);
        v += mxV;
        if (v >= V - eps)
            break;
    }
    if (v < V - eps)
        return 0;
    high_t = t;
    return X >= low_t - eps && X <= high_t + eps;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %lf %lf", &N, &V, &X);
        
        A.clear();
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &R[i], &C[i]);
            A.push_back(make_pair(C[i], R[i]));
        }
        sort(A.begin(), A.end());
        
        double mxT, mnT;
        mnT = A[0].first, mxT = A[N-1].first;
        
        printf("Case #%d: ", ++cases);
        if (X < mnT - eps || X > mxT + eps) {
            puts("IMPOSSIBLE");
        } else {
            double l = 0, r = 1e+9, mid; // MAXV / MINR = 10000.0 / 0.0001 
            double ret = 0;
            for (int it = 0; it < 256; it++) {
                mid = (l + r)/2;
                if (checkTime(mid))
                    r = mid, ret = mid;
                else
                    l = mid;
            }
            printf("%.8lf\n", ret);
        }
    }
    return 0;
}

Minkowski Sum

在此先將問題轉換成「求 1 秒內最多能湊出多少公升的 X 度水」，知道單位時間內的最多流量，就能貪心得到最短時間。

將每一種水源 $(R_i, C_i)$ 轉換成向量 $v_i = (R_i, R_i \times C_i)$，目標要在 $t$ 時間內，得到 $\sum{t_i v_i} = (V, V \times X)$，滿足所有的 $t_i \le t$

將問題壓縮成 $t_i \in \left \[ 0, 1 \right]$，將所有符合的 $\sum{t_i v_i}$ 疊加起來，得到的區域相當於在做 Minkowski Sum，區域是一個凸多邊形。接著在 $y = X x$ 尋找交集的最大 x 值。

Demo

上圖是一個 3 個水源的情況，假設要湊出溫度 $X = 0.5$，相當於找 $y = 0.5 x$，這三個向量在單位時間內的疊加為淡紅色區域。為了得到這淡紅色區域，使用極角排序，依序疊加可以得到下凸包，反過來疊加可以得到上凸包。

明顯地要找一個凸包跟一條線的交點，得到單位時間內的最大流量。此時的 x 軸表示流量、y 軸表示熱量，找到交集中最大的 x 座標值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    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 (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
Pt getIntersect(Pt as, Pt ae, Pt bs, Pt be) {
    Pt u = as - bs;
    double t = cross2(be - bs, u)/cross2(ae - as, be - bs);
    return as + (ae - as) * t;
}
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
//
const int MAXN = 128;
int N;
double R[MAXN], C[MAXN], V, X;
void solveWithMinkowskiSum() {
    vector<Pt> P;
    for (int i = 0; i < N; i++)
        P.push_back(Pt(R[i], R[i]*C[i]));
    sort(P.begin(), P.end(), cmp);  // solar sort
    
    vector<Pt> convex;
    double mxFlow = 0;              // in unit time with temperature X
    Pt u, v, o(0, 0), to(1, X);     // y = (X) x, maximum x
    
    u = v = Pt(0, 0);
    convex.push_back(u);
    for (int i = 0; i < N; i++) {
        v = u + P[i];
        u = v;
        convex.push_back(v);
    }
    
    reverse(convex.begin(), convex.end());
    u = v = Pt(0, 0);
    for (int i = N-1; i >= 0; i--) {
        v = u + P[i];
        u = v;
        convex.push_back(v);
    }
    
    for (int i = 0, j = (int) convex.size()-1; i < convex.size(); j = i++) {
        u = convex[j], v = convex[i];
        if (cmpZero(cross(o, to, u)) * cmpZero(cross(o, to, v)) < 0) {
            Pt in = getIntersect(o, to, u, v);
            mxFlow = max(mxFlow, in.x);
        }
        if (cmpZero(cross(o, to, v)) == 0)
            mxFlow = max(mxFlow, v.x);
    }
    
    if (fabs(V) < eps)
        printf("%.10lf\n", 0.0);
    else if (fabs(mxFlow) < eps)
        puts("IMPOSSIBLE");
    else
        printf("%.10lf\n", V / mxFlow);
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %lf %lf", &N, &V, &X);
        
        V *= 10000, X *= 10000;
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &R[i], &C[i]);
            R[i] *= 10000, C[i] *= 10000;
        }
        
        printf("Case #%d: ", ++cases);
        solveWithMinkowskiSum();
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

ITSA 2015 第四屆 桂冠賽

有 中文題目，那就不多做解釋，咱們直接來坑題解。由於我沒有參與比賽，目前也沒辦法進行 submit 測試我的代碼跟算法正確性。因此以下內容、代碼僅供參考。

題目已經放在 E-tutor，但沒提供測試功能，不能 submit 的 OJ 相當逗趣，再等幾天吧，也許在調數據的時間，或者是根本不打算弄好 … 也許是下一次舉辦比賽才完成。

看過一次題目，大約有下列特徵算法 模擬、Bfs、樹形 dp、拓樸排序、最短路徑、dp、二分圖最大匹配、搜索優化、矩形并、掃描線、二分答案。有一題沒看懂，對於那題多維度部分，可能需要的是假解搜索。

有提供中文題目描述呢，不確定自己是否都看得懂，當然程式有點 bug 的話，歡迎大家來 challenge。

感謝各位提供的解法！讓我更了解 BWT $O(n)$ 逆變換。

Problem A

每一輪進行投票，將少數票的那一方留下，直接模擬運行即可，UVa 也有類似的題目。

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
#include <stdio.h>
#include <vector>
using namespace std;
int A[1024][512];
char s[16];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%s", s);
                A[i][j] = s[0] == 'Y';
            }
        }
        
        vector<int> p;
        for (int i = 0; i < n; i++)
            p.push_back(i);
        for (int i = 0; i < m; i++) {
            int Y = 0;
            for (int j = 0; j < p.size(); j++)
                Y += A[p[j]][i] == 1;
            if (Y == p.size() - Y || Y == 0 || Y == p.size())
                continue;
            vector<int> np;
            for (int  j = 0; j < p.size(); j++) {
                if (Y < p.size() - Y) {
                    if (A[p[j]][i] == 1)
                        np.push_back(p[j]);
                } else {
                    if (A[p[j]][i] == 0)
                        np.push_back(p[j]);
                }
            }
            p = np;
        }
        
        for (int i = 0; i < p.size(); i++) {
            printf("%d%c", p[i]+1, i == p.size()-1 ? '\n' : ' ');
        }
    }
    return 0;
}

Problem B

兩個機器人運行的行動和週期不同，用 timeline 的方式去模擬兩台機器人的狀態，利用 time mod (N + E) 來得到當前屬於前 N 還是後 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
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
    int testcase;
    int N, M, N1, F1, N2, F2;
    int X1, Y1, E1, X2, Y2, E2;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &M, &N);
        scanf("%d %d %d %d %d", &X1, &Y1, &E1, &N1, &F1);
        scanf("%d %d %d %d %d", &X2, &Y2, &E2, &N2, &F2);
        
        int has = 0;
        for (int i = 0; i <= max(F1, F2); i++) {
            if (X1 == X2 && Y1 == Y2) {
                printf("robots explode at time %d\n", i);
                has = 1;
                break;
            }
            if (i < F1) {
                if (i%(N1 + E1) < N1)
                    Y1 = (Y1 + 1)%N;
                else
                    X1 = (X1 + 1)%M;
            }
            if (i < F2) {
                if (i%(N2 + E2) < E2)
                    X2 = (X2 + 1)%M;
                else
                    Y2 = (Y2 + 1)%N;
            }
        }
        
        if (!has)
            puts("robots will not explode");
    }
    return 0;
}

Problem C

樹中心 (把一點當根，到所有葉節點距離最大值越小越好)，其中一種方法是使用樹形 dp，另外一種方法是拓樸排序。保證樹中心會在最長路徑上的中點，當最長路徑是偶數個頂點構成，則中心會有兩個代表，反之會有一個。只會有這兩種情況。

那麼拓樸排序拔點，順便紀錄拓樸的深度 (分層去看)，看最後一層有一個點、還是兩個點，找字典順序最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
vector<int> g[MAXN];
int deg[MAXN], dist[MAXN];
int main() {
    int testcase, n, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            g[i].clear(), deg[i] = 0, dist[i] = -1;
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++, deg[v]++;
        }
        
        queue<int> Q;
        for (int i = 0; i < n; i++)
            if (deg[i] == 1)
                Q.push(i), dist[i] = 1;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < g[u].size(); i++) {
                v = g[u][i];
                if (--deg[v] == 1) {
                    dist[v] = dist[u] + 1;
                    Q.push(v);
                }
            }
        }
        
        int mx = 0, ret;
        for (int i = 0; i < n; i++) {
            if (dist[i] > mx)
                mx = dist[i], ret = i;
        }
        printf("%d\n", ret);
    }
    return 0;
}

Problem D

Bfs 搜索，定義狀態為 dist[x][y][dir] 表示從起點到 (x, y) 時，利用 dir 方向上的門進入的最短路徑，接著按照 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
#include <stdio.h> 
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 20;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0}; 
char sg[MAXN][MAXN][4][8];
int dist[MAXN][MAXN][4];
int toDir(char c) {
    switch(c) {
        case 'E': return 0;
        case 'S': return 1;
        case 'W': return 2;
        case 'N': return 3;
    }
    return -1;
}
void bfs(int dir, int sx, int sy, int ex, int ey) {
    queue<int> X, Y, D;
    memset(dist, 0, sizeof(dist));
    X.push(sx), Y.push(sy), D.push(dir);
    dist[sx][sy][dir] = 1;
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        dir = D.front(), D.pop();
        if (sx == ex && sy == ey) {
            printf("%d\n", dist[sx][sy][dir]);
            return ;
        }
        for (int i = 0; sg[sx][sy][dir][i]; i++) {
            int d = toDir(sg[sx][sy][dir][i]);
            int tx, ty, td;
            tx = sx + dx[d], ty = sy + dy[d];
            td = (d + 2)%4;
            if (dist[tx][ty][td] == 0) {
                dist[tx][ty][td] = dist[sx][sy][dir]+1;
                X.push(tx), Y.push(ty), D.push(td);
            }
        } 
    }
    puts("Are you kidding me?");
}
int main() {
    int testcase;
    int n, m, q, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d %d", &x, &y);
                for (int k = 0; k < 4; k++)
                    scanf("%s", &sg[x][y][k]);
            }
        }
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            int ex, ey, sx, sy;
            char s[8];
            scanf("%s %d %d %d %d", &s, &sx, &sy, &ex, &ey);
            bfs(toDir(s[0]), sx, sy, ex, ey);
        }
        puts("----------");
    }
    return 0;
}

Problem E

題目沒看懂，一扯到多維度計算，似乎每年都是同一個出題者嗎？有一種既視感。

Problem F

可以參照 Zerojudge 基因的核，找到多字串的 LCS 長度。但是這一題要求找到所有 LCS，而且還要按照字典順序排好，同時也不能輸出重複的。根據討論，輸出結果可能破百萬，那麼從輸出檔案中得知，這有點不科學大小，光是輸出有可能就會 TLE。

下方的代碼也許只有長度輸出是正確的，在輸出解部分有點問題，假設答案總數並不多，為了加速排序部分以及重複回溯，使用 trie 來輔助完成。若答案總數過多，會使得 trie 記憶體滿溢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXP = 1<<21;
const int MAXN = 4;
const int MAXL = 64;
char pwd[MAXN][MAXL];
int pwdLen[MAXN], A[MAXN], n, sumA;
char dp[MAXP];
int arg_dp[MAXP][2];
void dfs(int dep, int idx[], int v) {
    if (dep == n) {
        int same = 1;
        for (int i = 1; i < n; i++)
            same &= pwd[i][idx[i]] == pwd[0][idx[0]];
        if (same) {
            int s = 0;
            arg_dp[v][0] = -1, arg_dp[v][1] = pwd[0][idx[0]];
            for (int i = 0; i < n; i++) {
                if (idx[i] == 0) {
                    dp[v] = 1;
                    return ;
                }
                s = s + (idx[i]-1) * A[i];
            }
            dp[v] = dp[s] + 1, arg_dp[v][0] = s;
        } else {
            arg_dp[v][0] = -2;
            for (int i = 0; i < n; i++) {
                if (idx[i] == 0)
                    continue;
                if (dp[v - A[i]] > dp[v])
                    dp[v] = dp[v - A[i]];
            }
        }
        return ;
    }
    for (int i = 0; i < pwdLen[dep]; i++) {
        idx[dep] = i;
        dfs(dep+1, idx, v + A[dep] * i);
    }
}
// 
#define MAXCHAR (52 + 10)
#define MAXNODE (131072)
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        set<int> S;
        void init() {
            cnt = 0, S.clear();
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
    	assert(size < MAXNODE);
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
    	if (c <= '9')	return c - '0';
    	if (c <= 'Z')	return 10 + c - 'A';
    	if (c <= 'z')	return 36 + c - 'a';
        assert(false);
    }
    inline int toChar(int i) {
    	if (i < 10)		return i + '0';
    	if (i < 36)		return i - 10 + 'A';
    	if (i < 62)		return i - 36 + 'a';
    	assert(false);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt += w;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
        
    void free() {
        return ;
    }
} tool;
char s[MAXL];
void dfsLCS(int idx[], int v, Trie::Node *u) {
    if (v < 0)
        return ;
    
    if (arg_dp[v][0] >= -1) {
        int vidx = tool.toIndex(arg_dp[v][1]);
        if (u->next[vidx] == NULL)	
            u->next[vidx] = tool.getNode();
        u = u->next[vidx];
        if (u->S.count(v))
            return;
        u->S.insert(v);
        if (dp[v] == 1)
            return ;
        if (arg_dp[v][0] != -1) {
            for (int i = 0; i < n; i++)
                idx[i]--;
            dfsLCS(idx, arg_dp[v][0], u);
            for (int i = 0; i < n; i++)
                idx[i]++;
        }
    } else {
        if (u->S.count(v))
            return;
        u->S.insert(v);
        for (int i = 0; i < n; i++) {
            if (idx[i] == 0)
                continue;
            if (dp[v - A[i]] == dp[v]) {
                idx[i]--;
                dfsLCS(idx, v - A[i], u);
                idx[i]++;
            }
        }
    }
}
void printLCS(int dep, Trie::Node *u, char *s, vector<string> &ret) {
    if (u == NULL)	return;
    if (dep == -1) {
        ret.push_back(s+1);
        return;
    }
    for (int i = 0; i < MAXCHAR; i++) {
        *s = tool.toChar(i);
        printLCS(dep-1, u->next[i], s-1, ret);
    }
}
int countLCS(int dep, Trie::Node *u, char *s) {
    if (u == NULL)	return 0;
    if (dep == -1)
        return 1;
    int ret = 0;
    for (int i = 0; i < MAXCHAR; i++) {
        *s = tool.toChar(i);
        ret += countLCS(dep-1, u->next[i], s-1);
    }
    return ret;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", pwd[i]);
            pwdLen[i] = strlen(pwd[i]);
        }
        A[0] = 1;
        for (int i = 1; i < n; i++)
            A[i] = A[i-1] * pwdLen[i-1];
        
        memset(dp, 0, sizeof(char) * A[n-1] * pwdLen[n-1]);
        
        int idx[MAXN], f = A[n-1] * pwdLen[n-1] - 1;
        dfs(0, idx, 0);
        
//		printf("%d\n", (int) dp[f]);
        
        tool.init();
        memset(s, 0, sizeof(s));
        for (int i = 0; i < n; i++)
            idx[i] = pwdLen[i]-1;
        dfsLCS(idx, f, tool.root);
        printf("%d\n", countLCS(dp[f]-1, tool.root, s + dp[f]-1));
        vector<string> ret;
        printLCS(dp[f]-1, tool.root, s + dp[f]-1, ret);
        sort(ret.begin(), ret.end());
        for (int i = 0; i < ret.size(); i++)
            printf("%s\n", ret[i].c_str());
    }
    return 0;
}
/*
999
2
abcdabcdabcdabcdefghefghefghefgh
dcbadcbadcbadcbahgfehgfehgfehgfe
2
abcdabcdabcdabcd
dcbadcbadcbadcba
999
2
abcabcaa
acbacba
2
abcdfgh
abccfdsg
3
3124158592654359
3173415926581359
763141578926536359 
*/

Problem G

看起來是一題二分圖找最大匹配數，可以利用 maxflow 或者是匈牙利算法得到。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 1024;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int testcase;
    int n, m;
    int nx[128], ny[128], mx[128], my[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &nx[i], &ny[i]);
        for (int i = 0; i < m; i++)
            scanf("%d %d", &mx[i], &my[i]);
            
        int source = n+m, sink = n+m+1;
        g.Init(n+m+2);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (abs(nx[i]-mx[j]) + abs(ny[i]-my[j]) <= 5)
                    g.Addedge(i, j+n, 1);
            }
        }
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1);
        for (int i = 0 ; i < m; i++)
            g.Addedge(i+n, sink, 1);
            
        int flow = g.Maxflow(source, sink);
        printf("%d\n", flow);
    }
    return 0;
}

Problem H

如果摩擦力和位能動能互換是連續的，那這一題的作法可能就會有問題。很明顯地為了要求出起點到終點的最少能量需求，必然希望最後到終點的能量恰好為 0，因此逆推最少能量消耗，從終點推論到起點。

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 8192;
int n, m, st, ed, h[MAXN];
vector< pair<int, int> > g[MAXN];
int dist[MAXN], inq[MAXN];
void spfa(int st, int ed, int n) {
    for (int i = 0; i < n; i++)
        dist[i] = 0x3f3f3f3f, inq[i] = 0;
    queue<int> Q;
    int u, v, w;
    dist[ed] = 0, Q.push(ed);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++)  {
            v = g[u][i].first, w = g[u][i].second;
            if (h[v] > h[u]) {
                if (dist[v] > max(dist[u] - (h[v] - h[u]) + w, 0)) {
                    dist[v] = max(dist[u] - (h[v] - h[u]) + w, 0);
                    if (inq[v] == 0) {
                        inq[v] = 1;
                        Q.push(v);
                    }
                }
            } else {
                if (dist[v] > dist[u] + (h[u] - h[v]) + w) {
                    dist[v] = dist[u] + (h[u] - h[v]) + w;
                    if (inq[v] == 0) {
                        inq[v] = 1;
                        Q.push(v);
                    }
                } 
            }
            
        }
    }
    printf("%d\n", dist[st]);
}
int main() {
    int testcase;
    int u, v, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d %d", &n, &m, &st, &ed);
        st--, ed--;
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < n; i++)
            scanf("%d", &h[i]);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            u--, v--;
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        
        spfa(st, ed, n);
    }
    return 0;
}

Problem I

快速找到多少對的漢明距離恰好相差 P，保證任兩個字串不同，暴力法是直接 $O(N^2)$ 進行比較。由於字串長度不長，可以考慮一下到底要怎麼優化。這一題突然可以想到 UVa 1462 - Fuzzy Google Suggest，但是那一題考慮到字符串長度會比較長，而且還有編輯距離的搜索，跟漢明距離有點差別，也是值得思考的題目。

由於字串長度為 4，只使用大寫字母和數字，下面測試想法 5 組 50000 個的字串，大約跑了 4 秒，不曉得能不能通過正式比賽的數據。想法很簡單，窮舉相同的位置後，利用排容原理找完全不同的字串數量。

例如給定 ABCD，此時 $P = 2$，那麼找到符合 A_C_ 所有的情況，符合配對的字串保證有相似程度有 2 個，但是這些情況可能會出現 ABC_、A_CD、ABCD，也就是說為了找到符合 A_C_，__ 不能填入 BD 的任何相似，計算排容得到完全不相似 (有一個相同的位置) 的個數。

Version 1

直接用字串進行檢索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        map< string, map<string, int> > FUZZY[1<<4];
        map< string, int > CNT[1<<4];
        int ret = 0;
        char s[8], s1[8], s2[8], s3[8];
        int same = 4 - m, diff = m;
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1[sidx1++] = s[k];
                        else 
                            s2[sidx2++] = s[k];
                    }
                    
                    s1[sidx1] = '\0', s2[sidx2] = '\0', s3[sidx2] = '\0';
                    
                    map<string, int> &tfuzzy = FUZZY[j][s1];
                    int tot = CNT[j][s1], similar = 0;
                    if (tot == 0)	continue;
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3[p] = s2[p];
                            else
                                s3[p] = '_';
                        }
//						cout << s3 << endl; 
                        if (__builtin_popcount(k)%2 == 0)
                            similar -= tfuzzy[s3];
                        else
                            similar += tfuzzy[s3];
                    }
                    
                    ret += tot - similar;
//					printf("%d -- %d %d\n", tot - similar, tot, similar);
                }
            }
            
            // add
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0, sidx3 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1[sidx1++] = s[k];
                        else 
                            s2[sidx2++] = s[k];
                    }
                    s1[sidx1] = '\0', s2[sidx2] = '\0', s3[sidx2] = '\0';
                    map<string, int> &tfuzzy = FUZZY[j][s1];
                    CNT[j][s1]++;
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3[p] = s2[p];
                            else
                                s3[p] = '_';
                        }
                        tfuzzy[s3]++;
                    }
                }
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}

Version 2

將字串轉數字當作索引值加快速度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
int toIndex(int x) { // [0...36]
    if ('0' <= x && x <= '9')
        return x - '0';
    if ('A' <= x && x <= 'Z')
        return x + 10 - 'A';
    return 36;
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        map< int, map<int, int> > FUZZY[1<<4];
        map< int, int > CNT[1<<4];
        int ret = 0;
        char s[8], s2[8], s3[8];
        int same = 4 - m, diff = m;
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0;
                    int s1 = 0, s3 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1 = s1 * 37 + toIndex(s[k]);
                        else 
                            s2[sidx2++] = s[k];
                    }
                                        
                    map<int, int> &tfuzzy = FUZZY[j][s1];
                    int tot = CNT[j][s1], similar = 0;
                    CNT[j][s1]++;
                    
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        s3 = 0;
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3 = s3 * 37 + toIndex(s2[p]);
                            else
                                s3 = s3 * 37 + toIndex('_');
                        }
                        if (__builtin_popcount(k)%2 == 0)
                            similar -= tfuzzy[s3];
                        else
                            similar += tfuzzy[s3];
                        
                        tfuzzy[s3]++;
                    }
                    
                    ret += tot - similar;
//					printf("%d -- %d %d\n", tot - similar, tot, similar);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Version 3

發現排容地方寫得不恰當，善用排容原理的組合計算，類似 N 不排 N 的組合數 (錯排)。map 查找會慢很多，就算用分堆的 map 效率仍然提升不高，那麼直接開一個陣列空間 $O(37^4) = O(1874161)$，所有字串轉數字，雖然清空會慢很多，但是查找速度夠快。

感謝蚯蚓、卡車告知這問題。

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 <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
inline int toIndex(int x) { // [0...36]
    if ('0' <= x && x <= '9')
        return x - '0';
    if ('A' <= x && x <= 'Z')
        return x + 10 - 'A';
    return 36;
}
const int MOD = 1874161; // 37^4
int FUZZY[MOD];
int main() {
    int C[16][16] = {};
    for (int i = 0; i < 16; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    
    int testcase, n, m;	
    
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < MOD; i++)
            FUZZY[i] = 0;
        int ret = 0;
        int same = 4 - m, diff = m;
        char s[8];
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) >= same) {
                    int s1 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1 = s1 * 37 + toIndex(s[k]);
                        else 
                            s1 = s1 * 37 + toIndex('_');
                    }
                    int &r = FUZZY[s1];
                    int v = __builtin_popcount(j);
                    if ((v - same)%2 == 0)
                        ret += r * C[v][same];
                    else
                        ret -= r * C[v][same];
                    r++;
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Problem J

考了一題 BWT 壓縮的逆轉換，從簡單的思路至少要 $O(N^2 log N)$ 吧？沒想到的是利用特性可以達到 $O(N)$。這裡需要研究一下 為什麼相同字母順序在壓縮和解壓縮會相同 ，百思不解的就是這個地方，若是能解決，就直接利用輔助數組達到 $O(N)$ 逆推上一個元素是什麼，最後輸出一個反向的結果。

這裡解釋一下順序性問題

1
2
3
4
5
6
BANANA          ABANAN            (1)A----N(9)
ANANAB    sort  ANABAN   view A   (2)A----N(10)
NANABA  ------> ANANAB  --------> (3)A----B(12)
ANABAN          BANANA           (11)B----A(4)
NABANA          NABANA            (7)NAB--A(5)
ABANAN          NANABA            (8)NAN--A(6)

明顯地左側的 A 順序會跟右側的 A 順序相同，原因是 B----A < NAB--A < NAN--A，那麼保證 AB----, ANAB--, ANAN-- 一定也會出現 (根據 $O(N^2 log N)$ 的做法得到，因為他們是循環的！)，既然後綴順序已經排序 (B----A, NAB--A, NAN--A)，那麼右側中，相同的字母順序，肯定跟左側一樣 (由小到大)。

藉此可以推導下一個字母到底是何物！例如結尾字母是 A(4)，那麼前一個一定是 B(11)，而 B(11) 對應右側的 B(12)，B(12) 的前一個是 A(3)，A(3) 對應右側 A(6) …

1
2
3
R:      B(11)    A(3)     N(8)   A(2)    N(7)   A(1)   <---- inverse result
       /  \    /    \    /  \   /   \   /   \   /
L:  A(4)  B(12)      A(6)   N(10)   A(5)     N(9)

Version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
// O(n), BWT compress inverse
const int MAXN = 2048;
char s[MAXN];
int K[MAXN], M[MAXN], C[MAXN], N;
int main() {
    int testcase, e_pos;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s %d", s, &e_pos), e_pos--;
        
        string L(s), F(s);
        N = L.length();
        
        memset(K, 0, sizeof(K));
        memset(M, 0, sizeof(M));
        memset(C, 0, sizeof(C));
        
        for (int i = 0; i < N; i++) {
            C[i] = K[L[i]];
            K[L[i]]++;
        }
        
        sort(F.begin(), F.end());
        for (int i = 0; i < N; i++) {
            if (i == 0 || F[i] != F[i-1])
                M[F[i]] = i;
        }
        
        string T(N, '?');
        for (int i = 0; i < N; i++) {
            T[N-1-i] = L[e_pos];
            e_pos = C[e_pos] + M[L[e_pos]];
        }
        puts(T.c_str());
    }
    return 0;
}
/*
2
CGA
3
NNBAAA
4 
*/

Version 2

蚯蚓的寫法順推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
static const int MXN = 514514;
int main() {
    int t;
    std::cin >> t;
    
    while (t--) {	
        int p;
        std::string str;
        std::cin >> str >> p;
        
        std::vector<std::pair<char, int>> vec;
        for (size_t i = 0; i < str.length(); i++)
            vec.push_back(std::make_pair(str[i], i));
        std::sort(vec.begin(), vec.end());
        
        std::string ans;
        for (int i = p - 1; ans.length() < str.length(); i = vec[i].second)
            ans += vec[i].first;
        std::cout << ans << std::endl;
    }
}

Problem K

二分答案 + 掃描線，來找到是否矩形并的面積等於所求的整個面積。算法的複雜度是 $O(N \log^2{N} )$，如果太慢的話就懇求各位幫忙。

掃描線部分，將每個平行兩軸的矩形保留垂直的邊，水平的邊不影響運算結果。接著按照 X 軸方向由左往右掃描，將矩形左側的垂直邊當作入邊 +1、右側的垂直邊當作出邊 -1，維護 Y 值的區間覆蓋。

假設 Y 可能是實數，需要針對 Y 進行離散化處理，接著懶操作標記，對於線段樹的某個區間，若覆蓋數 cover = 0 則表示該區間無法提供，相反地提供整個區間。

註記 邪惡的 $\text{round}(\sqrt{k} \times c)$ ，不小心看成 $\text{round}(\sqrt{k}) \times c$

感謝蚯蚓告知這問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <stdio.h> 
#include <string.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
class SegmentTree {
public:
    struct Node {
        int cover;				// #cover
        int L, R;			// value in real line, cover [L, R]
        int clen;			// cover length
        void init(int a = 0, int b = 0, int c = 0, int d = 0) {
            cover = a, L = b, R = c, clen = d;
        }
    } nodes[MAXN];
    int Y[MAXN];
    void pushDown(int k, int l, int r) {
    }
    void pushUp(int k, int l, int r) {
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void build(int k, int l, int r) { 
        nodes[k].init(0, Y[l], Y[r+1], 0);
        if (l == r)
            return ;
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k, l, r);
    } 
    // operator, add
    void addUpdate(int k, int l, int r, int val) {
        nodes[k].cover += val;
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void add(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            addUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            add(k<<1, l, mid, x, y, val);
        if (y > mid)
            add(k<<1|1, mid+1, r, x, y, val);
        pushUp(k, l, r);
    }
    // query 
    long long r_sum;
    void qinit() {
        r_sum = 0;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_sum += nodes[k].clen;
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
        pushUp(k, l, r);
    }
} tree;
struct Event {
    long long x, yl, yr;
    int val;
    Event(long long a = 0, long long b = 0, long long c = 0, int d = 0):
    x(a), yl(b), yr(c), val(d) {}
    bool operator<(const Event &a) const {
        return x < a.x;
    }
};
const int MAXD = 32767;
int Lx[MAXD], Ly[MAXD], Rx[MAXD], Ry[MAXD];
long long X[MAXD], Y[MAXD];
double K[MAXD];
long long areaCoverAll(int N, int Lx[], int Ly[], int Rx[], int Ry[]) {
    vector<Event> events;
    vector<int> VY;
    map<int, int> RY;
    for (int i = 0; i < N; i++) {
        int x1, x2, y1, y2;
        x1 = Lx[i], x2 = Rx[i];
        y1 = Ly[i], y2 = Ry[i];
        if (x1 < x2 && y1 < y2) {
            events.push_back(Event(x1, y1, y2,  1));
            events.push_back(Event(x2, y1, y2, -1));
            VY.push_back(y1), VY.push_back(y2);
        }
    }
    
    sort(VY.begin(), VY.end());	
    VY.resize(unique(VY.begin(), VY.end()) - VY.begin());
    
    for (int i = 0; i < VY.size(); i++) {
        tree.Y[i] = VY[i];
        RY[VY[i]] = i;
    }
                
    if (VY.size() < 2)	
        return 0;
    tree.build(1, 0, VY.size()-2);
    
    sort(events.begin(), events.end());
    long long area = 0, prevX = 0;
    for (int i = 0, j; i < events.size(); ) {		
        if (i > 0) {
            tree.qinit();
            tree.query(1, 0, VY.size()-2, 0, VY.size()-2);
            area += (events[i].x - prevX) * tree.r_sum;
        }
        j = i;
        while (j < events.size() && events[j].x <= events[i].x) {
            tree.add(1, 0, VY.size()-2, RY[events[j].yl], RY[events[j].yr] - 1, events[j].val);
            j++;
        }
        prevX = events[i].x;
        i = j;
    }
    return area;
}
int main() {
    int testcase, cases = 0;
    long long W, H;
    int N;
    double sqrtK[128];
    for (int i = 0; i < 128; i++)
        sqrtK[i] = sqrt(i);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld", &W, &H);
        scanf("%d", &N);
                
        for (int i = 0; i < N; i++) {
            int x, y, k;
            scanf("%d %d %d", &k, &x, &y);
            if (k < 1 || k > 100)
                return 0;
            X[i] = x, Y[i] = y, K[i] = sqrtK[k];
        }
                
        if (N < 1 || N > 20000 || W <= 0 || H <= 0 || W > 1e+7 || H > 1e+7)
            return 0;
            
        double l = 0.4, r = max(W, H), mid;
        int ret = -1;
        while (fabs(l - r) > 0.1) {
            mid = (l + r)/2;
            
            for (int i = 0; i < N; i++) {
                Lx[i] = min(max(round(X[i] - K[i] * mid), 0.0), (double) W);
                Rx[i] = min(max(round(X[i] + K[i] * mid), 0.0), (double) W);
                Ly[i] = min(max(round(Y[i] - K[i] * mid), 0.0), (double) H);
                Ry[i] = min(max(round(Y[i] + K[i] * mid), 0.0), (double) H);
            }
            
            long long area = areaCoverAll(N, Lx, Ly, Rx, Ry);
            if (area == W*H)
                r = mid, ret = ceil(mid*2);
            else
                l = mid;
        }
        
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
9999
9 9
1
1 0 0
1 1
1
4 0 0
2
12 8
3
4 2 2
16 8 4
4 2 6
12 8
3
4 2 2
10 8 4
4 2 6 
*/

後記

如有錯誤，多多包涵。

Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 F - No challenge No life

Problem

這次要挑戰的題目為 UVa 12647 - Balloon，由於網路上有一些線段樹的作法，如

http://www.cnblogs.com/yours1103/p/3426212.html

這裡可以看到有一些人利用線段樹來完成操作，實際上的做法根據掃描線，y 座標從高度低到高、或者是高到低的線段依序放入，到時候查找第一個獲最後一個覆蓋的線段編號。

UVa 12647 - Balloon 主要是在問，給予一些天花板，請問放置一個氣球，氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止)，詢問最後停留的位置。有可能會飛到無窮遠，則輸出最後的 x 座標，反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板，發生擦邊情況，則氣球會依據第一個碰觸到的天花板進行移動。

Solution

既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式，找到覆蓋編號去完成移動、建造飛行的所有可能。

明顯地，由於天花板線段的斜率有正有負，不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段，讓覆蓋方案失效。

下面有數組測資，可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好，那用最大最小值去維護如何！這樣也許就好點了吧？但不幸地，這麼做一樣會遇到排序 y 的問題，不管怎麼排序，都會造成建構方法不正確。

challenge 的題目還不太會傳，中間有點小問題。

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
#include <stdio.h> 
int main() {
//	puts("4 1");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("4");
    puts("3 3");
    puts("5 5 10 4");
    puts("2 2 6 4");
    puts("0 3 4 4");
    puts("0");
    puts("1");
    puts("2");
//	puts("7 4");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("25 5 30 4");
//	puts("22 2 26 4");
//	puts("20 3 24 4");
//	puts("4");
//	puts("20");
//	puts("21");
//	puts("22");
    return 0;
}
/*
3 3
5 5 10 4
2 2 6 4
0 3 4 4
0
1 
2
4 1
3 1 12 4
5 2 2 3
1 4 4 4
7 5 14 5
4
4 1
3 1 12 4
5 2 2 3
1 4 4 3
7 5 14 5
4
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 G - Strange Permutations

Problem

排列 1 到 n 的整數，使得相鄰兩數互質，部分位置一定要填入某些數字，請問剩餘數字的填法方案數為何？

Sample Input

1
2
3
1
8
1 2 0 0 0 0 7 8

Sample Output

1
2

Solution

bitmask 下去 dp[N][1<<N][N]，dp[i][j][k] 表示前 i 個位置，已經使用的數字狀態 j，最後一個數字 k。不曉得需不需要滾動，記憶體用量驚人。萬萬沒想到，撰寫過程中坑了一個建表的 gcd[20][20]，當 n = 20 時，直接 index out of bound，先撇開這個蠢錯。滾動數組下去玩，真是誘人的時間限制，再次得到 9.990s TLE 的事蹟 ！仔細想想，運算過程中只出現加法，將 mod 運算替換成條件判斷 + 減法，

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 <string.h>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 20;
int dp[2][1<<MAXN][MAXN], used[2][1<<MAXN][MAXN], ucases = 0;
int g[MAXN+20][MAXN+20];
int vaild(int i, int a, int b) { // a contract b
    if (i == 0)	return 1;
    return g[a+1][b+1];
}
int main() {
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++)
            g[i][j] = __gcd(i, j) == 1;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int cant = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if (A[i])
            	cant |= 1<<(A[i]-1);
        }
        
        int flag = 0;
        int mask = (1<<n)-1;
        int ret = 0;
//        memset(dp, 0, sizeof(dp));
        ucases++;
        used[flag][0][0] = ucases;
        dp[flag][0][0] = 1;
        for (int i = 0; i < n; i++) {
            int p = flag, q = !flag;
            flag = 1 - flag;
            ucases++;
//            for (int j = mask; j >= 0; j--)
//            	for (int k = 0; k < n; k++)
//            		dp[q][j][k] = 0;
            for (int j = (1<<n)-1; j >= 0; j--) {
            	for (int k = 0; k < n; k++) {
            		if (used[p][j][k] != ucases-1)
            			continue;
            		int ways = dp[p][j][k];
            		if (ways == 0)
            			continue;
            		if (A[i] == 0) {
            			for (int p = 0; p < n; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
            				if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		} else {
            			for (int p = A[i]-1; p <= A[i]-1; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
                            if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		}
            	}
            }
        }
        
        for (int i = 0; i < n; i++) {
        	if (used[flag][(1<<n)-1][i] != ucases)
        		continue;
        	ret += dp[flag][(1<<n)-1][i];
        	ret %= MOD;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
10
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4
0 2 4 0
8
1 3 5 0 0 0 0 0
8
1 2 0 0 0 0 7 8
8
1 0 5 8 0 0 0 0
8
0 2 0 7 0 0 0 8
8
0 2 0 0 0 0 0 8
8
0 2 0 0 0 0 0 0
8
0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0
1
0
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 E - Kirino in Google Code Jam

Problem

2015 Google Code Jam Round 1A 中，C - Logging 有點嚴重的問題！很多精準度不高的代碼都通過了！現在要求去找到測資 tricky cases，讓他們通通 WA！

原題是對於任意平面點，找到要移除最小的平面點，使得自己在凸包邊緣上。標準的極角排序，維護 180 度以內 (半平面) 的點個數。

atan2 esp = 1e-12 not enough for $x, y \in \left [0, 10^6 \right]$，極角排序替代方案！快來戳我的講法，看 POJ 類似的題目，精準度要壓到 1e-16 呢，所以誤差還要抓更小才行。

Solution

等等，challenge 這一題時，自己的代碼也 WA 了！

一開始誤以為是 index out of bound，assert() 下去都沒發生。後來估計是 atan2(y, x) 的誤差，對此誤差早有耳聞，解題撞壁的機會很低。咱很蠢，隨機生了 1000 萬個平面點，按照 atan2 排序，檢查相鄰兩個座標的外積 (叉積) 是否為逆時針，跑一次隨機生成大概能爆出一個誤差的相鄰點，十來次得到 n 個點，隨機組合這 n 個點於四個象限，再亂撒少數個點，再跟自己撰寫的代碼做比對 (中間又測了上萬組)。

atan2 誤差測試

atan2_eps_test
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}	
double distSeg2Point(Pt a, Pt b, Pt p) {
    Pt c, vab;
    vab = a - b;
    if (between(a, b, p)) {
        c = getIntersect(Seg(a, b), Seg(p, Pt(p.x+vab.y, p.y-vab.x)));
        return (p - c).length();
    }
    return min((p - a).length(), (p - b).length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int 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;
}
const double pi = acos(-1);
int main() {
    srand ( time(NULL));
    
    vector< pair<double, Pt> > V;
    for (int i = 0; i < 10000000; i++) {
        int X, Y;
        X = (rand()*rand())%2000000 - 1000000;
        Y = (rand()*rand())%2000000 - 1000000;
        V.push_back(make_pair(atan2(Y, X), Pt(X, Y)));
    }
    sort(V.begin(), V.end());
    for (int i = 0; i+1 < V.size(); i++) {
        if (cross2(V[i].second, V[i+1].second) != 0 && fabs(V[i].first - V[i+1].first) < 1e-12)
            printf("%.0lf %.0lf %.0lf %.0lf\n", V[i].second.x, V[i].second.y, V[i+1].second.x, V[i+1].second.y);
    }
//	long long a = 599430;
//	long long b = 1428722;
//	long long c = 648824;
//	long long d = 1546451;
//	long long a = 885828;
//	long long b = 737167;
//	long long c = 898961;
//	long long d = 748096;
//
//	printf("%lld\n", a * d - b * c);
//	printf("%lf %lf, %d\n", atan2(b, a), atan2(d, c), fabs(atan2(b, a) - atan2(d, c)) < 1e-12);
    return 0;
}
/*
885828 737167 898961 748096
854425 732894 706721 606199
-971645 988877 -838743 853618
993753 -652232 991850 -650983
620105 659001 916399 973880
*/

誤差數據產生

testdata
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <set>
#include <algorithm>
using namespace std;
double random() {
    int r = rand();
    return (double) r / RAND_MAX;
}
int vvv[20] = {885828, 737167, 898961, 748096,
854425, 732894, 706721, 606199,
-971645, 988877, -838743, 853618,
993753, -652232, 991850, -650983,
620105, 659001, 916399, 973880};
main() {
    int n, m, t, a, b, c, tmp;
    int z, i, j, k, l, p, q;
    srand ( time(NULL));
    freopen("in.txt", "w+t", stdout);
    
    int T = 10000;
    printf("%d\n", T);
    while(T--) {
        int n = 30, m = rand()%n + 1;
        printf("%d\n", n);
        set< pair<int, int> > S;
        S.insert(make_pair(0, 0));
        printf("%d %d\n", 0, 0);
        for (int i = 1; i < n; i++) {
            int x, y;
            do {
                if (rand()%10 < 8) {
                    x = vvv[rand()%20], y = vvv[rand()%20];
                    if (rand()%2)	x = -x;
                    if (rand()%2)	y = -y;
                } else {
                    x = rand()%100 - 50, y = rand()%100 - 50;
                }
            } while (S.count(make_pair(x, y)));
            S.insert(make_pair(x, y));
            printf("%d %d\n", x, y);
        }		
    }
    
    return 0;
}

對照組

利用外積的計算方案，誤差情況會更小。又因為是整數座標，基本上是不產誤差。

fixed-bug-Problem-C-Logging
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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    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 (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
    int N, testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        printf("Case #%d:\n", ++cases);
        
        if (N == 1) {
            puts("0");
            continue;
        }
        
        for (int i = 0; i < N; i++) {
            vector< Pt > A;
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                Pt p = D[j] - D[i];
                A.push_back(p);
            }
            sort(A.begin(), A.end(), cmp);
            int M = (int)A.size();
            int l = 0, r = 0, cnt = 1;
            int ret = 0;
            for (l = 0; l < M; l++) {
                if (l == r)
                    r = (r+1)%M, cnt++;
                while (l != r && cross2(A[l], A[r]) >= 0) {
                    r = (r+1)%M, cnt++;
                }
                ret = max(ret, cnt);
                cnt--;
            }
            printf("%d\n", N - ret);
        }
    }
    return 0;
}

Final

生了 10000 組，終於在裡面發現其中幾組。

final
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 <stdio.h>
int main() {
    puts("1\n30\n0 0\n-971645 838743\n748096 -988877\n-652232 -993753\n737167 -838743\n-48 27\n706721 -885828\n606199 854425\n659001 -993753\n898961 885828\n-659001 885828\n748096 -973880\n21 -13\n-748096 606199\n-732894 991850\n13 -12\n659001 -737167\n-32 -32\n737167 -748096\n650983 -971645\n650983 -732894\n854425 -606199\n-606199 885828\n916399 -988877\n652232 -838743\n-606199 988877\n-620105 -652232\n-748096 -737167\n24 -23\n916399 854425\n");
    return 0;
}
/*
1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 D - A Parking Problem

Problem

停車場有 n 個位置呈現單方向，由入口到出口分別編號為 1 到 n，現在有 m 名駕駛準備要停車，每名駕駛的停車方案都會先開到偏愛的車位上，如果發現已經有人停過，則會往後找一個空車位。由於駕駛入停車場任意順序。請問從 m 個駕駛中挑出 n 個駕駛，任意進入停車場，按照他們各自偏愛的停車方法，每一位都有停車位的合法選擇駕駛的方案數。

Sample Input

1
2
3
1
3
2 1 2

Sample Output

1
7

Solution

維護前 i 個位置中，挑選 j 名駕駛的方法數！dp[i][j] 表示前 i 個位置，挑選 j 個駕駛的方法數，並且滿足 j >= i，否則會有留空一格造成後續的非法解。窮舉下一個位置挑選的人數 k，得到 dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;

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 <stdio.h>
const int MOD = 1000000007;
const int MAXN = 64;
long long C[MAXN][MAXN] = {};
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        long long dp[MAXN][MAXN] = {};
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 0; k <= A[i+1] && j+k <= n; k++) {
                    dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;
                    dp[i+1][j+k] %= MOD;
                }
            }
        }
        printf("%lld\n", dp[n][n]);
    }
    return 0;
}
/*
 1
 3
 2 1 2
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 B - Dreamoon's Criterion

Problem

夢月解題目會根據夢月法則？如果題目需要花費大於等於 t 的時間，則定義題目難度為 hard，反之為 easy。小番茄 (求解釋) 準備 n 個題目請求夢月協助，但隨著每解一題，下一題的難度會隨著疲累值增加，疲累值為一個等差為 k 個數列。只打算解決 easy 的題目，請問在相同的 k 下，不同的 t 分別能解決的最多題數。

Sample Input

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

Sample Output

1
2
4
0

Solution

t 越大，能解的題目肯定越多！難度越低的題目一定會選，因此前 i 小難度的題目都會被挑。利用類似求方程式值的方式 (隨便講講，別太在意 f(x) = a0 + a1x + a2x^2 + a3x^3 … + anx^n，可以在 O(n) 完成的方法) 下去猜測？維護已選題目如果增加 k 不大於 t 且下一個題目難度也小於 t，則所有已選難度都增加 k！離線處理，將詢問的 t 由小到大排序，掃描過去？

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
int A[MAXN], Qt[MAXN], out[MAXN];
int main() {
    int testcase;
    int N, K, Q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++)
            scanf("%d", &Qt[i]);
        
        vector< pair<int, int> > QV;
        for (int i = 0; i < Q; i++)
            QV.push_back(make_pair(Qt[i], i));
        
        sort(QV.begin(), QV.end());
        sort(A, A+N);
        
        int idx = -1, sum = 0, t, mx = -0x3f3f3f3f;
        for (int i = 0; i < Q; i++) {
            t = QV[i].first;
            while (idx+1 < N && mx + K <= t && A[idx+1] <= t) {
                idx++, sum++;
                mx = max(mx+K, A[idx]);
            }
            out[QV[i].second] = sum;
        }
        
        for (int i = 0; i < Q; i++)
            printf("%d\n", out[i]);
    }
    return 0;
}
/*
 1
 5 2
 7 3 6 8 5
 2
 9
 1
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 A - Attack and Split

Problem

有一隻史萊姆可以進行分裂和合併，大小為 x 的史萊姆可以分裂成兩個小史萊姆 y 和 z，滿足 x = y + z。當兩個史萊姆大小 p, q 合併時，新的史萊姆為 r = p xor q。請問是否存在數次的分裂和合併，所有史萊姆都消失！

Sample Input

1
2
3
4
3
1 1
2 9 17
3 12 15 19

Sample Output

1
2
3
No
Yes
Yes

Solution

亂來的奇偶和判定！以下是不負責任的說法！對於一種合法解 {a1, a2}，則 {a1-1, 1, a2-1, 1} 也一定會合法，不斷地拆分下去，所有史萊姆的大小都是 1，也發現到總和一定是偶數。因此只要判斷總和的奇偶數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        long long x, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            sum += x;
        }
        puts(sum%2 ? "No" : "Yes");
    }
    return 0;
}
/*
 3
 1 1
 2 9 17
 3 12 15 19
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 Warmup C - Exploding CPU 2

Problem

詢問一個區間有多少 鄒賽爾數 (Zeisel number)

鄒賽爾數是一種無平方數因數的數，而且至少有三個質因數可以用下式表示，質因數由小排到大滿足$p_{x} = A p_{x-1} + B$。

105, 1419, 1729, 1885, 4505, 5719, 15387, 24211, 25085, …

1
2
3
4
5
6
7
4505 = 1 * 5 * 17 * 53
A = 3, B = 2
p0 = 1
p1 = 3 * p0 + 2 = 5
p2 = 3 * p1 + 2 = 17
p3 = 3 * p2 + 2 = 53

找到 $10^{15}$ 以內的所有 Zeisel number。

Sample Input

1
2
3
2
4505 4505
0 5000

Sample Output

1
2
1
5

Solution

一開始設想，既然小於 $10^{15}$ 又要三個質數，那麼最小的質因數應該要小於 $10^5$，否則會超過指定範圍。

接著第一次嘗試時，窮舉變數 $A$ 針對第一個質因數$p_{1}$ 得到$B = p_{1} - A$，得到下一項在範圍內 … 這樣效率非常差。A 的範圍非常大，質因數也非常多，而且還要檢驗每一項是否質數，效能相當低落。

接著第二次嘗試時，窮舉$p_{1}, p_{2}$，這樣的計算量是 $10^5$ 內的質數個數 n，至少為 $O(n^2)$，嘗試一下發現速度還是太慢，藉由聯立方程式解出 A, B，卻有不少 A 是不存在的整數解。

1
2
3
A + B = p1
p1 A + B = p2
A = (p2 - p1)/(p1 - 1), B = p1 - A

接著第三次嘗試時，反過來窮舉，先讓 $A$ 一定有解，再看$p_{2}$ 是否為質數，因此$p_2 = p_1 + k \times (p_1 - 1)$，由於$p_{i} - 1$ 造成的增長幅度遠比質數個數快很多，效能上有顯著地提升。

現在還有一個疑問，保證$p_1 \le 10^5$，但是當$p_1$ 很小$p_2$ 可能會大於 $10^5$ 嗎，甚至必須窮舉到 $\sqrt{10^{15}}$？

這裡我不確定，放大範圍去嘗試時，發現找到的 Zeisel number 最多 9607 個，放大搜索範圍不再增加，那就不斷地縮減，讓找到的時間縮小不逾時。

1.980s TLE

不是說好限制 2.000s？1.980s 得到 TLE，第一次使用 NTUJ 真歡樂。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXL (10000000>>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[5500000], Pt = 0;
vector<long long> ret;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long MAXVAL = 1e+15;
int isprime(long long v) {
    if (v < 2)	
        return 0;
    if (v < 10000000)
        return !GET(v);
    for (int i = 0; i < Pt && (long long) P[i] * P[i] <= v; i++)
        if (v%P[i] == 0)
            return 0;
    return 1;
}
void make() {
    for (int i = 0; i < Pt && P[i] < 100000; i++) {
        for (int j = P[i] + P[i]-1; j < 1000000; j += P[i] - 1) {
            if (!isprime(j))
                continue;
            long long A = (j - P[i])/(P[i]-1);
            long long B = P[i] - A;
            long long m = P[i], cnt = 1, mm = P[i];
            while (mm <= MAXVAL) {
                if (A && MAXVAL / m / A <= 0)
                    break;
                if (m * A + B <= m)
                    break;
                m = m * A + B;
                if (MAXVAL / mm / m <= 0)
                    break;
                if (!isprime(m))
                    break;
//				printf("%lld ", m);
                mm = mm * m, cnt ++;
                if (cnt >= 3) {
                    ret.push_back(mm);
//					printf("%lld %lld %lld\n", mm, A, B);
                }
            }
        }
    }
    sort(ret.begin(), ret.end());
    for (int i = 0; i < 243; i++)
        printf("%d\n", ret[i]);
//	printf("%d\n", ret.size());
}
int main() {
    sieve();
    make();
    int testcase;
    long long L, R;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld", &L, &R);
        int r = 0;
        for (int i = 0; i < ret.size(); i++)
            r += ret[i] >= L && ret[i] <= R;
        printf("%d\n", r);
    }
    return 0;
}
/*
2
4505 4505
0 5000
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 Warmup B - The Brush

Problem

給一個 $N \times N$ 的棋盤，放置城堡 (rook)，城堡只能攻擊同行同列，這裡更特別一些，只能攻擊右下角位置。

下方是一個 $5 \times 5$ 範例，其中 R 表示城堡的位置，* 表示城堡可攻擊的格子，也就是範例的第三組測資。

1
2
3
4
5
6
7
8
9
10
11
12
+-+-+-+-+-+
| | | | |R| 1
+-+-+-+-+-+ 
| | |R|*|*| 2
+-+-+-+-+-+
| |R|*|*|*| 3
+-+-+-+-+-+
|R|*|*|*|*| 4
+-+-+-+-+-+
|*|*|*|R|*| 5
+-+-+-+-+-+
 1 2 3 4 5

保證輸入中城堡不會出現在同行同列，請問可攻擊的格子有多少個 (意即計算 * 的數量)。

Sample Input

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

Sample Output

1
2
3
6
10
13

Solution

很明顯地發現，答案是 所有城堡可攻擊數量總和 扣除 交集點數量 ，兩兩城堡最多一個交集點，並且交集點不會重疊 (不同行列的關係)，而交集點只發生在逆序對中。因此找到逆序對總數，可以利用 D&C 的 merge sort 算法，或者套用 Binary indexed tree，利用掃描線思路找到逆序對。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, A[131072];
int BIT[131072];
void modify(int x, int val) {
    while (x <= n) {
        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() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n); 
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        for (int i = 0; i <= n; i++)
            BIT[i] = 0;
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += n - A[i];
            ret += n - i - 1;
            ret -= i - query(A[i]-1);
            modify(A[i], 1);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
3
1 2 3
5
5 4 3 2 1
5
5 3 2 1 4
*/
Read More +