Educational Codeforces Round 148 (Rated for Div. 2)

A. New Palindrome

map<int,int>mp;
void solve(){
    string s;
    mp.clear();
    cin>>s;
    for(int i=0;i<s.size()/2;i++){
        mp[s[i]]++;
    }
    puts(mp.size()>=2?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Maximum Sum

#define int long long
int a[N],l[N],r[N];
void solve(){
    int n=read(),k=read(),sum=0,ans=INF;
    for(int i=1;i<=n;i++)a[i]=read(),sum+=a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=k;i++)
        l[i]=l[i-1]+a[i*2-1]+a[i*2];
    for(int i=1;i<=k;i++)
        r[i]=r[i-1]+a[n-i+1];
    for(int i=0;i<=k;i++)
        ans=min(ans,l[i]+r[k-i]);
    cout<<sum-ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Contrast Value

int a[N],d[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int ans=1,fl=0;
    for(int i=2;i<=n;i++){
        d[i]=a[i]-a[i-1];
        if(fl==0){
            if(d[i]<0)fl=-1,ans++;
            if(d[i]>0)fl=1,ans++;
        }else if(fl==1){
            if(d[i]<0)fl=-1,ans++;
        }else if(fl==-1){
            if(d[i]>0)fl=1,ans++;
        }
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D1&&D2. Red-Blue Operations

首先关于k<=n的情况采用a[1]+k,a[2]+(k-1),a[3]+(k-2)...的贪心策略使最小值最大

如果k>n,也显然是对k的奇偶性讨论

k为偶数的时候，在前(k-n)次的操作可以进行(k-n)/2次-1操作，最后进行n次的上述贪心操作

k为奇数的时候，在k为偶数的基础上不对a[n]进行操作

至于要在哪进行减1操作，我们用计算总值的平均数和对最小值的操作方式，在两个值中取更小值

#define int long long
void solve(){
    int n=read(),q=read(); 
    vector<int>a(n),f(n+1,inf);
    for(int i=0;i<n;i++)  a[i]=read();
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++){
        f[i+1]=min(f[i]+1,a[i]+1);
    }
    int sum=accumulate(a.begin(),a.end(),0ll);
    while(q--){
        int k=read(),ans;
        if(k<n)cout<<min(f[k],a[k])<<' ';
        else {
            int s=sum;
            if((k-n)%2==0){
                ans=f[n]+k-n;
                s+=n*(k+k-n+1)/2-(k-n)/2;
            }else{
                ans=min(a[n-1],f[n-1]+k-(n-1));
                s+=(n-1)*(k+k-n+2)/2-(k-n+1)/2;
            }
            ans=min(ans,s>=0?s/n:(s-n+1)/n);
            cout<<ans<<' ';
        }
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}