2024-12-13周赛 2024-2025 ICPC Northwestern European Regional Programming Contest

题目链接#

2024-2025 ICPC Northwestern European Regional Programming Contest (NWERC 2024)

A. Alphabetical Aristocrats #

题意#

给定 $n$ 行字符串，从第一个大写字符开始计算有效字符，按字典序进行排序

题解#

签到，按题意模拟即可，注意在输入 $n$ 后，使用 $cin.get()$ 将第一行的回车读入缓存区

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    cin.get();
6
    vector<pair<string, string>> a(n + 1);
7
    for (int i = 1; i <= n; i++) {
8
        getline(cin, a[i].second);
9
        for (int j = 0; j < a[i].second.size(); j++) {
10
            if (a[i].second[j] >= 'A' && a[i].second[j] <= 'Z') {
11
                a[i].first = a[i].second.substr(j);
12
                break;
13
            }
14
        }
15
    }
16
    sort(a.begin() + 1, a.end());
17
    for (int i = 1; i <= n; i++) {
18
        cout << a[i].second << '\n';
19
    }
20
}

E. Evolving Etymology #

题意#

给定一个长度为 $n$ 的初始的字符串 $s$ ，按以下规则构造成一个新的字符串 $s'$ ：

将两个 $s$ 合成一个字符串 $t$ 即： $t = s + s$
$s'$ 为 $t$ 所有的偶数下标的字符集，即 $s'=[t_0, t_2...t_{2n}]$
$s:=s'$

重复 $k$ 次过程，输出最后的 $s$

数据范围#

$1 \le n \le 10^5$ , $1 \le k \le 10^{18}$

题解#

第一次过程获得的字符串为： $[s_{0\%n}, s_{2\%n}, s_{4\%n}, s_{6\%n}...s_{2*(n-1)\%n}]$

第二次过程获得的字符串为： $[s_{0\%n}, s_{4\%n}, s_{8\%n}, s_{12\%n}...s_{4*(n-1)\%n}]$

第三次过程获得的字符串为： $[s_{0\%n}, s_{8\%n}, s_{16\%n}, s_{24\%n}...s_{8*(n-1)\%n}]$

因此，第 $k$ 次过程获得的字符串为： $\sum\limits_{i = 0} ^ {n-1} {s_{i * 2^k \% n}}$

总时间复杂度为 $O(n*log{k})$ ，若预处理 $i * 2 ^ k$ 将优化到 $O(n + logk)$

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    long long n, k;
4
    cin >> n >> k;
5
    mod = n;
6
    string s;
7
    cin >> s;
8
    string tmp;
9
    for(int i = 0; i < s.size(); i++){
10
        tmp += s[qpow(2, k) * i % n];
11
    }
12
    cout << tmp << '\n';
13
}

J. Jib Job #

题意#

给定 $n$ 个不同位置和高度的起重机塔。在每台起重机顶部放置一个吊臂，使得：

任何臂架都不能与任何其他起重机塔碰撞
臂架不能超过起重机的高度，且为整数长度
使可达的面积最大

数据范围#

$1 \le n \le 500$

题解#

每个起重机的最大臂长为所有与比它高的起重机的距离以及它本身高度的最小值

由于 $n \le 500$ ，所以直接模拟即可

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    vector<int>x(n + 1), y(n + 1), h(n + 1);
6
    for(int i = 1;i <= n;i++){
7
        cin >> x[i] >> y[i] >> h[i];
8
    }
9
    for(int i = 1;i <= n; i++){
10
        int ans = h[i];
11
        for(int j = 1; j <= n; j++){
12
            if(h[j] <= h[i]){
13
                continue;
14
            }
15
            ans = min(ans, (int)sqrt(pow(x[i] - x[j],2) + pow(y[i] - y[j], 2)));
16
        }
17
        cout << ans << '\n';
18
    }
19
}

D. Dutch Democracy #

题意#

给定 $n$ 个数字，计所有满足以条件的子集的数目：

子集数字之和严格大于总和的一半
去掉子集的最小值后子集之和小于等于总和的一半

数据范围#

$1 \le n \le 60$ ， $1 \le a_i \le 10,000$

题解#

从大到小dp每一个可能的和的子集数量，转移方程为：

dp[j] = \begin{cases} dp[j] + dp[j - a[i]], & \text{if } j > a[i] \\ dp[0] + 1, & \text{if } j = a[i] \end{cases}

由于是从大到小dp，此时所有新增的子集的最小值一定是 $a_i$ ，那么根据题意更新答案即可

时间复杂度为 $O(n * sum)$

代码#

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

L. Limited Library #

题意#

有 $n$ 个书架， $m$ 本书，书架和书都有各自的高度，书只能放在比它高的书架里。

如果一个书架放满书，那么最多放 $x$ 本书，如果一个书架放艺术品，那么最多放 $y$ 本书

求保证书全放在书架的情况下，最多放几个书架的艺术品

题解#

在确定放几件艺术品的情况下，显然让最矮的书架放艺术品更优，所以二分放艺术品的书架数量即可

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, m, x, y;
4
    cin >> n >> m >> x >> y;
5
    vector<int> a(n + 1);
6
    for (int i = 1; i <= n; i++) {
7
        cin >> a[i];
8
    }
9
    vector<int> b(m + 2);
10
    for (int i = 1; i <= m; i++) {
11
        cin >> b[i];
12
    }
13
    b[m + 1] = INF;
14
    int l = 0, r = n;
15
    int ans = -1;
16
    sort(a.begin() + 1, a.end());
17
    sort(b.begin() + 1, b.end());
18
    auto check = [&](int mid) {
19
        int book = 1;
20
        for (int i = 1; i <= mid; i++) {
21
            for (int j = 1; j <= y; j++) {
22
                if (a[i] >= b[book]) {
23
                    book++;
24
                }
25
                if (book == m + 1) {
26
                    return true;
27
                }
28
            }
29
        }
30
        for (int i = mid + 1; i <= n; i++) {
31
            for (int j = 1; j <= x; j++) {
32
                if (a[i] >= b[book]) {
33
                    book++;
34
                }
35
                if (book == m + 1) {
36
                    return true;
37
                }
38
            }
39
        }
40
        return false;
41
    };
42
    while (l <= r) {
43
        int mid = (l + r) >> 1;
44
        if (check(mid)) {
45
            ans = mid;
46
            l = mid + 1;
47
        } else {
48
            r = mid - 1;
49
        }
50
    }
51
    if (ans == -1) {
52
        cout << "impossible\n";
53
    } else {
54
        cout << ans << '\n';
55
    }
56
}

F. Flowing Fountain #

题意#

模拟香槟塔的倒入流程

题解#

用单调栈来初始化每一层塔所对应的下一层塔的位置，用并查集实现倒入流程的路径压缩

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n, q;
4
    cin >> n >> q;
5
    vector<ll> siz(n + 2);
6
    vector<ll> val(n + 2);
7
    vector<ll> nex(n + 2);
8
    for (int i = 1; i <= n; i++) {
9
        cin >> siz[i];
10
        val[i] = 0;
11
    }
12
    siz[n + 1] = 1e18;
13
    vector<int> p;
14
    for (int i = 1; i <= n + 1; i++) {
15
        while (!p.empty() && siz[i] > siz[p.back()]) {
16
            nex[p.back()] = i;
17
            p.pop_back();
18
        }
19
        p.emplace_back(i);
20
    }
21
    auto get_next = [&](int x, auto& get_next) {
22
        if (val[nex[x]] < siz[nex[x]]) {
23
            return nex[x];
24
        } else {
25
            return nex[x] = get_next(nex[x], get_next);
26
        }
27
    };
28
    while (q--) {
29
        char op;
30
        cin >> op;
31
        if (op == '+') {
32
            ll l, x;
33
            cin >> l >> x;
34
            if (val[l] + x <= siz[l]) {
35
                val[l] += x;
36
            } else {
37
                x -= siz[l] - val[l];
38
                val[l] = siz[l];
39
                while (x) {
40
                    l = get_next(l, get_next);
41
                    ll nextval = val[l] + x;
42
                    if (nextval <= siz[l]) {
43
                        val[l] = nextval;
44
                        break;
45
                    } else {
46
                        x -= siz[l] - val[l];
47
                        val[l] = siz[l];
48
                    }
49
                }
50
            }
51
        }
52
        else{
53
            int x;
54
            cin >> x;
55
            cout << val[x] << '\n';
56
        }
57
    }
58
}

H. Hash Collision #

题意#

给定一个范围 $n$ 和一个散列函数 $f$ ，这个散列函数接受两个 $1-n$ 的参数 $c$ , $r$ , $f^c(r)$ 表示将初始值 $r$ 进行 $c$ 次散列化，并返回一个范围为 $1-n$ 的散列值，在 $1000$ 次询问内找到一对 $c$ , $r$ 满足 $f^c(r) = c$

题解#

询问 $n$ , $c$ ，得到 $x = f^n(c)$
如果 $x=n$ ，那么就找到一对答案 $f^n(c) = n$
否则必然满足 $x < n$ ，询问 $n-x, c$ ，得到 $y = f^{n-x}(c)$
此时满足 $f^x(y) = f^x(f^{n-x}(c)) = f^n(c) = x$

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    int n;
4
    cin >> n;
5
    cout << "? " << n << ' ' << 1 << endl;
6
    int x;
7
    // f(n, 1)
8
    cin >> x;
9
    if (x == n) {
10
        cout << "! " << n << ' ' << 1 << endl;
11
        return;
12
    }
13
    cout << "? " << n - x << ' ' << 1 << endl;
14
    // f(n - x, 1)
15
    int y;
16
    cin >> y;
17
    // f(x, f(n - x, 1)) = f(n, 1) = x
18
    // f(x, y) = x
19
    cout << "! " << x << ' ' << y << endl;
20
}

K. Kruidnoten #

题意#

在无向图中，其中一些点有 $p_i$ 的概率成为途径点，每个点之间的概率独立计算，问在至少经过一个途径点的情况下的期望最短路径是多少

题解#

当选择其中一个点作为路径上的途径点时最优时，必然满足经过其他途径点的且比这条路径更短的路径上的途径点都在 $1 - p_j$ 的概率下未能成为途径点，且这个点在 $p_i$ 的概率下成为了途径点

故使用双向Dijkstra算法求出每个途径点所在的最短路径，并排序。

得到 $dis(v_1) < dis(v_2) < dis(v_3) ... dis(v_n)$

答案为 $ans = \sum\limits_{i = 1}^{n} p_{v_i} * \prod\limits_{j = 1}^{n-1}(1-p_{v_j})$

代码#

1
constexpr int MAXN = 1e6 + 100;
2
struct edge {
3
    ll to, weight;
4
};
5
struct node {
6
    ll id, weight;
7
    bool operator<(const node& rhs) const { return weight > rhs.weight; }
8
};
9
vector<edge> e[MAXN];
10

11
vector<ll> dijkstra(int s) {
12
    vector<ll> dis(MAXN, 1e18);
13
    vector<bool> vis(MAXN, false);
14
    dis[s] = 0;
15
    priority_queue<node> q;
16
    q.push({s, 0});
17
    while (!q.empty()) {
18
        auto [u, d] = q.top();
19
        q.pop();
20
        if (vis[u]) continue;
21
        vis[u] = true;
22
        for (auto [v, w] : e[u]) {
23
            if (dis[v] > d + w) {
24
                dis[v] = d + w;
25
                q.push({v, dis[v]});
26
            }
27
        }
28
    }
29
    return dis;
30
}
31

32
struct reslut {
33
    ll dis, id;
34
    long double p;
35
    bool operator<(const reslut& rhs) const { return dis < rhs.dis; }
36
};
37
void idol_produce(int testCase) {
38
    /*Code Here*/
39
    int n, m, k;
40
    cin >> n >> m >> k;
41
    vector<reslut>res(k + 1);
42
    for (int i = 1; i <= m; i++) {
43
        ll u, v, w;
44
        cin >> u >> v >> w;
45
        e[u].push_back({v, w});
46
        e[v].push_back({u, w});
47
    }
48
    for (int i = 1; i <= k; i++) {
49
        cin >> res[i].id >> res[i].p;
50
    }
51
    if (!any_of(res.begin() + 1, res.end(), [](const reslut& x) { return x.p == 1; })){
52
        cout << "impossible\n";
53
        return;
54
    }
55
    auto dis = dijkstra(1);
56
    for(int i = 1; i <= k; i++){
57
        res[i].dis = dis[res[i].id];
58
    }
59
    dis = dijkstra(n);
60
    for(int i = 1; i <= k; i++){
61
        res[i].dis += dis[res[i].id];
62
    }
63
    sort(res.begin() + 1, res.end());
64
    long double ans = 0;
65
    long double pre = 1;
66
    for(int i = 1;i <= k; i++){
67
        ans += res[i].dis * pre * res[i].p;
68
        pre *= (1.0 - res[i].p);
69
    }
70
    cout << fixed << setprecision(10) << ans << '\n';
71
}

C. Connect Five #

题意#

矩阵上有5个点，用最短的路径连接这5个点满足每个点之间的路径长度最短

题解#

注意到，对于最左侧的点，必然有一条直线向右的路径直到与另一个点在同一条直线上。因此可以将最左侧的点向右平移，这对于上下左右方向都同理。

如果操作后使得多个点在同一个位置，那么合并这多个点，因为这多个点接下来一定共享接下来的路径

重复操作，直到没有点可以缩短和合并

所有操作完成后，剩下的点集必然构成一个点，一个矩阵，或两个相邻矩阵，根据不同的结果进行划分即可。

代码#

1
void idol_produce(int testCase) {
2
    /*Code Here*/
3
    vector<pair<ll, ll> > a(5);
4
    for (int i = 0; i < 5; i++) {
5
        cin >> a[i].first >> a[i].second;
6
    }
7
    ll ans = 0;
8
    for (int i = 1; i <= 100 && a.size() > 1; i++) {
9
        sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y) {
10
            if(x.first == y.first){
11
                return x.second < y.second;
12
            }
13
            return x.first < y.first;
14
        });
15
        ans += a[1].first - a[0].first;
16
        a[0].first = a[1].first;
17
        ans += a[a.size() - 1].first - a[a.size() - 2].first;
18
        a[a.size() - 1].first = a[a.size() - 2].first;
19
        sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y) {
20
            if(x.second == y.second){
21
                return x.first < y.first;
22
            }
23
            return x.second < y.second;
24
        });
25
        ans += a[1].second - a[0].second;
26
        a[0].second = a[1].second;
27
        ans += a[a.size() - 1].second - a[a.size() - 2].second;
28
        a[a.size() - 1].second = a[a.size() - 2].second;
29
        sort(a.begin(), a.end());
30
        a.erase(unique(a.begin(), a.end()), a.end());
31
    }
32
    if(a.size() == 1){
33
        cout << ans << '\n';
34
        return;
35
    }
36
    assert(a.size() >= 4);
37
    set<int>s1, s2;
38
    for(int i = 0; i < a.size(); i++){
39
        s1.insert(a[i].first);
40
        s2.insert(a[i].second);
41
    }
42
    assert(s1.size() <= 3 && s2.size() <= 3);
43
    assert(s1.size() > 1 && s2.size() > 1);
44
    if(s1.size() <= 2 || s2.size() <= 2){
45
        ans += 2 * (*s1.rbegin() - *s1.begin());
46
        ans += 2 * (*s2.rbegin() - *s2.begin());
47
        cout << ans << '\n';
48
        return;
49
    }
50
    else{
51
        ans += 2 * (*s1.rbegin() - *s1.begin());
52
        ans += 2 * (*s2.rbegin() - *s2.begin());
53
        int l1 = *s1.begin(), r1 = *s1.rbegin(), l2 = *s2.begin(), r2 = *s2.rbegin();
54
        for(int i = 0;i < a.size(); i++){
55
            if(a[i].first == l1 || a[i].first == r1 || a[i].second == l2 || a[i].second == r2){
56
                continue;
57
            }
58
            ans += min(*s1.rbegin() - *s1.begin(), *s2.rbegin() - *s2.begin());
59
            break;
60
        }
61
        cout << ans << '\n';
62
        return;
63
    }
64
}

M. Mouse Trap #

题意#

凸多边形中任意三个点会组成一个三角形覆盖凸多边形的一部分区域，求凸多边形内部的一个点期望被多少个三角形覆盖

题解#

题目可以直接转化成求凸多边形内所有的三元组点构成的三角形面积之和与凸多边形的面积的除数

重点在于如何求出所有的三角形面积之和，我们转化公式：

\begin{align} \sum_{i < j < k}\frac{1}{2}(p_j - p_i) \otimes (p_k - p_j) \newline = \frac{1}{2}\sum_j(\sum_{i < j}(p_j - p_i)) \otimes (\sum_{j < k}(p_k - p_j)) \newline = \frac{1}{2}\sum_j((j-1)p_j - \sum_{i<j}p_i) \otimes (\sum_{j<k}p_k-(n-j)p_j) \end{align}

代码#

1
struct point{
2
    double x, y;
3

4
    constexpr double operator^(point & rhs) const{
5
        return x * rhs.y - y * rhs.x;
6
    }
7
};
8
void idol_produce(int testCase) {
9
    /*Code Here*/
10
    int n;
11
    cin >> n;
12
    vector<point> p(n + 10);
13
    vector<double> prex(n + 10), prey(n + 10), sufx(n + 10), sufy(n + 10);
14
    for (int i = 1; i <= n; i++) {
15
        cin >> p[i].x >> p[i].y;
16
    }
17
    prex[1] = p[1].x;
18
    sufx[n] = p[n].x;
19
    for (int i = 2; i <= n; i++) {
20
        prex[i] = prex[i - 1] + p[i].x;
21
    }
22
    for (int i = n - 1; i >= 1; i--) {
23
        sufx[i] = sufx[i + 1] + p[i].x;
24
    }
25
    prey[1] = p[1].y;
26
    sufy[n] = p[n].y;
27
    for (int i = 2; i <= n; i++) {
28
        prey[i] = prey[i - 1] + p[i].y;
29
    }
30
    for (int i = n - 1; i >= 1; i--) {
31
        sufy[i] = sufy[i + 1] + p[i].y;
32
    }
33
    auto get_area = [&]() -> double{
34
        double ans = 0;
35
        for(int i = 1;i <= n; i ++){
36
            int nxt = (i + 1);
37
            if (i == n) nxt = 1;
38
            ans += (p[i] ^ p[nxt]);
39
        }
40
        return abs(ans) / 2;
41
    };
42
    double area = get_area();
43
    double ans = 0;
44
    for(int i = 1;i <= n; i++){
45
        point a, b;
46
        a.x = (i - 1) * p[i].x - prex[i - 1];
47
        a.y = (i - 1) * p[i].y - prey[i - 1];
48
        b.x = sufx[i + 1] - (n - i) * p[i].x;
49
        b.y = sufy[i + 1] - (n - i) * p[i].y;
50
        ans += (a ^ b) / 2;
51
    }
52
    cout << fixed << setprecision(10) << ans / area << '\n';
53
}