2020-07-25

Codeforces 634(Div.3)

字数统计: 1k字 | 阅读时长: 4分

A题

题意：你现在有n块糖果，然后你要把n块糖果分给Alice和Betty。Alice分得a块糖果，Betty分得b块糖果。然后约束条件是$a>b$且$a+b=n$，问你有多少种可以表示$n=a+b$的分解方法。

思路：这道题的话，通过看题不难看出当$n<=2$的时候是不能分解的；当$n>2$的时候就是共有$(n-1)/2$种分解方法。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if (n <= 2)
            cout << "0" << endl;
        else
            cout << (n - 1) / 2 << endl;
    }
    return 0;
}

B题

题意：给你三个整数n,a,b表示在n长度的字符串中，每a个连续的字串中，含有b个不同的字母。然后问你满足要求的字符串。

思路：这道题的话，我们构造一下即可。首选我们在a-b的位置构造不同的字母，然后b~a的位置再构造相同的字母，最后我们再重复前面的即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
char s[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, a, b;
        cin >> n >> a >> b;
        char c = 'a';
        memset(s, 0, sizeof(s));
        for (int i = 0; i < a; i++)
        {
            if (i < b)
                s[i] = c + i;
            else
                s[i] = 'a';
            cout << s[i];
        }
        for (int i = a; i < n; i++)
            cout << s[i % a];
        cout << endl;
    }
    return 0;
}

C题

题意：给你一个序列a，然后你可以将里面的元素进行分组，第一组的元素全部都要不同的，第二组全部都要相同的最后两组的数量要一样，问最大的数量是多少。

思路：这道题的话，先用ans记录不同的技能一共有多少人，然后用map记录每个技能的人数有多少人。之后从1~n遍历，如果不同的人数大于相同的，则计算不同的人数；如果不同的人数小于相同的，则计算相同的人数；如果二者相等，求不同的人数减一，因为不同的人数当中包含了相同的，求每一个循环的最大值。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int a[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        map<int, int> h;
        set<int> s;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            h[a[i]]++;
            s.insert(a[i]);
        }
        int cnt = s.size();
        int m = 0;
        for (int i = 1; i <= n; i++)
        {
            if (cnt > h[a[i]])
                m = max(m, h[a[i]]);
            else if (cnt == h[a[i]])
                m = max(m, h[a[i]] - 1);
            else
                m = max(m, cnt);
        }
        cout << m << endl;
    }
    return 0;
}

D题

题意：给你一个9x9的数独，现在要你改数独，要求每一个3x3的块都包含至少两个相同的数字。

思路：这道题的话，我们只需要随便找一个数字改成另一个数字即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 10;
const int inf = 0x3f3f3f3f;
using namespace std;
char a[maxx][maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                cin >> a[i][j];
                if (a[i][j] == '2')
                    a[i][j] = '1';
            }
        }
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                cout << a[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}