牛客算法周周练1题解

A Maximize The Beautiful Value

题意翻译

给出一个单调不减的数列 $\{a_n\}$ ，选择一个数 $a_i$ ，将其放置至 $a_1$ 至 $a_{i-k-1}$ 的任意一个位置 $a_j$ 中，并将 $a_j$ 到 $a_n$ 依次向后移动一位。

求 $\max \{\sum\limits_{i=1}^n{a_i\times i} \}$

题解

因为单调不减，所以越往前越吃亏，显然选择的这个数只会移动 $k$ 位。

设 $sum$ 为移动前的 $\sum\limits_{i=1}^n{a_i\times i}$ ，如果移动的位置为 $a_p(p > k)$ ，则有移动后的 $\sum\limits_{i=1}^n{a_i\times i}=sum-a_p\times(k+1)+\sum\limits_{j=p-k}^p{a_j}$

发现等式右边的 $\sum$ 可以前缀和处理。

所以从 $k+1$ 到 $n$ 扫一遍就行了。

时间复杂度 $O(n-k)$

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

const int maxn = 100007;

int T, n, k;
int a[maxn];
LL s[maxn];

void Init(void) {
    read(T);
}

void Work(void) {
    while(T--) {
        read(n); read(k);
        LL ans = 0ll, sum = 0ll;
        for(int i = 1; i <= n; i++) {
            read(a[i]);
            s[i] = s[i - 1] + (LL)a[i];
            sum = sum + (LL)a[i] * (LL)i;
        }
        for(int i = k + 1; i <= n; i++) ans = max(ans, sum - (LL)a[i] *(LL)i + (LL)a[i] * (LL)(i - k - 1) + s[i] - s[i - k - 1]);
        printf("%lld\n", ans);
    }
}

int main(void) {
    Init();
    Work();
    return 0;
}

B 身体训练

题解

考虑枚举每个人 $i$ 和出发时间 $j$ 。

可以得到答案为 $\sum {\dfrac{n\times u}{c_i-j\times d_i-v}}$

考虑到每个人的概率均为 $\dfrac{1}{n}$ ，则最后答案为 $\sum {\dfrac{u}{c_i-j\times d_i-v}}$

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

const int maxn = 1000 + 7;
double c[maxn], d[maxn], v, u, ans;
int n;

void Init(void) {
    scanf("%d%lf%lf", &n, &v, &u);
}

void Work(void) {
    for(int i = 1; i <= n; i++) scanf("%lf", &c[i]);
    for(int i = 1; i <= n; i++) scanf("%lf", &d[i]);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            ans += u / (c[i] - (j - 1) * d[i] - v);
        }
    }
    printf("%.3f\n", ans);
}

int main(void) {
    Init();
    Work();
    return 0;
}

C Borrow Classroom

题解

显然这道题和 LCA 有关。

我个人比较喜欢通过树剖的方式求 LCA。

可以通过求 $B,C$ 的LCA $K$ ，得到 $B,C$ 间的距离

然后对 $A,C$ 的 LCA 进行分类讨论。

如果 $A,C$ 的 LCA 为 1 ，那 A 就要跨过根，再多走一个，否则追到 LCA 就行了。

通过递送的时间和路程可以轻松判断是否可以追上。

E 幸运数字Ⅱ

题解

发现 $l,r$ 的值域比较大，不可能对于 $\forall i \in [l,r]$ ，求 $f(i)$ 的。

那么发现 $f(i)$ 的取值数量实际上很小，可以考虑每个 $f(i)$ 对答案的贡献。

令 $g(t)$ 为 $i \in [l,r]$ 中第 $t$ 小的 $f(i)$ 取值，设 $t \le m$ 。

则答案为 $\sum\limits_{i=2}^{m-1}{g(i) \times (g(i)-g(i-1))} + g(1) \times (g(1)-l+1)+g(m) \times (r-g(m-1))$

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

LL L, R;
LL que[100007];
int f, r;

void Init(void) {
    read(L); read(R);
}

void Work(void) {
    que[1] = 4ll, que[2] = 7ll;
    f = 1ll, r = 2ll;
    while(f <= r) {
        LL x = que[f]; f++;
        LL x4 = x * 10ll + 4ll, x7 = x * 10ll + 7ll;
        if(x4 <= R * 10ll + 10ll) que[++r] = x4;
        if(x7 <= R * 10ll + 10ll) que[++r] = x7;
    }
    sort(que + 1, que + r + 1);
    int posl, posr;
    for(int i = 1; i <= r; i++) {
        if(que[i] >= L) {
            posl = i;
            break;
        }
    }
    for(int i = r; i >= 1; i--) {
        if(que[i] < R) {
            posr = i;
            break;
        }
    }
    if(posr < posl) {
        LL ans = (R - L + 1) * que[posl];
        printf("%lld\n", ans);
        return ;
    }
    LL ans = 0;
    for(int i = posl + 1; i <= posr; i++) {
        ans = ans + que[i] * (que[i] - que[i - 1]);
    }
    ans += que[posl] * (que[posl] - L + 1) + que[posr + 1] * (R - que[posr]);
    printf("%lld\n", ans);
}

int main(void) {
    Init();
    Work();
    return 0;
}