educational codeforces round 127(Div.2)

Educational Codeforces Round 127 (Rated for Div. 2)，咕了有点久了，现在开写题解。

A. String Building

题目描述

题目分析

分析字符串是否能由aa,aaa,bb,bbb组成，给定字符串只含有a和b，很简单，就看看有没有单独存在的a或者b即可

标程

#include<bits/stdc++.h>
using namespace std;
char s[100005]; 
void solve(){
    scanf("%s",s);
    int len=strlen(s);
    int ans=1;
    if(len==1){
        puts("NO");
        return ;
    }
    s[len++]='c';
    for(int i=1;i<len;i++){
        if(s[i]==s[i-1]){
            ans++;
        }
        else{
            if(ans==1){
                puts("NO");
                return ;
            }
            ans=1;
        }
    }
    
    puts("YES");
    
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

B. Consecutive Points Segment

题目描述

题目分析

在数轴上放若干个点，每个点可以左移或者右移一个单位，或者不移，判断最后所有点能否在整数集合内连续。只考虑最左边和最右边的点，不难发现，若能连续，则满足a[n]-a[1]=n-1，我们就看最外两个点能否达到这个约束。若左边点右移，右边点左移则可以使得间距缩小2，因此若原本距离超过了n+1则一定不行。

标程

#include<bits/stdc++.h>
using namespace std;
int a[200005]; 
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //printf("%d %d\n",a[n]-a[1],n);
    if(a[n]-a[1]>n+1){
        puts("NO");
    }
    else{
        puts("YES");
    }
    
    
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

C. Dolce Vita

题目描述

题目分析

这题很有意思。给你n个商店和每天 $k$ 枚金币，每个商店只每天卖一个糖果包，每天涨价一块。问经过很多天后你最多能买到多少，并且它告诉你了最后一定有一天你一个糖果包也买不了。

首先不难得出，我肯定要从最小的糖果开始买买到不能买为止才是最优的解。因此先排个序肯定没错，然后求出前缀和 $sum[i]$表示买 $i$ 个糖果的最小花费。这里因为天数不确定很可能要过超过 $10^9$ 天，因此我们不能从天数上循环，我们就推从能买 $i$ 个物品到 $i-1$ 个物品过了多少天，假设过了 $q$ 天，那么这几天的收益就是 $q*i$。

那么假设今天是x天，我能买j件物品，我们能持续买j件物品的天数就是 $ceil((double)(x-sum[j])/j-i)+!((x-sum[j])%j)$。推出表达式之后其实整个程序也就不难写了，先二分出第0天的位置然后往前一件一件数即可，最后不要忘了开 $long\ long$，可恶，没准我开了就蓝名了。

标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int sum[200005];
void solve(){
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    sum[0]=0;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    int i=0,ans=0;
    int cnt=upper_bound(sum,sum+1+n,x)-sum-1;
    //printf("I can choose %d pack\n",cnt);
    for(int j=cnt;j>=1;j--){
        //printf("today is %d-th day\n",i);
        int after= ceil((double)(x-sum[j])/j-i)+!((x-sum[j])%j);
        i+=after;
        //printf("I can buy until %d\n",i);
        ans+=j*after;
    }
    printf("%lld\n",ans);
    
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

D. Insert a Progression

题目描述

题目分析

在数列中插入x个数，使得 $\sum {i=1}^{n+x-1}|a_i^{‘}-a{i-1}^{‘}|$ 最小。不难发现如果我插入的数在两个数之间，那么插入这个数对结果没有影响。若数列的最小值和最大值包括的部分那些数插入中间对答案没有影响，若剩余其它数则插在两边，至于插在哪边可以min一下。

这里当时看错题目了，以为每个数之间只能插入一次吗，导致后面卡了很长时间。

标程

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
void solve(){
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int max_x=a[1],min_x=a[1],ans=0;
    for(int i=2;i<=n;i++){
        ans+=abs(a[i]-a[i-1]);
        max_x=max(max_x,a[i]);
        min_x=min(min_x,a[i]);
    }
    ans+=min((min_x-1)*2,min(abs(a[1]-1),abs(a[n]-1)));
    if(x>max_x){
        ans+=min((x-max_x)*2,min(abs(x-a[1]),abs(x-a[n])));
    }
    cout<<ans<<endl;
    
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

结果：

1595分，加油上蓝！！！