CF-1111 (2019/2/7 补)

CF-1111

A. Superhero Transformation

tags : strings

#include <bits/stdc++.h>

using namespace std;

char s[5] = {'a','e','i','o','u'};

bool check(char t){

    for(int i=0;i<5;i++){

        if(t == s[i])

            return true;

    }

    return false;

}

int main(){

    string a,b;

    cin>>a>>b;

    int la = a.length();

    int lb = b.length();

    if(la!=lb){

        puts("No");

        return 0;

    }

    else{

        for(int i=0;i<la;i++){

            bool f1 = check(a[i]);

            bool f2 = check(b[i]);

            if((f1&&f2)||(!f1&&!f2)){

                continue;

            }

            else{

                puts("No");

                return 0;

            }

        }

    }

    puts("Yes");

    return 0;

}

B. Average Superhero Gang Power

tags:brute force
（一开局就想了个假算法，wa了n发，楞是没想到O(n)暴力

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,k,m;

ll a[1000100];

ll sum[1000100];

//num为删除的个数

double calc(int num){

    ll s;

    if(num>0)

    s = sum[n-1]-sum[num-1];

    else s = sum[n-1];

    s += min((m-num),(n-num)*k);

    return (double)s/(n-num);

}

int main(){

    scanf("%lld%lld%lld",&n,&k,&m);

    for(int i=0;i<n;i++){

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

    }

    sort(a,a+n);

    sum[0] = a[0];

    for(int i=1;i<n;i++)sum[i] = sum[i-1]+a[i];

    double ans = 0;

    //枚举剩余个数

    for(int i=max(1ll,n-m);i<=n;i++){

        ans = max(ans,calc(n-i));

    }

    printf("%.18f\n",ans);

    return 0;

}

C. Creative Snap

分治算法
考虑区间[l,r]，二分求出区间内复仇者数量num。
- 若num==0，则返回A
- 否则
  - 若l==r，则返回B*num
  - 否则，返回：min(B*num*(r-l+1),calc(l,mid)+calc(mid+1,r))
复杂度为：O(n*k*log(k))

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,k,A,B;

ll a[100010];

ll calc(int l,int r){

    ll num = upper_bound(a,a+k,r) - lower_bound(a,a+k,l);

    if(num==0){

        return A;

    }

    else {

        if(r==l)return num*B;

        ll mid = (l+r)/2;

        return min(B*(r-l+1ll)*num,calc(l,mid)+calc(mid+1,r));

    }

}

int main(){

    scanf("%lld%lld%lld%lld",&n,&k,&A,&B);

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

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

    sort(a,a+k);

    ll ans = calc(1,1<<n);

    cout<<ans<<endl;

    return 0;

}

D. Destroy the Colony

待补

E. Tree

待补

巴特西

CF-1111 (2019/2/7 补)

CF-1111

A. Superhero Transformation

B. Average Superhero Gang Power

C. Creative Snap

D. Destroy the Colony

E. Tree

最新文章

热门文章