Educational Codeforces Round 53

Eric20521 · 2019-08-11 15:30:16 · 个人记录

A. Diverse Substring

只要找到挨着的两个不同字符便可以了

    if(s[i]!=s[i-1]){
        cout<<"YES"<<endl<<s[i-1]<<s[i];
        return 0;
    }

B. Vasya and Books

每个时刻都一定有一个分界线，一侧是放入的，一侧是未放入的记录这个分界线就可以了。

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        c[a[i]]=i;//编号对应位置
    }
    int t=0;    
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        int p=c[b[i]];
        printf("%d",max(0,p-t));
        cout<<" ";
        t=max(t,p);//分界线
    }

    return 0;

C - Vasya and Robot

可使用二分答案

预处原指令横纵坐标移动效果的前/后缀和

bool check(int l){
    for(int i=1;i+l-1<=n;i++){//枚举修改部分
        int temp=abs(x-px[i-1]-sx[i+l])+abs(y-sy[i+l]-py[i-1]);//不修改部分的移动结果
        if(temp<=l&&(l-temp)%2==0){//来得及弥补且能正好回到位置
            return 1;
        }
    }
    return 0;
}

D. Berland Fair

肯定要找规律，所以想到一圈一圈周期形式。

考虑到不能买的糖只会增加不会减少且不会变化，每次转一圈记录买下的糖数和花费，看这样的圈能转几圈，计算后重新转一圈进行记录，直至一圈下来一颗糖也买不到。

    cin>>n>>t;

    for(int i=1;i<=n;i++){
        cin>>a[i];

    }
    ll ans=0;
    while(1){

        ll cnt=0,s=0;
        for(int i=1;i<=n;i++){
            if(s+a[i]<=t){
                s+=a[i];cnt++;
            }
        }
        if(s==0)break;
        ans+=cnt*(t/s);
        t%=s;
    }
    cout<<ans;