2024-12-21周赛 2024 Benelux Algorithm Programming Contest (BAPC 24)

题目链接#

2024 Benelux Algorithm Programming Contest (BAPC 24)

A. “Aaawww…” or “Aaayyy!!!”#

题意#

模拟滚榜的流程

题解#

注意每次过完一道题都应该更新榜单

代码#

1
struct team
2
{
3
    int id;
4
    string problems;
5
};
6

7
void idol_produce(int testCase) {
8
    /*Code Here*/
9
    int n, m, p;
10
    cin >> n >> m >> p;
11
    vector<team> teams(n + 1);
12
    int sum = 0;
13
    for(int i = 1;i <= n; i++){
14
        cin >> teams[i].problems;
15
        teams[i].id = i;
16
        sum += count(teams[i].problems.begin(), teams[i].problems.end(), 'P');
17
    }
18
    int id = n;
19
    for(int i = 1;i <= sum; i++){
20
        string s;
21
        cin >> s >> s;
22
        while(teams[id].problems.find('P') == string::npos) id--;
23
        if (s == "Aaawww..."){
24
            for(auto &c : teams[id].problems){
25
                if(c == 'P'){
26
                    c = 'R';
27
                    break;
28
                }
29
            }
30
        }
31
        else{
32
            s.pop_back();
33
            s.pop_back();
34
            s.pop_back();
35
            s = s.substr(6);
36
            int up = s.size();
37
            for (auto &c : teams[id].problems) {
38
                if (c == 'P') {
39
                    c = 'A';
40
                    break;
41
                }
42
            }
43
            for(int i = id - 1; i >= id - up; i --){
44
                swap(teams[i], teams[i + 1]);
45
            }
46
        }
47
    }
48
    for(int i = 1;i <= n; i++){
49
        if(teams[i].id == p){
50
            cout << i << '\n';
51
            return;
52
        }
53
    }
54
}

J. Jumbled Scoreboards #

题意#

判断给定的对是否形成不降序

题解#

按题意模拟即可

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<pair<int, int> > a(n + 1);
6
    for (int i = 1; i <= n; i++) {
7
        cin >> a[i].first >> a[i].second;
8
    }
9
    for (int i = 2; i <= n; i++) {
10
        if (a[i].second < a[i - 1].second || a[i].first < a[i - 1].first) {
11
            cout << "no\n";
12
            return;
13
        }
14
    }
15
    cout << "yes\n";
16
}

G. Grocery Greed #

题意#

给定 $n$ 个价格的物品，可以选择现金或刷卡支付，若选择现金支付价格将四舍五入最接近的 $0.05$ ，你可以将多个物品分为一组进行支付，使总价格最小

题解#

将所有价格单位转化成美分，并对 $5$ 美分取模，这样就得到模数为 $0 - 4$ 美分的各个物品的价格

对于所有的 $1$ 和 $2$ 美分的价格直接向下取整
对于每一对 $3$ 和 $4$ 美分的价格分为一组得到 $2$ 美分后向下取整
若剩余 $3$ ，则将每一对 $3$ 分为一组得到 $1$ 后向下取整
若剩余 $4$ ，则将每三个 $4$ 分为一组得到 $2$ 后向下取整
剩余的价格直接加入答案

为什么要先把 $3$ 和 $4$ 组成一对，再处理剩余的？

令 $f$ 表示将一些价格分为一组可以省下来的美分

f(3,4) = 2\\ f(3 * 2) = 1\\ f(4 * 3) = 2\\ f(3 * 2, 4 * 2) = f(3 * 2) + f(4 * 3) = 4\\ f(3 * 3, 4 * 3) = f(3 * 4) + f(4 * 3) = 4

显然对于省下同样的美分，将 $3$ 和 $4$ 组合起来一定比单独分组更优

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<int> a(5);
6
    int ans = 0;
7
    for (int i = 1; i <= n; i++) {
8
        double x;
9
        cin >> x;
10
        // use round() not (int)()
11
        int p = round(x * 100);
12
        a[p % 5]++;
13
        ans += p;
14
    }
15
    ans -= a[1];
16
    ans -= a[2] * 2;
17
    ans -= min(a[3], a[4]) * 2;
18
    int tmp = min(a[3], a[4]);
19
    a[3] -= tmp;
20
    a[4] -= tmp;
21
    ans -= a[3] / 2;
22
    ans -= a[4] / 3 * 2;
23
    cout << fixed << setprecision(2) << ans / 100.00 << '\n';
24
}

E. Extraterrestrial Exploration #

题意#

给定一个长度为 $n$ 的不递减的未知数列 $o$ ，每一次询问 $i$ 可以得到 $o_i$ 的值，在 $50$ 次询问内，得到一个三元组 $(x, y, z)(1 \leq x,y,z \leq n, x \neq y, x \neq z, y \neq z)$ 使得 $\sqrt{|{o_x - o_y}|} + \sqrt{|{o_x - o_z}|} + \sqrt{|{o_y - o_z}|}$ 最大

题解#

设 $x < y < z$ ，显然 $x = 1, z = n$ 必然最优，即：

\sqrt{|{o_y - o_1}|} + \sqrt{|{o_n - o_y}|} + \sqrt{|{o_1 - o_n}|}

我们只需要确定 $y$ 的值即可，该函数求导后为一个凸函数，在 $o_y = \frac{1}{2} (o_1 + o_n)$ 最大，二分找到原数列最接近的值即可

1
int ask(int x) {
2
    cout << "? " << x << endl;
3
    int res;
4
    cin >> res;
5
    return res;
6
}
7

8
void answer(int x, int y, int z) {
9
    cout << "! " << x << " " << y << " " << z << endl;
10
    return;
11
}
12
void idol_produce(int testCase) {
13
    /*Code Here*/
14
    int n;
15
    cin >> n;
16
    int target = ask(1) + ask(n);
17
    int ans = -1;
18
    int res = INF;
19
    int l = 2, r = n - 1;
20
    while(l <= r){
21
        int mid = (l + r) >> 1;
22
        int tmp = ask(mid);
23
        if(abs(tmp * 2 - target) < res){
24
            ans = mid;
25
            res = abs(tmp * 2 - target);
26
        }
27
        if(tmp * 2 == target){
28
            break;
29
        }
30
        if(tmp * 2 < target){
31
            l = mid + 1;
32
        }else{
33
            r = mid - 1;
34
        }
35
    }
36
    answer(1, ans, n);
37
}

I. Interrail Pass #

题意#

计划完成 $n$ 天的旅行，票价分为单程票和通行证

$n$ 张单程票，第 $i$ 张单程票表示第 $t_i$ 天旅行票价为 $f_i$

$k$ 张通行证，第 $i$ 张通行证表示购买价格为 $c_i$ 的通行证后，接下来的 $p$ 天内（包含当天），前 $d$ 次旅行免费

求完成 $n$ 天旅行的最少花费的价格

题解#

令 $pre(t)$ 表示第 $t$ 天之前的最新的旅行日的索引，即 $max(i|t_i \leq t)$ ，这个可以预处理

令 $dp_i$ 表示前 $i$ 次旅行最少花费的价格

那么得到转移方程:

dp_i = \min \begin{cases} f_i + dp_{i-1}\\ \min\limits_{1 \leq j \leq k}\{c_j + dp_{\max(i-d_j, pre(t_i-p_j))}\} \end{cases}

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, k;
4
    cin >> n >> k;
5
    vector<int> t(n + 1), f(n + 1);
6
    for (int i = 1; i <= n; i++) {
7
        cin >> t[i] >> f[i];
8
    }
9
    vector<int> pre((int)1e6 + 5);
10
    int id = 0;
11
    for (int i = 0; i <= 1e6; i++) {
12
        while (id < n && t[id + 1] <= i) {
13
            id++;
14
        }
15
        pre[i] = id;
16
    }
17
    vector<int> p(k + 1), d(k + 1), c(k + 1);
18
    for (int i = 1; i <= k; i++) {
19
        cin >> p[i] >> d[i] >> c[i];
20
    }
21
    auto get_pre = [&](int x) {
22
        if (x < 0) return 0;
23
        return pre[x];
24
    };
25
    vector<int> dp(n + 1);
26
    for (int i = 1; i <= n; i++) {
27
        dp[i] = dp[i - 1] + f[i];
28
        for (int j = 1; j <= k; j++) {
29
            dp[i] = min(c[j] + dp[max(i - d[j], get_pre(t[i] - p[j]))], dp[i]);
30
        }
31
    }
32
    cout << dp[n] << '\n';
33
}

F. Failing Factory #

题意#

给定 $n$ 个步骤，这些步骤有依赖关系（可能存在循环依赖），步骤 $i$ 有 $p_i$ 概率失败，一个步骤不失败要求它及其前置步骤均不失败，问失败概率最小的步骤的不失败概率为多少

题解#

对于非循环依赖的步骤，显然所有不存在依赖的步骤失败概率最小，对于循坏依赖的步骤，其组成的一个强连通分量中的每一个步骤的不失败概率均为 $\prod(1 - p_i)$ 先求强连通分量，再对所有入度为 $0$ 的步骤的失败概率取最小即可。

NOTE
输出小数点后200位

代码#

1
const int N = 1e5 + 5;
2
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
3
int scc[N], sc;  // 结点 i 所在 SCC 的编号
4
int sz[N];       // 强连通 i 的大小
5
vector<vector<int>> e(N);
6
void tarjan(int u) {
7
    low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
8
    for (auto v : e[u]) {
9
        if (!dfn[v]) {
10
            tarjan(v);
11
            low[u] = min(low[u], low[v]);
12
        } else if (in_stack[v]) {
13
            low[u] = min(low[u], dfn[v]);
14
        }
15
    }
16
    if (dfn[u] == low[u]) {
17
        ++sc;
18
        do {
19
            scc[s[tp]] = sc;
20
            sz[sc]++;
21
            in_stack[s[tp]] = 0;
22
        } while (s[tp--] != u);
23
    }
24
}
25

26
void idol_produce(int testCase) {
27
    /*Code Here*/
28
    int n, m;
29
    cin >> n >> m;
30
    vector<double> p(n + 1);
31
    for(int i = 1;i <= n; i++){
32
        double x;
33
        cin >> x;
34
        p[i] = 1.0 - x;
35
    }
36
    vector<pair<int,int> > ed;
37
    for (int i = 1; i <= m; i++) {
38
        int u, v;
39
        cin >> u >> v;
40
        e[v].push_back(u);
41
        ed.push_back({u, v});
42
    }
43
    for(int i = 1;i <= n; i++){
44
        if(!dfn[i]) tarjan(i);
45
    }
46
    vector<double> ans(sc + 1, 1);
47
    vector<int> in(sc + 1);
48
    for(int i = 1;i <= n; i++){
49
        ans[scc[i]] *= p[i];
50
    }
51
    for(auto &[u, v] : ed){
52
        if(scc[u] != scc[v]){
53
            in[scc[u]]++;
54
        }
55
    }
56
    double res = 0;
57
    for(int i = 1;i <= sc; i++){
58
        if(in[i] == 0){
59
            res = max(res, ans[i]);
60
        }
61
    }
62
    cout << fixed << setprecision(200) << res << '\n';
63
}

M. Museum Visit #

题意#

给定 $1-n$ 每个整数的代价 $c_i$ , 选择一个整数集合使得对于共计 $m$ 个区间的每一个区间 $[l_i,r_i]$ ，都有至少一个整数落在区间内，求最小的代价之和

题解#

显然动态规划：

设 $dp_i$ 表示在选择整数 $i$ 的前提下，所有 $r_i \leq i$ 的区间均被满足的最小代价

dp_i = c_i + \min\limits_{j \in [k_i,i)}dp_j

其中 $k_i$ 表示所有 $\max(l_i|r_i < i)$ ，即所有满足 $r_i < i$ 的区间中，最大的 $l_i$

可以使用线段树维护 $dp$ 值

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, m;
4
    cin >> n >> m;
5
    vector<ll> dp(n + 2, 0);
6
    vector<ll> c(n + 2, 0);
7
    for (int i = 1; i <= n; i++) {
8
        cin >> c[i];
9
    }
10
    vector<pair<int,int>> p(m + 1);
11
    for (int i = 1; i <= m; i++) {
12
        cin >> p[i].first >> p[i].second;
13
    }
14
    sort(p.begin() + 1, p.end(), [](const pair<int,int> &a, const pair<int,int> &b) {
15
        return a.second > b.second;
16
    });
17
    SegmentMinTree st(vector<ll>(n + 2));
18
    int l = 0;
19
    for(int i = 1;i <= n + 1; i++){
20
        while(!p.empty() && p.back().second < i){
21
            l = max(l, p.back().first);
22
            p.pop_back();
23
        }
24
        if(l == 0) dp[i] = c[i];
25
        else dp[i] = c[i] + st.query(l, i - 1);
26
        st.change(i, i, dp[i]);
27
    }
28
    cout << dp[n + 1] << '\n';
29
}

K. Karaoke Compression #

题意#

给定一个字符串 $s$ ，选择一个非空字符串 $t$ ，将字符串 $s$ 中的所有不相交的子串 $t$ 均替换为单个字符，获得新的字符串 $s'$ ，求 $|{t}| + |{s'}|$ 的最小值

题解#

采用哈希计算每个不相交子字符串出现的数量，注意必须选择一个非空子串，所以初始 $ans = |{s}| + 1$

NOTE
不要用 map or unordered_map 将哈希值直接作为下标存储对应的 $index$ 集合，否则你的时间常数和空间常数会巨大

代码#

1
int get_id(int i, int j){
2
    return 5000 * i + j;
3
}
4
void idol_produce(int testCase) {
5
    /*Code Here*/
6
    string s;
7
    cin >> s;
8
    int n = s.size();
9
    vector<ull> hash_value(5005 * 5005);
10
    for(int i = 0; i < n; i++){
11
        ull h = 0;
12
        for(int j = i; j < s.size(); j++){
13
            h = h * 131 + s[j];
14
            hash_value[get_id(i, j + 1)] = h;
15
        }
16
    }
17
    int ans = s.size() + 1;
18
    unordered_map<ull, int> count, next_pos;
19
    for(int len = 2; len < n; len++){
20
        count.clear();
21
        next_pos.clear();
22
        for(int i = 0; i <= n - len; i++){
23
            ull h = hash_value[get_id(i, i + len)];
24
            if(next_pos[h] > i) continue;
25
            count[h]++;
26
            next_pos[h] = i + len;
27
        }
28
        for(auto [_,c]:count){
29
            ans = min(ans, n - (len - 1) * (c - 1) + 1);
30
        }
31
    }
32
    cout << ans << "\n";
33
}

B. Buggy Blinkers #

题意#

在未加权图中找到最短路径，但不能进行超过 $k$ 个不间断的转弯。求最短路径

题解#

以 路口位置，路口方向，信号灯状态，开启次数，步数 为节点状态进行广度优先搜索。

NOTE
朝路口某段方向行驶时，不一定走直线。如样例，从路口 $2$ 向南行驶，到达路口 $3$ 时不处在其北侧。

代码#

1
vector<vector<int> > a(5005, vector<int>(4, 0));
2

3
enum Light { left = -1, right = 1, up = 0 };
4
struct node {
5
    int loc;
6
    int direction;
7
    int light;
8
    int time;
9
    int step;
10

11
    node go_up() {
12
        node res = *this;
13
        if (res.light != Light::up) {
14
            res.light = Light::up;
15
        }
16
        res.loc = a[res.loc][(res.direction + 2) % 4];
17
        res.step += 1;
18
        if (res.loc == 0) return res;
19
        for (int i = 0; i < 4; i++) {
20
            if (a[res.loc][i] == this->loc) res.direction = i;
21
        }
22
        return res;
23
    }
24

25
    node go_right() {
26
        auto res = *this;
27
        if (res.light != Light::right) {
28
            res.light = Light::right;
29
            res.time += 1;
30
        }
31
        res.loc = a[res.loc][(res.direction + 3) % 4];
32
        res.step += 1;
33
        if (res.loc == 0) return res;
34
        for (int i = 0; i < 4; i++) {
35
            if (a[res.loc][i] == this->loc) res.direction = i;
36
        }
37
        return res;
38
    }
39

40
    node go_left() {
41
        auto res = *this;
42
        if (res.light != Light::left) {
43
            res.light = Light::left;
44
            res.time += 1;
45
        }
46
        res.loc = a[res.loc][(res.direction + 1) % 4];
47
        res.step += 1;
48
        if (res.loc == 0) return res;
49
        for (int i = 0; i < 4; i++) {
50
            if (a[res.loc][i] == this->loc) res.direction = i;
51
        }
52
        return res;
53
    }
54

55
    bool operator==(const node &x) const {
56
        return x.loc == loc && x.direction == direction && x.light == light &&
57
               x.time == time;
58
    }
59
};
60

61
struct NodeHasher {
62
    size_t operator()(const node &x) const {
63
        return (hash<int>()(x.loc) * 4) ^ (hash<int>()(x.direction) * 3) ^
64
               (hash<int>()(x.light) * 2) ^ hash<int>()(x.time);
65
    }
66
};
67
void idol_produce(int testCase) {
68
    /*Code Here*/
69
    int n, k;
70
    cin >> n >> k;
71
    for (int i = 1; i <= n; i++) {
72
        for (int j = 0; j < 4; j++) {
73
            cin >> a[i][j];
74
        }
75
    }
76
    if (n == 1) {
77
        cout << 0 << '\n';
78
        return;
79
    }
80
    queue<node> q;
81
    for (int i = 0; i <= 3; i++) {
82
        if (a[1][i] == 0) continue;
83
        int dir = 0;
84
        for (int j = 0; j < 4; j++) {
85
            if (a[a[1][i]][j] == 1) {
86
                dir = j;
87
                break;
88
            }
89
        }
90
        q.push({a[1][i], dir, up, 0, 1});
91
    }
92
    unordered_set<node, NodeHasher> vis;
93
    while (!q.empty()) {
94
        auto t = q.front();
95
        q.pop();
96
        if (t.time > k) continue;
97
        if (vis.count(t)) continue;
98
        vis.insert(t);
99
        if (t.loc == n) {
100
            cout << t.step << '\n';
101
            return;
102
        }
103
        auto res = t.go_up();
104
        if (res.loc != 0) q.push(res);
105
        res = t.go_left();
106
        if (res.loc != 0) q.push(res);
107
        res = t.go_right();
108
        if (res.loc != 0) q.push(res);
109
    }
110
    cout << "impossible\n";
111
}

C. Concurrent Contests #

题意#

将 $n$ 个数 $[a_1,a_2,a_3...,a_n]$ 分为 $m$ 组，每组的价值为 $p_j$ 使得所有数均满足以下条件：

对于组别 $j$ 的总和 $sum_j = \sum\limits_{i \in j} a_i$
属于组别 $j$ 的数字 $a_i$ ，满足 $\frac{a_i \times p_j}{sum_j} \geq \frac{a_i \times p_k}{sum_k + a_i},k \neq j$

题解#

对数字从大到小排序，以此将每个数字放在其占比最大的一个分组中。

证明：

对于当前选择的数字 $a_i$ ，显然选择价值最大的组为最优解，设其选择的组别为 $k$ 。
对于已经分好组的数字 $a_j$ ，满足 $a_j \geq a_i$
对于与 $a_i$ 同组的 $a_j$ ，在 $a_i$ 不加入 $k$ 前满足：
$\frac{a_i \times p_k}{sum_k + a_i} \geq \frac{a_i \times p_{other}}{sum_{other} + a_i}$
因此，必然满足：
$\frac{a_j \times p_k}{sum_k + a_i} \geq \frac{a_j \times p_{other}}{sum_{other} + a_j}, a_j \geq a_i$
因此 $a_j$ 移到其他组一定不优
对于与 $a_i$ 不同组的 $a_j$ ，在 $a_i$ 不加入前就已经选择好了最优组， $a_i$ 加入 $k$ 只是让一个对于 $a_j$ 不优的组变得更加不优而已

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, m;
4
    cin >> n >> m;
5
    vector<pair<ll, int>> a(n + 1);
6
    vector<ll> p(m + 1);
7
    for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
8
    for (int i = 1; i <= m; i++) cin >> p[i];
9
    sort(a.begin() + 1, a.end(), greater<>());
10
    vector<vector<int> > ans(m + 1);
11
    vector<ll> sum(m + 1);
12
    for(int i = 1;i <= n;i ++){
13
        int id = 1;
14
        for(int j = 2;j <= m;j ++){
15
            if(p[j] * (sum[id] + a[i].first) > p[id] * (sum[j] + a[i].first)){
16
                id = j;
17
            }
18
        }
19
        ans[id].emplace_back(a[i].second);
20
        sum[id] += a[i].first;
21
    }
22
    for(int i = 1;i <= m;i ++){
23
        cout << ans[i].size() << ' ';
24
        for(int j = 0;j < ans[i].size();j ++){
25
            cout << ans[i][j] << ' ';
26
        }
27
        cout << '\n';
28
    }
29
}