SMU Summer 2024 Contest Round 3

寻找素数对

题意

给你一个偶数，找到两个最接近的素数，其和等于该偶数。

思路

处理出 1e5 以内的素数，然后遍历，更新最接近的答案。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

vector<int> euler_range(int n) {
    vector<int> phi(n + 1), prime;
    vector<bool> is_prime(n + 1, true);
    is_prime[1] = 0, phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) prime.push_back(i), phi[i] = i - 1;
        for (int j = 0; j < (int)prime.size() && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    return prime;
}

const int N = 1e5;
auto pr = euler_range(N);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x;
    set<int> s(pr.begin(), pr.end());
    while (cin >> x) {
        int a = 0, b = 0;
        for (auto i : pr) {
            if (i > x) break;
            if (s.count(x - i)) {
                if (!a) a = i, b = x - i;
                else if (abs(x - i - i) < abs(a - b))
                    a = i, b = x - i;
            }
        }
        if (a > b) swap(a, b);
        cout << a << ' ' << b << '\n';
    }

    return 0;
}

抱歉

题意

平面上有 n 个点，每个点至少有 2 条曲线线段连接，所有曲线线段不相交，但是任意两点之间可以有多条曲线，问你 n 个点将平面分成了 m 份中存在的曲线线段数量。

思路

满足最小的条件，即每个点都能有两条曲线线段相连的图中最少有 n 条线段。

如图：

可以看出，最小符合条件的连线方式将平面分成了 2 份，又因为两点之间可以有多条曲线，所以每增加一个曲面只需要加一条曲线即可。

如图：

所以答案就是 \(n+m-2\)，记得开longlong。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n,m;
    while(cin >> n >> m && n && m){
       	cout << n + m - 2 << '\n';
    }

    return 0;
}

搬寝室

题意

从 n 个物品中选出 2k 个物品，每两个物品产生的贡献是其重量差值的平方，求最小的贡献值。

思路

n 个选 2k 个，考虑dp。

因为要求差值的平方最小，所以我们将物品按重量按差值排序，排序后相邻的物品其重量差值相对最小。

然后处理出第 i 个物品与 i + 1 个物品间的差值平方。

设 \(dp_{i,j}\) 为前 i 个物品中搬运 j 次的最小贡献。

对于第 i 个物品，如果选择它，则答案是 i-1 物品与它的贡献加上 \(dp_{i-2,j-1}\) 时的贡献，如果不选，那答案就等于 \(dp_{i-1,j}\) 。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    while (cin >> n >> k) {
        vector<i64> w(n + 1);
        for (int i = 1; i <= n; i ++)
            cin >> w[i];

        sort(w.begin() + 1, w.end());

        vector<vector<i64>> dp(n + 1, vector<i64>(k + 1, LLONG_MAX / 2));

        vector<int> val(n + 1);
        for (int i = 1; i < n; i ++) {
            val[i] = pow(w[i + 1] - w[i], 2);
        }

        for (int i = 0; i <= n; i ++)
            dp[i][0] = 0;

        for (int i = 2; i <= n; i ++)
            for (int j = 1; j * 2 <= i && j <= k; j ++) {
                dp[i][j] = min(val[i - 1] + dp[i - 2][j - 1], dp[i - 1][j]);
            }

        cout << dp[n][k] << '\n';
    }

    return 0;
}

Nuts

题意

累加 n 个数大于 10 的部分。

思路

按题意模拟。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int ans = 0;
    while (n --) {
        int x;

        cin >> x;
        ans += max(0, x - 10);
    }

    cout << ans << '\n';

    return 0;
}

Happy Birthday! 2

题意

给你一个含有 N 个正整数的序列 A，请你构造两个序列 B 和 C。

设这两个序列长度分别为