Codeforces Round #708 (Div. 2)

Codeforces Round #708 (Div. 2)

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

A题 Meximization

原题链接

题意:

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

思路:

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

#include 
#include 
#include 
#include 

using namespace std;

const int N = 110;
int a[N];
map 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 
#include 
#include 

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 
#include 

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 
#include 

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;
}
codeforces练习赛

相关

标签