Codeforces Round #585 (Div. 2)

B: https://codeforces.com/contest/1215/problem/B

题意:

给出一个序列，每个数要么是负数要么是正数，问你总共有多少[l,r]大于0，有多少[l,r]小于0？

题解：

O(n)遍历；
每次遇到正数，正数++；
每次遇到负数，将正数和负数swap，负数++
每次累加目前负数和正数的个数。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int x;
    ll n ,k,sum = 0,ans = 0,cnt1 = 0,cnt0 = 0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        sum += i;
        scanf("%d",&x);
        if(x > 0)
            cnt1++;
        else{
            k = cnt0;
            cnt0 = cnt1;
            cnt1 = k;
            cnt0++;
        }
        ans += cnt1;
    }
    cout<<sum-ans<<" "<<ans<<endl;
    return 0;
}

C：https://codeforces.com/contest/1215/problem/C

题意：

给出俩个长度相同并且只包含'a'和'b'的字符串，每次可以选择第一个字符串的任意一个字母和第二个字符串任意一个字母进行交换，最少需要几次可以使得俩个字符串完全相同，如果不存在输出-1

题解：

考虑俩个字符串对应位置上如果要交换，肯定是'ab'或者'ba'，记录ab的个数k1和ba的个数k2。
如果和为奇数，肯定无解，输出-1
如果和为偶数，肯定有解；
考虑k1和k2分别为奇数和偶数的情况，
如果都是偶数，结果就是(k1+k2）/2，直接让'ab'和'ab'交换或者'ba'和'ba'交换。
如果都是奇数，结果就是(k1/2+k2/2+2),最后多的俩个是'ab'和'ba'进行交换，需要俩步

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 200005;
char s1[maxx],s2[maxx];
int pos1[maxx],pos2[maxx];
int main()
{
    int n,cnt1 = 0,cnt = 0,cnt2 = 0;
    scanf("%d",&n);
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    for(int i=1;i<=n;i++)
    {
        if(s1[i] != s2[i]){
            cnt++;
            int k1 = s1[i]-'a',k2 = s2[i]-'a';
            if(k1 == 0)
                pos1[++cnt1] = i;
            else
                pos2[++cnt2] = i;
        }
    }
    if(cnt%2){
        printf("-1\n");
        return 0;
    }
    if(cnt1 % 2)
    {
        cout<<cnt1/2 + cnt2/2 + 2<<endl;
        for(int i=1;i<=cnt1-1;i+=2)
            printf("%d %d\n",pos1[i],pos1[i+1]);
        for(int i=1;i<=cnt2-1;i+=2)
            printf("%d %d\n",pos2[i],pos2[i+1]);
        printf("%d %d\n",pos1[cnt1],pos1[cnt1]);
        printf("%d %d\n",pos1[cnt1],pos2[cnt2]);
    }
    else{
        cout<<cnt/2<<endl;
        for(int i=1;i<=cnt1;i+=2)
            printf("%d %d\n",pos1[i],pos1[i+1]);
        for(int i=1;i<=cnt2;i+=2)
            printf("%d %d\n",pos2[i],pos2[i+1]);
    }
    return 0;
}

D：https://codeforces.com/contest/1215/problem/D

题意：

给出一个字符串，长度是偶数，每个字母只能是'0'-'9'和'?'，'?'的个数是偶数。
博弈游戏，A先手，B后手，每个人选择一个'?'替换成任意一个'0'-'9'的数字。
最后如果字符串的前半部分和后半部分相等，则B胜，否则A胜

题解：

遍历字符串，前半部分已知数字和 = sum1 ,前半部分'?'个数 = cnt1
前半部分已知数字和 = sum2,前半部分'?'个数 = cnt2
(1)如果cnt1 = cnt2 如果sum1 = sum2 B只要保证每次在A相反的位置上放一样的数，左右肯定一样，B获胜
如果sum1 != sum2 A只要保证在大的一段每次都放9，左右肯定最后不一样，A获胜
(2)如果cnt != cnt2 ,我们可以多写几个样例找一下规律
对于A，肯定想让左右俩边差值尽量的大,就会在一侧只放0，另一侧只放9

????08->结果是A赢最后肯定会是 900 008
????91->结果是A赢最后情况是 099 991
????09->结果是B赢最后情况是 009 009 或者 909 909

推出结论-> sum1-sum2 == 9*(cnt1-cnt2)/2 则B获胜，否则A获胜
记得判断cnt1 cnt2的大小

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 200005;
int n;
char s[maxx];
string B = "Bicarp";
string M = "Monocarp";
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    int cntl,cntr,suml,sumr;
    cntl = cntr = suml = sumr = 0;
    for(int i=1;i<=n;i++)
    {
        if(i <= n/2){
            if(s[i] == '?')
                cntl++;
            else
                suml += s[i]-'0';
        }else{
            if(s[i] == '?')
                cntr++;
            else
                sumr += s[i]-'0';
        }
    }
    if(cntl == cntr){
        if(suml == sumr){
            cout<<B<<endl;
        }else{
            cout<<M<<endl;
        }
        return 0;
    }
    if(cntl > cntr){
        if(sumr-suml == 9*(cntl-cntr)/2)
           cout<<B<<endl;
        else
           cout<<M<<endl;
        return 0;
    }
    if(cntr > cntl){
        if(suml-sumr == 9*(cntr-cntl)/2)
            cout<<B<<endl;
        else
            cout<<M<<endl;
    }
    return 0;
}