Educational Codeforces Round 60 (Rated for Div. 2) 解题报告

A. Best Subsegment

给定一串数列， 求区间最大平均值

显然，最大的区间平均值可以就是数列中最大的那个，然后基于最大的点想两边枚举区间长度

#include <cstdio>
#include <algorithm>

inline int Max(int a, int b){return a > b? a: b;}

const int N = 1e5 + 1e4;

int n, max, max_id, len, rig, max_len;
int a[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] > max)
            max = a[i];
    }
    for(int i = 1; i <= n; i++){
        if(a[i] == max && ( a[i - 1] != max || i == 1 ) ){
            rig = i; len = 0;
            while( a[rig] == a[i] && rig <= n ){
                rig++; len++;
            }
            max_len = Max(len, max_len);
        }
    }
    printf("%d", max_len);
}

B. Emotes

总共 $n$ 个表情， 你需要输出一个长度为 $m$ 的长度序列，但是同一个表情不能连续出现 $k$ 次

排个序，每个周期按，最大的出现 $k$ 次，然后出现一次第二大的，枚举周期即可

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 1e4;

int n, m, k, tmp;
long long ans;
int a[N];

bool cmp(int a, int b){
    return a > b;
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1, cmp);
    if( m <= k ){
        printf("%lld", 1LL * a[1] * m);
        return 0;
    }
    else {
        ans = 1LL * a[1] * k + (long long) a[2];
        ans *= (m / (k + 1) );
        m %= (k + 1);
        ans += 1LL * a[1] * m;
        printf("%lld", ans);
    }
}

C. Magic Ship

本来是到直接两点坐标差的绝对值之和就可以的

然后有洋流

我们设每一轮洋流为一个周期，然后二分最少需要多少周期

然后 $O(n)$ 判断不在整数周期内部的就可以

#include <cstdio>

inline long long Aabs(long long a){return a < 0? (0 - a): a;}

const long long N = 1e5 + 1e4;

long long x1, y1, x2, y2, dx, dy, n, tmp, ans, mid;
char str[N];

int main(){
    scanf("%lld%lld", &x1, &y1);
    scanf("%lld%lld", &x2, &y2);
    scanf("%lld", &n);
    scanf("%s", str + 1);

    for(long long i = 1; i <= n; i++){
        if(str[i] == 'U') dy++;
        if(str[i] == 'D') dy--;
        if(str[i] == 'L') dx--;
        if(str[i] == 'R') dx++;
    }

    long long left = 0, rig = (int)2e9;
    while(left <= rig){
        mid = (left + rig) >> 1;
        if( Aabs(x1 + dx * mid - x2) + Aabs(y1 + dy * mid - y2) <= n * mid ) rig = mid - 1;
        else left = mid + 1;
    }

    x1 += dx * rig;
    y1 += dy * rig;
    ans = n * rig;
    if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans){
        printf("%lld", ans);
        return 0;
    }

    for(long long i = 1; i <= n; i++){
        if(str[i] == 'U') y1++;
        if(str[i] == 'D') y1--;
        if(str[i] == 'L') x1--;
        if(str[i] == 'R') x1++;
        ans++;

        if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans ){
            printf("%lld", ans);
            return 0;
        }
    }
    printf("-1");
}