Codeforces Round #377 (Div. 2)A,B,C,D【二分】

PS：这一场真的是上分场，只要手速快就行。然而在自己做的时候不用翻译软件，看题非常吃力非常慢，还有给队友讲D题如何判断的时候又犯了一个毛病，一定要心平气和，比赛也要保证，不要用翻译软件做题；

Codeforces732A

水题；

#include<cstdio>

#include<math.h>

#include<queue>

#include<map>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int tmp;

    for(int i=0;;i++)

    {

        tmp=i*10;

        if(tmp%n==0&&tmp)

        {

            printf("%d\n",tmp/n);

            return 0;

        }

        tmp+=m;

        if(tmp%n==0)

        {

            printf("%d\n",tmp/n);

            return 0;

        }

    }

}

Codeforces 732B.
Cormen — The Best Friend Of a Man

求一个最少数量，使得连续两个是>=k

保证b[i]>=a[i];

我肯定是加中间的，加中间的话两边都能利用，而且一定要加；

#include<cstdio>

#include<math.h>

#include<queue>

#include<map>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

const int N=5e2+10;

int a[N];

int b[N];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    int tmp,flag=0,ans=0;

    b[1]=a[1];

    for(int i=2;i<=n;i++)

    {

        tmp=b[i-1]+a[i];

        if(tmp>=m)

            b[i]=a[i];

        else

        {

            b[i]=m-b[i-1];

            ans+=b[i]-a[i];

        }

    }

    printf("%d\n",ans);

    for(int i=1;i<=n;i++)

    {

        if(i!=1) printf(" ");

        printf("%d",b[i]);

    }

    return 0;

}

Codeforces 732C
- Sanatorium

最大和最小的数量<=1就一定能全部进行结束，所以求一个最大，保证和最大的差值<=1就好了；

#include<cstdio>

#include<math.h>

#include<queue>

#include<map>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef __int64 LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

LL a[4];

int main()

{

    LL mx;

    scanf("%I64d",&a[1]);

    mx=a[1];

    for(int i=2;i<=3;i++)

    {

        scanf("%I64d",&a[i]);

        mx=max(a[i],mx);

    }

    LL ans=0;

    for(int i=1;i<=3;i++)

    {

        if(a[i]+1>=mx)

            continue;

        ans+=mx-1-a[i];

    }

    printf("%I64d\n",ans);

    return 0;

}

Codeforces 732D

只要二分一个答案，然后判断满不满足就行了，判断的时候倒着判断，开了两个值代表需要准备的天数，已经准备的天数维护一下就好了；

#include<cstdio>

#include<iostream>

#include<string.h>

#include<algorithm>

using namespace std;

const int N=1e5+10;

int a[N],w[N];

bool vis[N];

int m;

bool Judge(int n)

{

    int sum,x,y,num;

    memset(vis,false,sizeof(vis));

    x=y=num=0;

    for(int i=n;i>=1;i--)

    {

        if(!a[i])

        {

            if(x>y)

                y++;

        }

        else

        {

            if(vis[a[i]])

            {

                if(x>y)

                    y++;

            }

            else

            {

                num++;

                x+=w[a[i]];

                vis[a[i]]=true;

            }

        }

        if(x==y&&num==m)

            return true;

    }

    return false;

}

int solve(int n)

{

    int left=1,right=n;

    while(left<right)

    {

        int mid=left+(right-left)/2;

        if(Judge(mid))

            right=mid;

        else

            left=mid+1;

    }

    return left;

}

int main()

{

    int n;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    for(int i=1;i<=m;i++)

        scanf("%d",&w[i]);

    if(!Judge(n))

    {

        puts("-1");

        return 0;

    }

    int ans;

    ans=solve(n);

    printf("%d\n",ans);

    return 0;

}

巴特西

Codeforces Round #377 (Div. 2)A,B,C,D【二分】

最新文章

热门文章