Codeforces Round #708 (Div. 2)

没有正式参加(又划水), 这场比赛unrated。 从比赛结果看, 题目似乎不是很难.

A题 Meximization

原题链接

题意:

给定一个数组$a$, 对该数组重新排序得到$b$, 使得$\sum_{i=0}^NMEX(b_{1}…b_{i})$最大, 其中$MEX$是指所有数中没有出现的最小非负整数.

思路:

贪心, 尽量把小的数向前填, 同时保证不出现重复数字, 即构造$b$前面部分为$a$中数字从小到大排序后的数字(不重复), 剩下部分为$a$中重复出现的数字.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 110;
int a[N];
map<int,int> mp;

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i ++ ){
        if (mp[a[i]])
            mp[a[i]] ++;
        else{
            cout << a[i] << ' ';
            mp[a[i]] ++;
        }
    }
    for (int i = 0; i <= N; i ++ )
        if (mp[i] >= 2){
            for (int j = 2; j <= mp[i]; j ++ )
                cout << i << ' ';
        }
    cout << endl;
    mp.clear();
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- ){
        solve();
    }

    return 0;
}

B题 M-arrays

原题链接

题意:

给定数组$a$和$m$, 对$a$中元素重新分组, 使得每一组中相邻两个元素都能被$m$整除, 求一种分组方法,使得组数最小.(单独一个数认为可以被$m$整除)

思路:

构造, 使用数组$cnt[]$, $cnt[i]$ 记录数字i出现次数, 将每个数对$m$取模, 并将结果$i$对应的$cnt[i] ++$, 遍历 $1 -> m$, 对$cnt[i]$ 与 $cnt[m - i]$ 进行处理.

设 $ i = x mod m $, $j = y mod m$ , 易知, 当 $i + j = m$ 时, $x + y$一定可以被$m$整除.据此进行构造.

#include <iostream>
#include <cstring>
#include <map>

using namespace std;

const int N = 1e5 + 10;

int a[N];
int cnt[N];
int m;
int st[N];

void solve()
{
    int n;
    memset(cnt, 0, sizeof cnt);
    int ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        cnt[a[i] % m]++;
        //cout << a[i] % m << ' ';
        //cout << cnt[a[i] % m] << endl;
    }
    if (cnt[0])
        ans += 1;

    for (int i = 1; i <= m / 2; i ++ ){
        if (m - i == 0)
            continue;
        int x = cnt[i];
        int y = cnt[m - i];
        if (x == 0 && y == 0)
            continue;
        if ( x == y + 1 || y == x + 1)
            ans += 1;
        else if (x == y)
            ans += 1;
        else{
            if (y > x)
                swap(x, y);
            ans += 1 + x - y - 1;
        }
        //cout << ans << ' ' << i << endl;
    }
    cout << ans << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- ){
        solve();
    }

    return 0;
}

C1题 k-LCM (easy version)

原题链接

题意:

给定数字$n$, $k$($k = 3$), 构造$k$个数, 使得这$k$个数和为$n$,且最小公倍数小于等于$n / 2$

思路:

(感觉比B简单), 分三种情况:
1. $n$为奇数, 构造三个数为$1,(n - 1) / 2,(n - 1)/2$
2. $n$能被2和4整除: $n / 2,n / 4,n / 4$
3. $n$能被2整除,不能被4整除: $2,(n - 2)/2,(n - 2)/2$

#include <iostream>
#include <cstring>

using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    if (n % 2){
        int t = (n - 1) / 2;
        printf("%d %d %d\n", 1, t, t);
    }else{
        if (n % 4 == 0){
            printf("%d %d %d\n", n / 2, n / 4, n / 4);
        }else{
            int t = (n - 2) / 2;
            printf("%d %d %d\n", 2, t, t);
        }
    }
    return ;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

C2题 k-LCM (hard version)

原题链接

题意:

和C1不同就是$k$未知,但满足$3\leq k\leq n$

思路:

将$k - 3$个数全部设为$1$, 剩下$3$个数和C1题一样

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k - 3; i ++ ){
        cout << 1 << ' ';
        n--;
    }
    if (n % 2){
        int t = (n - 1) / 2;
        printf("%d %d %d\n", 1, t, t);
    }else{
        if (n % 4 == 0){
            printf("%d %d %d\n", n / 2, n / 4, n / 4);
        }else{
            int t = (n - 2) / 2;
            printf("%d %d %d\n", 2, t, t);
        }
    }
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}