2021-03-02-3月2日题解

Codeforces Global Round 13

C题

题解

贪心，Pekora 一定从第一个开始跳，直到把第一个变为1，然后跳到第2个，这样能够达到最优解。

在把一个位置为i且高度为cur的蹦床变为1时，从[i+2,cur+i]这个区间内所有蹦床的高度将减少1。

如果位置i的蹦床高度已经为1，则应当转移到第i+1个上。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[6000]={0},cur[6000]={0};
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            cur[i]=0;
        }
        ll ans=0;
        for(ll i=1;i<=n;i++)
        {
            ll now=cur[i];
            if(now<a[i]-1)
            {
                ans+=a[i]-now-1;
                now+=a[i]-now-1;
            }
            cur[i+1]+=now-a[i]+1;  ///多出来的跳到下一个
            for(ll j=i+2;j<=min(n,i+a[i]);j++)
                cur[j]+=1;
        }
        printf("%lld\n",ans);
    }
}

D题

题解

容易发现如果一个数u二进制某一位为1，则可以且一个其余全为0，只有该位置为1的另一个数v并且结果依然为v，将v加到u上便可以把u的1前移一位，用前缀和模拟这个过程即可。

代码

#include <stdio.h>
using namespace std;
int a[50]={0};
int b[50]={0};
int sum1[50]={0};
int sum2[50]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long u,v;
        scanf("%lld%lld",&u,&v);
        if(v<u)
        {
            printf("NO\n");
            continue;
        }
        for(int i=1;i<=40;i++)
        {
            a[i]=u%2,u/=2;
            sum1[i]=sum1[i-1]+a[i];
        }
        for(int i=1;i<=40;i++)
        {
            b[i]=v%2,v/=2;
            sum2[i]=sum2[i-1]+b[i];
        }
        int flag=1;
        for(int i=1;i<=40;i++)
        {
            if(sum1[i]<sum2[i])
                flag=0;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
}