Practice.

A. Factorise N+M

题意

给定一个质数，输出一个质数，使两者相加不是质数。

思路

除 \(2\) 之外，偶数都不是质数，所以直接加上 \(3\) 即可。

若为 \(2\)，那么加上 \(2\) 即可。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        cout << (n % 2 == 0 ? 2 : 3) << '\n';
    }
}

水

B. Jumbo Extra Cheese 2

题意

给定 \(n\) 个长方形，所有长方形必须有一条边在 \(x\) 轴上，每个长方形至少需要和另一个长方形有公共边，输出周长最小值。

思路

首先，贴靠在一起后，周长只和最高的高度和所有长方形贴靠在 \(x\) 轴上的长度有关，所以我们希望让最高的高度降低，同时尽量将所有的长方形的短边贴靠在 \(x\) 轴。

因此，我们可以贪心地直接将最高的方块横着放，其余竖着放即可。

但是我不会证

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10;

pii p[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        for(int i=0;i<n;i++) {
            int a, b;
            cin >> a >> b;
            p[i] = {max(a, b), min(a, b)};
        }
        sort(p, p + n, greater<>());
        int cnt = p[0].first;
        for(int i=1;i<n;i++) cnt += p[i].second;
        cout << 2 * (p[0].second + cnt) << '\n';
    }
}

怎么证捏

C. Bricks and Bags

题意

给定一个数组 \(a\)，将所有数字任意分成 \(3\) 组，不能出现空组。从三组中各拿出一个数字，使 \(|w_1 - w_2| + |w_2 - w_3|\) 最小。将数字合理分配，使 \(|w_1 - w_2| + |w_2 - w_3|\) 的最小值最大。

思路

首先，假设我们确定了一个数，那么我们能决定的是将一个组合全部放入最小值或最大值，让这一部分的最小值固定，那么我们只要在一个组合里只放另一个数，要让其最小，肯定会拿出最靠近这个数的数字，因而我们也希望找出数值上相邻的两数，它们的差值最大。

所以，我们可以排序然后枚举这个数字，然后计算出最大值即可。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        for(int i=0;i<n;i++) cin >> a[i];
        sort(a, a + n);
        int ans = 0;
        for(int i=1;i<n;i++) ans = max(ans, max(2 * a[i] - a[i - 1] - a[0], a[i] + a[n - 1] - 2 * a[i - 1]));
        cout << ans << '\n';
    }
}

怎么就WA了那么多遍呢（