Codeforces Round #657 Div. 2

notes

	type	difficulty
1379A. cacius and String	violence , About strings	2
1379B. Dubious Cyrpto	About Mathematics	1
1379C. Choosing flowers	Sort	3

1379A. Acacius and String

solution ： violence

The question ： Give a length of n String , By lowercase letters and ‘？‘ form , Now we can put ’？‘ Replace , Ask if you can make the final result ’abacaba‘ Only once .

My thoughts ：

First, check the original string ‘abacaba’ Several times , Record as already

If already>1, Output no

If already=1, hold ’？‘ Replace with ’d’, Then the output

If alrady=0, It is found that it can be successfully replaced with ”abacaba“ The location of , Just take the rest ‘？’ become ‘d’, Then the output .

Now wa 了 ,wa Why ：

It is found that it can be successfully replaced with ”abacaba“ The location of , It should be checked whether the replacement can guarantee already by 1, And then output .

After correction ac The code is as follows

#include "bits/stdc++.h"
using namespace  std;
string ss,tem;
int n;
const char standard[]="abacaba";
int check(string ff)
{
    int cnt=0;
    for(int d=0;d+6<n;++d)
    {
        int suc=1;
        for(int k=0;k<=6;++k)
            if(standard[k]!=ff[d+k]){suc=0;
                break;}
        if(suc)++cnt;
        if(cnt>1)return cnt;
    }
    return cnt;
}
int possible(int i)
{
    for(int k=0;k<=6;++k)
    {
        if(ss[i+k]=='?')continue;
        if(ss[i+k]!=standard[k])return 0;
    }
    return 1;
}
int main()
{
//    freopen("in.text","r",stdin);

    int cas;
    scanf("%d",&cas);
    while (cas--)
    {
        cin>>n>>ss;

        int already=check(ss);
        if(already>1)
        {
            printf("No\n");
            continue;
        }
        else if(already==1)
        {
            printf("Yes\n");
            for(int i=0;i<n;++i)if(ss[i]=='?')ss[i]='d';
            cout<<ss<<endl;
        }
        else if(already==0)
        {
            int suc=0;
            for(int i=0;i+6<n;++i)
                if(possible(i)){
                    tem=ss;
                   for(int d=0;d<=6;++d)tem[i+d]=standard[d];
                    if(check(tem)==1)
                    {
                        suc=1;
                        for(int d=0;d<n;++d)if(tem[d]=='?')tem[d]='d';
                        break;
                    }

                    }
            if(suc)cout<<"Yes"<<endl<<tem<<endl;
            else cout<<"No"<<endl;
            }
        }


    return 0;
}

1379C Choosing flowers

The question ： Yes m grow flowers , The happiness of buying a bunch of flowers is $a_i$, buy k The happiness of a bouquet of flowers is $a_i+(k-1)b_i$ , Now I want to buy n Bouquet of flowers , Ask the maximum happiness value .

Ideas ：

There must be many answers a Attribute flowers and 1 Kind of b Attribute flower ,why？

Let's assume that there are many kinds of a Attribute flower , and $b_1,b_2$, Then if $b_1$ Greater than $b_2$, Since infinity , Why? $b_2$ Well .

Then choose by enumerating $b_i$ grow flowers , Must be greater than $b_i$ Of a flowers , So use the prefix and calculate in advance .

Algorithm ：

1. Press... On the flowers a Attribute value ordering jiejing

2. enumeration $b_i$, Two points Find out how many are greater than $b_i$ Of $a_i$, Add the corresponding prefix and .

   The complexity of the algorithm is $O(m\ast log（m))$

#include "bits/stdc++.h"
using namespace  std;
typedef  long long ll;
const int MAXN=1E5+10;
struct re{
    ll a,b;
    re(ll k1=0,ll k2=0): a(k1),b(k2){}
    bool operator< (const re &it)const
    {
        return a>it.a;
    }
};
re flower[MAXN];
ll presum[MAXN];
int main()
{
//    freopen("in.text","r",stdin);

    int cas,n,m;
    scanf("%d",&cas);
    while (cas--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;++i)scanf("%lld %lld",&flower[i].a,&flower[i].b);
        
        sort(flower+1,flower+1+m);

        presum[0]=0;
        for(int i=1;i<=m;++i)presum[i]=presum[i-1]+flower[i].a;
        

       ll ans=0;
        for(int i=1;i<=m;++i)
       {
           int xu=upper_bound(flower+1,flower+1+m,re(flower[i].b,0) )-flower-1;
           ll now;
           if(xu>=n){ now=presum[n];;}
           else if(xu<i)
           {
               now=presum[xu]+flower[i].a+(n-1-xu)*flower[i].b;
           } else if(xu>=i)
           {
               now=presum[xu]+(n-xu)*flower[i].b;
           }

           ans=max(now,ans);
       }
        printf("%lld\n",ans);
    }
}