Codeforces-Round#599-Div2部分题解

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

比赛链接

A.Maximum Square

题意：

给出n个长度为$a_i$宽度为1的方块，能组成最大的正方形的边长是多少？

分析：

排个序，然后就很明显了。话说有点儿像俄罗斯方块

Code:

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

B1.Character Swap (Easy Version)

题意：

给出两个不同的字符串s和t，s[i]与t[j]交换一次，是否可以使s与t相同。(i,j均为合法的下标)

分析：

显然，只有两串初始有两处不同时可能满足，再判断这两处交换后,s和t是否相同就行。

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
#include <bits/stdc++.h>
using namespace std;
char a[100001], b[100001];
int n;
int pd()
{
    int r = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] != b[i])
            r++;
    }
    return r;
}
int main()
{
    int k;
    cin >> k;
    while (k--) {
        cin >> n;
        scanf("%s%s", a, b);
        int no = pd();
        if (no != 2)
            puts("No");
        else {
            int ji[4], t0 = 0;
            for (int i = 0; i < n; ++i) {
                if (a[i] != b[i]) {
                    ji[t0++] = i;
                }
            }
            swap(a[ji[0]], b[ji[1]]);
            if (strcmp(a, b))
                puts("No");
            else
                puts("Yes");
        }
    }
    return 0;
}

B2.Character Swap (Hard Version)

题意：

给出两个不同的字符串s和t，长度均为n，s[i]与t[j]最多可以交换2n次，是否可以使s与t相同。如果可以，输出Yes和操作次数以及具体的操作，否则输出No(i,j均为合法的下标)

分析：

首先，判断两串所有字母的出现次数，如果每种字母出现的次数都是偶数，就可行，否则不可。
关于具体操作，对于可以一次交换就进行一次交换，而且，无需考虑对后边位置的影响，因为即使打乱后边位置原本的对应关系，也可以再通过操作弥补上。（题目不要求操作次数最小）。无法一次交换的就需要进行两次交换。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
char a[1001], b[10001];
int idx[300];
int main()
{
    int k, n;
    scanf("%d", &k);

    while (k--) {
        vector<int> v;
        vector<int> v1;

        scanf("%d", &n);
        scanf("%s%s", a, b);
        for (int i = 97, j = 0; j < 26; ++j, ++i)
            idx[i] = 0;
        for (int i = 0; i < n; ++i) {
            idx[a[i]]++;
            idx[b[i]]++;
        }
        int f = 1;
        for (int i = 0; i < 26; ++i) {
            if (idx['a' + i] % 2) {
                f = 0;
                break;
            }
        }
        if (f == 0)
            puts("No");
        else {
            for (int i = 0; i < n; ++i) {
                if (a[i] != b[i]) {
                    int fac = 0;
                    for (int j = i + 1; j < n; ++j) {
                        if (a[i] == a[j]) { //1次交换就可以使当前位置满足要求
                            swap(b[i], a[j]);
                            v.push_back(j);
                            v1.push_back(i);
                            fac = 1;
                            break;
                        }
                    }
                    if (fac == 0) {
                        for (int j = i + 1; j < n; ++j) {
                            if (a[i] == b[j]) { //2次交换才能满足要求
                                swap(a[i + 1], b[j]);//不会索引到最后一个字符之后，因为最后位置的字符必定相等
                                v.push_back(i + 1);
                                v1.push_back(j);
                                swap(b[i], a[i + 1]);
                                v.push_back(i + 1);
                                v1.push_back(i);
                                break;
                            }
                        }
                    }
                }
            }
            printf("Yes\n");
            int sz = v.size();
            printf("%d\n", sz);
            for (int i = 0; i < sz; ++i) {
                printf("%d %d\n", v[i] + 1, v1[i] + 1);
            }
        }
    }
    return 0;
}

C. Tile Painting

题意：

n个格子，现在涂色。例如n的因子是2，则1和3的颜色相同，2和4的颜色相同。假设n的因子是3，则1和4的颜色相同，2和5的颜色相同。

分析：

打表可以发现，素数n的颜色为n（n>2），和数n（质因子仅一种，为a）颜色为a，和数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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1000000;
int prime[maxn + 1];
void is_p()
{
    for (int i = 2; i <= maxn; i++) {
        if (prime[i] == 0)
            prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && prime[j] <= maxn / i; j++) {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}
ll n;
ll ans;
int ispri(ll x)
{
    int sqx=(int)sqrtl(x);
    for(int i=2 ;i<=sqx;++i){
        if(x%i==0)
            return 0;
    }
    return 1;
}
int so()
{
    int r = 0;
    for (int i = 1; n > prime[i] && i <= prime[0]; ++i) {
        if (n % prime[i] == 0) {
            ans = prime[i];
            // printf("%dggn\n",prime[i]);
            ll z = n/prime[i];
            if (prime[i] !=z&&ispri(z))
                ++r;
            r++;
        }
    }
    return r;
}

int main()
{
    is_p();
    //printf("%d %d\n",prime[0],prime[78499]);
    cin >> n;
    if (n < 2)
        printf("1\n");
    else {
        int ji = so();
        //printf("%d\n",ji);
        if (ji > 1) {
            printf("1\n");
        } else if (ji == 1) {
            printf("%lld\n", ans);
        } else {
            printf("%lld\n", n);
        }
    }
    return 0;
}
0%