HKU Provincists 4th Training

Posted on 繁/简： set

题目来自 2023-2024 ICPC Brazil Subregional Programming Contest。link


  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!


Best Fair Shuffles

思维+猜结论题，这种题没想出来真没办法，就是菜。

在序列中寻找最长的形如 \(1,2,...,x_1\) 的子序列，再寻找形如 \(x_1+1,...,x_2\) 的子序列，再寻找 \(x_2+1,...,x_3\) 的子序列……若最终找到了 \(k\) 个这样的子序列，答案为 \(\log_2(k)\)。

比较 intuitive 的证明：一次 fair shuffle 至多会将这样的子序列数量翻倍，因此 \(m\) 次 fair shuffle 后得到的序列中最多将会有 \(2^m\) 个子序列。

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;

const int MAX_N = 1e6 + 10;

int n;
bool pos[MAX_N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int k = 0;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        pos[x] = true;
        if (!pos[x - 1])
            ++k;
    }

    cout << ceil(log2(k)) << endl;

    return 0;
}


Challenging Hike

树上最长上升子序列问题。由于要在树上回溯，需要撤销操作，解普通最长上升子序列的树状数组要改成支持单点修改区间维护的最大值线段树。顺便也复习了一下离散化。

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 10;

struct dp {
    int end;
    int val;

    bool operator < (const dp& p) const {
        if (end == p.end)   return val < p.val;
        return end < p.end;
    }
};

int n, m;
int v[MAX_N], ans[MAX_N];
int tmp[MAX_N];

int tree[MAX_N << 2];

vector<int> e[MAX_N];

void modify(int x, int l, int r, int pos, int val) {
    if (l == r) {
        tree[x] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        modify(x << 1, l, mid, pos, val);
    else
        modify(x << 1 | 1, mid + 1, r, pos, val);
    tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}

int query(int x, int l, int r, int ql, int qr) {
    if (ql > qr)
        return 0;
    if (ql <= l && r <= qr)
        return tree[x];
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid)
        res = max(res, query(x << 1, l, mid, ql, qr));
    if (qr > mid)
        res = max(res, query(x << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

void dfs(int u, int fa) {
    int shoot = query(1, 1, m, 1, v[u] - 1) + 1;
    ans[u] = max(ans[fa], shoot);

    int cur = query(1, 1, m, v[u], v[u]);
    int flag = 0;
    if (shoot > cur) {
        flag = 1;
        modify(1, 1, m, v[u], shoot);
    }

    for (auto to : e[u]) {
        if (to == fa)   continue;
        dfs(to, u);
    }

    if (flag)
        modify(1, 1, m, v[u], cur);
}

void discretize() {
    for (int i = 1; i <= n; ++i)    tmp[i] = v[i];
    sort(tmp + 1, tmp + n + 1);
    m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    for (int i = 1; i <= n; ++i)
        v[i] = lower_bound(tmp + 1, tmp + m + 1, v[i]) - tmp;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 2; i <= n; ++i) {
        int x;
        cin >> x;
        e[i].push_back(x);
        e[x].push_back(i);
    }

    for (int i = 1; i <= n; ++i)    cin >> v[i];
    
    discretize();

    dfs(1, 0);

    for (int i = 2; i <= n; ++i)    cout << ans[i] << " ";

    return 0;
}


Extracting Pollen

很喜欢这道题。\(K\leq 10^9\)，显然暴力模拟行不通。观察到 \(F_i\leq 10^6\)，于是考虑从权值入手来做。用桶来存花朵的权值并从后往前扫描模拟采蜜过程，当 \(k\) 小于当前花朵的数量时就能够确定答案了。

其实这个方法本质上与暴力模拟的思路是一致的；但是把重心放到值域上后再来设计模拟就能保证 \(O(F)\) 的效率，真的很巧。

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 <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1e6 + 10;

int cnt[MAX_N];

int calc(int x) {
    int res = 0;
    while (x) { 
        res += x % 10; 
        x /= 10; 
    }
    return res;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    int maxR = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
        maxR = max(maxR, x);
    }


    for (int i = maxR; i > 0; --i) {
        if (!cnt[i])    continue;
        if (k > cnt[i]) {
            k -= cnt[i];
            cnt[i - calc(i)] += cnt[i];
        } else {
            cout << calc(i) << endl;
            return 0;
        }
    }

    cout << 0 << endl;

    return 0;
}


Great Treaty of Byteland

可以发现答案就是凸包上的点。凸包上两个相邻王国的边界即为连接它们的凸包边线段的法线，该法线是朝无限远处延申的。队友留下这一句结论就匆匆离席，徒留我一人挣扎在凸包 debug 地狱。

再次感受到准备好板子的重要性。以下程序可以作为 Andrew 算法求凸包的模板。(一开始写的是 Graham 扫描算法，但因为极角排序造成的精度问题 WA 爆了，，，求凸包还是用 Andrew 算法好)

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 10;

struct Point {

    int id;
    int x, y;

    bool operator < (const Point& p) {
        if (x == p.x)   return y < p.y;
        return x < p.x;
    }

    Point operator - (const Point& p) const { 
        return {0, x - p.x, y - p.y};
    }

} p[MAX_N];

Point sta[MAX_N];
int top;

int cross(Point p1, Point p2) {
    return p1.x * p2.y - p1.y * p2.x; 
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }

    sort(p + 1, p + n + 1);

    for (int i = 1; i <= n; ++i) {
        while (top > 1 && cross(p[i] - sta[top - 1], sta[top] - sta[top - 1]) > 0) {
            --top;
        }
        sta[++top] = p[i];
    }    

    if (top < n) {
        int tmp = top;
        for (int i = n - 1; i > 0; --i) {
            while (top > tmp && cross(p[i] - sta[top - 1], sta[top] - sta[top - 1]) > 0) {
                --top;
            }
            sta[++top] = p[i];
        }
        if (n > 1) --top;
    }

    vector<int> ans;
    for (int i = 1; i <= top; ++i)  ans.push_back(sta[i].id);

    sort(ans.begin(), ans.end());

    for (auto i : ans)  cout << i << " ";
    cout << endl;

    return 0;
}


Investigating 0s and 1s

比较基础的 DP。朴素想法是 \(O(n^2)\) 的，将第二维状态按照奇偶压缩成 \(0/1\) 后就能得到 \(O(n)\) 的 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
#include <iostream>

using namespace std;

const int MAX_N = 1e5 + 10;

long long a[MAX_N][2];

int main() {

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        a[i][x] = 1;
        if (x) {
            a[i][0] += a[i - 1][1];
            a[i][1] += a[i - 1][0];
        } else {
            a[i][0] += a[i - 1][0];
            a[i][1] += a[i - 1][1];
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) 
        ans += a[i][1];
    
    cout << ans << endl;

    return 0;
}


Maximizing Flight Efficiency

很好想。若从 \(a\) 到 \(b\) 的直飞航班可以取消，那么一定存在一种转机方式的成本和直飞的价格一致。判断 coherent 与后续的直飞航班取消方案都可以用类似 Floyd 的方式解决。

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
#include <iostream>

using namespace std;

const int MAX_N = 110;

int c[MAX_N][MAX_N];

int main() {

    int n;

    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> c[i][j];
    
    bool hasAns = true;
    for (int i = 1; i <= n; ++i) {
        if (!hasAns)    break;
        for (int k = i + 1; k <= n; ++k) {
            if (!hasAns)    break;
            for (int j = 1; j <= n; ++j) {
                if (j == i || j == k)   continue;
                if (c[i][j] + c[j][k] < c[i][k]) {
                    hasAns = false;
                    break;
                }
            }
        }
    }

    if (!hasAns) {
        cout << -1 << endl;
    } else {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int k = i + 1; k <= n; ++k) {
                for (int j = 1; j <= n; ++j) {
                    if (j == i || j == k)   continue;
                    if (c[i][j] + c[j][k] == c[i][k]) {
                        ans++;
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}
-----------------------------------そして、次の曲が始まるのです。-----------------------------------