Codeforces Round#585(Div2)部分题解

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

前言：会的题目笔者自己写，不会的题目笔者参考官方题解(顺便练习翻译，个人觉得翻译之后读起来比直接读英文舒服)

比赛链接

A

没啥好说的，直接暴力，codeforces传统艺能。
简述：最少的罚下人数很好确定，最多的罚下人数分类讨论一下即可。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000;
int a[maxn];
int main()
{
    // int n;
    // cin >> n;
    // for (int i = 0; i < n; ++i)
    //     scanf("%d", &a[i]);
    int a1,a2,k1,k2,n,o1,o2;
    cin>>a1>>a2>>k1>>k2>>n;
    int maxy=a1*(k1-1)+a2*(k2-1);
    // cout<<maxy;
    if(maxy>=n)
        o1=0;
    else 
        o1=n-maxy;
    if(k1>=k2)
    {
        if(k2*a2>=n)
            o2=n/k2;
        else 
        {
            o2=a2;
            n-=a2*k2;
            o2+=min(n/k1,a1);
        }
    }
    else 
    {
        if(k1*a1>=n)
            o2=n/k1;
        else 
        {
            o2=a1;
            n-=a1*k1;
            o2+=min(n/k2,a2);
        }
    }
    printf("%d %d\n",o1,o2);
    return 0;
}

B

题意：给出一个序列，确定有多少段的积是负数，多少段的积是正数。

做法：首先观察数据范围，很容易发现直接枚举起点终点不可行（然而我还是去试了两次，T飞），然后考虑其他做法。
用一个二维数组记录正数与负数出现的次数（注意，当出现负数时，记录方式有变），之后进行累加即可。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;

int n,a[200005];
ll f[200005][2],S1,S2;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        if(a[i]>0)
        {
            f[i][0]=f[i-1][0]+1;
            f[i][1]=f[i-1][1];
        }
        else
        {
            f[i][0]=f[i-1][1];
            f[i][1]=f[i-1][0]+1;
        }
    for(int i=1;i<=n;++i)
    {
        S1+=f[i][0];
        S2+=f[i][1];
    }
    std::cout<<S2<<' '<<S1<<std::endl;
    return 0;
}

C

题意：

两个长度相同的字符串，字符集为’a’,’b’,可以将字符串1中任意字符与字符串2中任一字符进行交换。问是否可以实现两字符串相同，如果可以，输出最少的操作步数及步骤，否则输出-1。

解法：

计算两个数组pos01和pos10。pos01包含所有满足s[x]=0+’a’,t[x]=1+’a’的位置x，类似地，pos10包含所有满足所有满足s[x]=1,t[x]=0的位置x。如果pos01和pos10的size各自除以2的余数不相等，则不能实现两字符串相同。
对于其他情况，我们应该暴力执行交换操作。在一次操作中，如果a和b在同一个数组中，我们可以使s[a]等于t[a]，s[b]等于t[b]。
如果pos01和pos10的数组大小都是偶数，我们只需要 (pos01.size()+pos10..size())/2 次操作，否则，有两个位置 x，y ，并且s[x]=0+’a’，s[y]=1+’a’ , t[x]=1+’a’, t[y]=0+’a’，我们需要进行两次操作：首先进行操作（x，x），之后进行操作（x，y）。

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;
typedef long long ll;
const int maxn = 200001;
char s1[maxn], s2[maxn];
vector<int> pos01, pos10;
vector<pair<int, int>> ans;
int main()
{
    int n;
    scanf("%d%s%s", &n, s1, s2);
    for (int i = 0; i < n; ++i)
    {
        if (s1[i] != s2[i])
        {
            if (s1[i] == 'a')
                pos01.push_back(i);
            else
                pos10.push_back(i);
        }
    }
    if (pos01.size() % 2 != pos10.size() % 2)
    {
        printf("-1\n");
    }
    else
    {
        int sz01 = pos01.size(), sz10 = pos10.size();
        for (int i = 0; i + 1 < sz01; i += 2)
        {
            ans.push_back(make_pair(pos01[i], pos01[i + 1]));
        }
        for (int i = 0; i + 1 < sz10; i += 2)
        {
            ans.push_back(make_pair(pos10[i], pos10[i + 1]));
        }
        if (sz01 % 2) // 已经保证了两个数组大小的奇偶性相同
        {
            int x = pos01.back();
            int y = pos10.back();
            ans.push_back(make_pair(x, x));
            ans.push_back(make_pair(x, y));
        }
        printf("%d\n", ans.size());
        int ans_sz = ans.size();
        for (int i = 0; i < ans_sz; ++i)
        {
            printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
        }
    }
    return 0;
}

D

题意：

0%