Codeforces585#div.2(D.Ticket Game)

原题链接:https://codeforces.com/contest/1215/problem/D

博弈(很水),但第一次做这种类型题 :yiwen:

题意:两人依次在?填入0-9,若能使前一半和等于后一半的和则Bircarp赢,否则Monocarp赢。

Monocarp先手

思路:左右两半的?相等的抵消,剩下的根据两边左右大小和剩余?个数判断谁会赢

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    char s[200010];
    scanf("%d",&n);
    scanf("%s",s);
    int op1=0,op2=0;
    int cnt1=0,cnt2=0;
    for(int i=0;i<n;i++)
    {
        if(i<n/2)
        {
            if(s[i]=='?')
            {cnt1++;}
            if(s[i]!='?')
            {op1+=(int)(s[i]-'0');}
        }
        else
        {
            if(s[i]=='?')
            {cnt2++;}
            if(s[i]!='?')
            {op2+=(int)(s[i]-'0');}
        }
    }
    if((cnt1+cnt2)==0)
    {
        if(op1==op2)
        {printf("Bicarp\n");}
        else
        {printf("Monocarp\n");}
    }
    if(cnt1==cnt2&&cnt1+cnt2!=0)
    {
        if(op1==op2)
        {printf("Bicarp\n");}
        if(op1!=op2)
        {printf("Monocarp\n");}
    }
    if(cnt1>cnt2)
    {
        int ans=cnt1-cnt2;
        if(op1>=op2)
        {printf("Monocarp\n");}
        if(op1<op2)
        {
            int kk=op2-op1;
            if(ans%2==0)
            {
                if((ans/2)*9==kk)
                {printf("Bicarp\n");}
                else
                {printf("Monocarp\n");}
            }
            if(ans%2!=0)
            {printf("Monocarp\n");}
        }
    }
    if(cnt1<cnt2)
    {
        int ans=cnt2-cnt1;
        if(op2>=op1)
        {printf("Monocarp\n");}
        if(op2<op1)
        {
            int kk=op1-op2;
            if(ans%2==0)
            {
                if((ans/2)*9==kk)
                {printf("Bicarp\n");}
                else
                {printf("Monocarp\n");}
            }
            if(ans%2!=0)
            {printf("Monocarp\n");}
        }
    }
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注