Codeforces-Round#603-Div2部分题解

发表于 | 更新于 | 阅读次数：

比赛链接

A.Sweet Problem

题意：

有三种糖果，要求每天必须吃两颗不同种类的糖果，问最多可以吃几天

分析：

排个序，然后很明显，如果最少的两种糖果个数之和（设为sum）小于等于最多的，就能吃sum天，否则是三种糖果之和除以2，向下取整。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int main()
{
    int n;
    scanf("%d", &n);
    while (n--) {
        int a[3];
        for (int i = 0; i < 3; ++i) {
            scanf("%d", a + i);
        }
        sort(a, a + 3);
        if ((a[0] + a[1]) <= a[2]) {
            printf("%d\n", a[0] + a[1]);

        } else {
            printf("%d\n", (a[0] + a[1] + a[2]) / 2);
        }
    }
    return 0;
}

B1.PIN Codes

题意：

给出n个4位PIN码，要求变换最少的数字，使得n个PIN码两两不同

分析：

因为每组样例的n最大为10，所以出现重复PIN时，我们可以只修改每个PIN的末位。注意，开始处理前必须将已经出现过的末位数字标记上。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int solve(int idx[])  //寻找0到9中没有出现过的数字
{
    for (int k = 0; k < 10; k++) { 
        if (idx[k] == 0) {
            idx[k] = 1;
            return k;
        }
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        string s[10];
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> s[i];
        int idx[10] = {}, ans = 0;
        for (int i = 0; i < n; i++) {
            idx[s[i][3] - '0'] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    s[j][3] = '0' + solve(idx);
                    ans++;
                }
            }
        }
        cout << ans << endl;
        for (int i = 0; i < n; ++i)
            cout << s[i] << endl;
    }
    return 0;
}

C.Everyone is a Winner!

题意：

一个n，分别被n+1到1除，向下取整，问商有几个，

分析：

打表找规律，规律看下方代码

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int sqn=(int)sqrt(n);
        set<int> v;
        for(int i=0 ;i<=sqn;++i)
        {
            //printf("%d ",i);
            v.insert(i);
        }
        for(int i=1 ;i<=sqn;++i)
        {
               // printf("%d ",n/i);
                v.insert(n/i);
        }
        cout<<v.size()<<endl;
        set<int> ::iterator it0=v.begin();
        while(it0!=v.end())
        {
            cout<<*it0<<' ';
                it0++;
        }
        cout<<'\n';
    }
    
    return 0;
}

D.Secret Passwords

题意：

n个密码串。如果两个密码含有同一个字母，两串密码等价。n个密码里仅有一个是正确密码，当然，和它等价的也是正确密码。问最坏情况要试多少个密码。

分析：

就是询问共有多少个不等价密码串。考虑等价条件，采用并查集进行合并。首先，以行为单位进行合并， 已知一个并查集的集合里所有元素的祖先只有一个，因此查询所有出现过的字母的祖先，去重即可

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 8;
int fa[26];
char s[maxn][55];
void mkSet(int sz);
int find0(int x);
void unionSet(int x, int y);
int idx[2666];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    mkSet(26);
    for (int i = 0; i < n; i++) //首先按照行来进行合并
    {
        for (int j = 0; s[i][j]; j++) {
            unionSet(s[i][j] - 'a', s[i][0] - 'a');
            idx[s[i][j]] = 1;
        }
    }
    set<int> se;
    for (int i = 0; i < 26; i++) {
        if (idx['a' + i])
            se.insert(find0(i));
    }
    printf("%d\n", se.size());
    return 0;
}
void mkSet(int sz)
{
    for (int i = 0; i < sz; i++)
        fa[i] = i;
}
int find0(int x)
{
    if (fa[x] != x)
        fa[x] = find0(fa[x]);
    return fa[x];
}
void unionSet(int x, int y)
{
    x = find0(x);
    y = find0(y);
    if (x == y) //表示在同一集合
        return;
    else
        fa[x] = y;
}
0%