NWERC 2024

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

Problems	Status	Notes
A. Alphabetical Aristocrats	○
B. Binary Search
C. Connect Five
D. Dutch Democracy	○
E. Evolving Etymology
F. Flowing Fountain
G. Glued Grid
H. Hash Collision	○
I. It’s a Kind of Magic
J. Jib Job	○
K. Kruidnoten	⊕
L. Limited Library	○
M. Mouse Trap

A - Alphabetical Aristocrats

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

按题意模拟即可

Code

struct Node {
    string s, t;
};
void solve() {
    int n = read();
    vector<Node> a(n);  
    for (auto &[s, t] : a) {
        getline(cin, s);
        int m = s.size();
        for (int i = 0; i < m; i++) {
            if ('A' <= s[i] and s[i] <= 'Z') {
                t = s.substr(i);
                break;
            }
        }
    }

    std::sort(a.begin(), a.end(), [&](Node a, Node b) {
        return a.t < b.t;
    });

    for (auto [s, t] : a) {
        cout << s << '\n';
    }
}

J - Jib Job

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

• 悬臂不会与任何其他起重机塔相撞。
• 任何起重机都不会因为悬臂长度超过塔高而不稳定。
• 可以覆盖的地面面积最大化。

$1 \le n \le 500$

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

Code

void solve() {
    int n = read();
    vector<int> x(n), y(n), h(n);
    for (int i = 0; i < n; i++) {
        x[i] = read();
        y[i] = read();
        h[i] = read();
    }

    for (int i = 0; i < n; i++) {
        int res = h[i];
        for (int j = 0; j < n; j++) {
            if (h[j] <= h[i]) continue;
            int d = (x[i] - x[j]) * (x[i] - x[j])
                    + (y[i] - y[j]) * (y[i] - y[j]);
            d = sqrt(d);
            res = min(res, d);
        }
        cout << res << '\n';
    }
}

L - Limited Library

将 $m$ 本高度为 $b_i$ 的书放入 $n$ 个高度为 $a_j$ 的书架中
如果一个书架放满书，那么最多放 $x$ 本书，如果一个书架放艺术品，那么最多放 $y$ 本书
求保证书全放在书架的情况下，最多放几个书架的艺术品

$1 \leq n, m \leq 10^5$, $1 \leq y < x \leq 1000$
$1 \leq a, b \leq 10^9$

二分放艺术品的书架数量，尽量让更矮的书架放艺术品

Code

void solve() {
    int n = read();
    int m = read();
    int x = read();
    int y = read();
    vector<int> a(n);
    for (auto &x : a) x = read();
    std::ranges::sort(a);
    vector<int> b(m);
    for (auto &x : b) x = read();
    std::ranges::sort(b);

    auto judge = [&](int lim) {
        // [1, lim]
        vector t(n, x);
        for (int i = 0; i < lim; i++) {
            t[i] = y;
        }

        int p = 0;
        for (auto x : b) {
            if (t[p] > 0 and a[p] >= x) {
                t[p]--;
            } else {
                while (p < n and (a[p] < x or !t[p])) p++;
                if (p >= n) return 0;
                t[p]--;
            }
        }
        return 1;
    };

    int ans = -1;
    for (int L = 0, R = n; L <= R; ) {
        int mid = L + R >> 1;
        if (judge(mid)) {
            ans = mid, L = mid + 1;
        } else {
            R = mid - 1;
        }
    }

    if (ans == -1) {
        cout << "impossible\n";
    } else {
        cout << ans << '\n';
    }
}

D - Dutch Democracy

给定 n 个政党及其席位数量，有多少个子集满足以下条件：

• 子集的累计席位数量大于总席位数量的一半，并且
• 放弃任何一个政党都会使累计席位数量小于等于总席位数量的一半？

$1 \le n \le 60$
$1 \le p \le 10,000$, the number of seats each party has.

将条件 2 转化为删除最小值后，子集的和 小于等于 全集的和 的一半

$O(n)$ 枚举最小值 $x$，问题转化成求子集数量，使得子集和 + x > tot / 2, 子集和 < tot / 2，$O(np)$ 01 背包求解，总复杂度 $O(n^2p)$

更进一步地，直接从大到小排序，每次用来更新状态的必然是最小的，时间复杂度 $O(n\log n + np)$

Code

void solve() {
    int n = read();
    vector<int> a(n);
    for (auto &x : a) x = read();
    std::sort(a.rbegin(), a.rend());
    
    int sum = std::accumulate(a.begin(), a.end(), 0ll);

    int half = sum / 2;
    int ans = 0;
    vector<int> f(1e6);


    for (auto x : a) {
        for (int j = half; j >= 0; j--) {
            f[j + x] += f[j];
            if (j + x > half) ans += f[j];
        }

        f[x]++;
        if (x > half) ans++;
    }
    cout << ans << '\n';
}

E - Evolving Etymology

Code >folded

K - Kruidnoten

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

$2\leq n\leq 2 \cdot 10^5$, $1\leq m\leq 2 \cdot 10^5$, $1\leq k\leq n$

一个点作为特殊点被最短路径经过的时候，充要条件是所有更短的路径上的点都没有成为特殊点，且这个点成为了特殊点。

对于每个可能成为特殊点的点，求出必须经过他时的最短路长度，并按此升序排序。

那么 $ans = \sum_{i = 1}^{n}p_{v_i} \prod_{j = 1}^{i - 1}(1 - p_{v_j})$

Code

using pii = pair<int, int>;
const int inf = 1e18;
struct Node {
    int d, id;
    long double p;
    bool friend operator< (Node a, Node b) {
        return a.d > b.d;
    }
};

void solve() {
    int n = read();
    int m = read();
    int k = read();

    vector<vector<pii>> g(n);
    for (int i = 0; i < m; i++) {
        int u = read() - 1;
        int v = read() - 1;
        int d = read();
        g[u].eb(v, d);
        g[v].eb(u, d);
    }

    vector<Node> a(k);
    for (auto &[_, id, p] : a) {
        cin >> id >> p;
        id--;
    }

    if (ranges::count_if(a, [&](auto x) { return x.p == 1; }) == 0) {
        puts("impossible");
        return;
    }

    auto dijkstra = [&](int s) {
        vector<int> dis(n, inf);
        vector<int> vis(n);
        dis[s] = 0;
        std::priority_queue<Node> q; q.ep(0, s);
        while (!q.empty()) {
            auto [d, u, __] = q.top(); q.pop();
            if (vis[u]) continue; vis[u] = 1;
            for (auto [v, w] : g[u]) {
                if (dis[v] > d + w) {
                    dis[v] = d + w;
                    q.ep(dis[v], v);
                }
            }
        }
        return dis;
    };

    auto dis = dijkstra(0);
    for (auto &[d, id, _] : a) {
        d += dis[id];
    }

    dis = dijkstra(n - 1);
    for (auto &[d, id, _] : a) {
        d += dis[id];
    }

    ranges::sort(a, [&](auto x, auto y) {
        return x.d < y.d;
    });

    long double ans = 0, pre = 1;
    for (auto [dis, id, p] : a) {
        ans += dis * pre * p;
        pre *= (1.0 - p);
    }
    cout << fixed << setprecision(10) << ans << '\n';
}