0%

Codeforces - Round 831 Div 1 plus 2

Practice.

A. Factorise N+M

题意

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

思路

之外,偶数都不是质数,所以直接加上 即可。

若为 ,那么加上 即可。

时间复杂度:

对应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

题意

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

思路

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

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

但是我不会证

时间复杂度:

对应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

题意

给定一个数组 ,将所有数字任意分成 组,不能出现空组。从三组中各拿出一个数字,使 最小。将数字合理分配,使 的最小值最大。

思路

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

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

时间复杂度:

对应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了那么多遍呢(