Educational Codeforces Round 86 (Div. 2) – Zechel

A. Road To Zero

给两个数x,y,通过a,b两种操作使x,y都归为0,求总花费。对于1和1,我们可以分别执行一次a操作,也可以只执行一次b操作,就使二者归为0。为了尽可能的用更少的钱,如果b<2*a,那么我们就采用第二种,否则使用第一种方法。这样,我们就可以使不相同的x,y的中一个数先变为0。当只剩一个数不为零时,我们只能采用a类型操作,花费是固定的。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
   ios::sync_with_stdio(false);
   int t;
   cin>>t;
   while(t--)
   {
       long long x,y,a,b;
       cin>>x>>y>>a>>b;
       long long ans=0;
       if(x==0&&y==0)ans=0;
       else if((x==0&&y!=0)||(y==0&&x!=0))
       {
           if(x==0)ans=ans+y*a;
           else ans=ans+x*a;
       }
       else
       {
            if(b<2*a)
            {
                long long big=max(x,y),sma=min(x,y);
                ans=ans+sma*b+(big-sma)*a;
            }
            else
            {
                ans=ans+(x+y)*a;
            }
       }
       cout<<ans<<endl;
   }
}

B.Binary  Period

题意大致是给出一段子串,在不改变子串原有顺序的情况下,插入‘0’或‘1’来得到原串,同时,要使原串的满足,其中任意一个字符与其前面第k个字符相同,且k需要最小。

该子串最大的特点是其只由0和1组成,所以,如果子串全为0或1,则其原串显然当k为 1 合题,故直接输出即可。当子串中既有1也有0时,那么k必然不能等于1。如果要k=2,则原串中任意一个字符必须和其前后的字符不同,所以我们只需要补充子串,使得到的原串0和1相间即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string t;
        cin>>t;
        int u=t.length();
        char p=t[0];
        int check=0;
        for(int j=0;j<u;j++)
        {
            if(p!=t[j])
            {
                check=1;
                break;
            }
        }
        if(!check)cout<<t<<endl;
        else
        {
            for(int i=0;i<u;i++)
            {
                cout<<t[i];
                if(i!=u-1&&t[i]==t[i+1])
                {
                    if(t[i]=='1')cout<<'0';
                    else cout<<'1';
                }
            }
            cout<<endl; 
        }
    }
}

C. Yet Another Counting Problem

要找到区间 l , r 内有多少x满足等式(x%a%b)!=(x%b%a)  。我们可以用前缀和来记录 1 到 i 中有多少个满足题意的x,记为Q[i]。可以发现规律,每间隔为a*b内的区间内 x的数量是固定的。所以我们只需要记录[1,a*b]内的Q[i],然后通过规律算出r,l的Q[r],Q[l],再相减即可。注意最后需要特判一下 l 是否满足,如果满足则加1。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
vector<ll>Q;
ll cul(ll x,int mod)
{
    ll ans=x/mod*Q[mod]+Q[x%mod];//根据规律计算 Q[x]
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll a,b,q;
        scanf("%lld %lld %lld",&a,&b,&q);
        Q.resize(a*b+1,0);
        for(int i=1;i<=a*b;i++)
        {
            if((i%a%b)!=(i%b%a))Q[i]=Q[i-1]+1; 
            else Q[i]=Q[i-1];                //计算前缀和
        }
        while(q--)
        {
            ll r,l;
            scanf("%lld %lld",&l,&r);
            cout<<cul(r,a*b)-cul(l,a*b)+((l%a%b)!=(l%b%a))<<" "<<endl;
        }                                  //特判 l 是不是满足题意
        cout<<endl;
    }
}

 

发表评论

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

川公网安备 51130202000337号