526互联

Codeforces Round 892 (Div. 2)(vp)

发布时间 2023-08-13 19:31:56作者: north_h

Codeforces Round 892 (Div. 2)

A United We Stand

题意：给一个数组，让你把它分成两个数组，第二个数组里的数不能是第一个数组里的数的除数，先输出两个数组的长度，依次输出两个数组的数，如果无法分出来，输出-1

思路：如果数的种类只有一种一定不行，反之一定行，对于可行的情况，我们把最大的数放在第二部分，其他的数放在第一部分，一定满足条件

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for(auto &i : a)cin >> i, mp[i]++;
    sort(rALL(a));
    if(mp.size() == 1)cout << -1 << endl;
    else {
        cout << n - mp[a[0]] << ' ' << mp[a[0]] << endl;
        for(auto i : a)if(i != a[0])cout << i << ' ';
        cout << endl;
        for(auto i : a)if(i == a[0])cout << i << ' ';
        cout << endl;
    }
}

B Olya and Game with Arrays

题意：给一个类似二维数组，但是不规则，通过无限次操作使得每一行最小的数的和最大，操作：最多可以将一个（可能是 0 ）整数从每个数组移动到另一个数组。需要注意的是，整数只能从一个数组中移动一次，但整数可以添加到一个数组中多次，而且所有移动都是同时完成的

思路：要是总和最大，尽可能是每一行的最小值最大，而所有数的最小一定固定占据一行，而每一个数最多移动一次，所以我们把每一行的最小的数移到一行，其他行的次小值就变成最小值，一定是最优的，总而言之就是所有数的最小值\(+\)每一行的次小值\(-\)每一行次小值的最小的那个就是答案

void solve() {
    int n;
    cin >> n;
    int mn = INT_MAX;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        vector<int> a(m);
        for(auto &j : a)cin >> j;
        sort(ALL(a));
        mn = min(mn, a[0]);
        ans.push_back(a[1]);
    }
    sort(rALL(ans));
    int sum = mn;
    for(int i = 0; i < n - 1; i++)sum += ans[i];
    cout << sum << endl;
}

C Another Permutation Problem

题意：找到一个\(n\)的排列\(p\)，满足：\((\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)\)

思路：看见排列，我直接打表，打表的代码和图片如下，我们可以发现最优解的排列只是在\(n,n-1,n-2,n-3,\dots,1\)的基础上向右移动获得的，我们可以暴力的去枚举每一中情况，时间复杂度：\(O(n)\)，而且此题数据范围只有250，妥妥的

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    int ans = 0;
    int mx = 0;
    for(int i = 0; i < n; i++) {
        sum = 0;
        mx = 0;
        for(int j = 1; j <= i; j++) {
            sum += j * j;
            mx = max(mx, j * j);
        }
        for(int j = i + 1, k = n; j <= n; j++, k--) {
            sum += k * j;
            mx = max(k * j, mx);
        }
        ans = max(ans, sum - mx);
    }
    cout << ans << endl;
}

打表的代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> ans;
    int an = 0;
    for (int i = 1; i <= n; i++)a[i] = i;
    do {
        int res = 0;
        int re = 0;
        for (int i = 1; i <= n; i++)res += a[i] * i, re = max(re, a[i] * i);
        if (an < res - re) {
            an = res - re;
            ans = a;
        }
    } while (next_permutation(a.begin() + 1, a.end()));
    cout << n << ' ' << an << endl;
    for (int i = 1; i <= n; i++)cout << ans[i] << ' ';
    cout << endl;
}

2 2
2 1
3 7
1 3 2
4 17
1 2 4 3
5 35
1 2 5 4 3
6 62
1 2 3 6 5 4
7 100
1 2 3 4 7 6 5
8 152
1 2 3 4 8 7 6 5
9 219
1 2 3 4 5 9 8 7 6
10 303
1 2 3 4 5 6 10 9 8 7
11 406
1 2 3 4 5 6 7 11 10 9 8