A - Maximize The Beautiful Value

tags: 贪心、前缀和、推公式

分析

题目说明了是不降的序列，所以低于答案的贡献 $i *a[i]$ 必定是越大的数字在后面越好，我们可以考虑如果枚举 $[k+1, n]$ 数字，让他们都往前移动 $k$ 位，取最大的值。

本题难点在于如何移动进行计算，如果暴力计算的话复杂度为 $O(n^2)$ 。我们设原答案为 $ans_0$ ，选择的是第 $x$ 个数字 $k + 1\leq x\leq n$ ，观察数列变化，返现对于答案的贡献 $\sum_{i=1}^{i\leq x-1} i *a[i]$ 是不变的， $\sum_{i=x+1}^{i\leq n} i *a[i]$ 的结果每一项都加上了 $a[i]$ 。所以可以维护前缀和，取得这一部分的区间和。

时间复杂度 $O(n)$

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int const maxn = 1e5 + 10;
ll a[maxn];
int n, k;
ll pre[maxn];

int main(void) {
    FAST_IO;

    int t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        ll first = 0;
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pre[i] = pre[i - 1] + a[i];
            first += a[i] * i;
        }
        for (int i = k + 1; i <= n; i++) {
            int x = i;
            int l = i - k;
            int r = i - 1;
            ll p = first - i * a[i] + a[i] * l;
            p += pre[r] - pre[l - 1];
            ans = max(p, ans);
        }
        cout << ans << endl;        
    }

    return 0;
}

B- 身体训练

tags: 数学

分析

因为概率相等，所以直接从第 $i$ 个开始枚举，计算总和。然后 $ans / n$

时间复杂度 $O(n^2)$

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int const maxn = 1e5 + 10;

int main(void) {
    FAST_IO;

    int n;
    double v, u;
    cin >> n >> v >> u;
    vector<double> c(n), d(n);
    for (auto &x : c) cin >> x;
    for (auto &x : d) cin >> x;
    double ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans += n * u / (c[i] - j * d[i] - v);
        }
    }
    cout <<fixed << setprecision(3) << ans / (n * 1.0) << endl;
    return 0;
}

C - Borrow Classroom

tags：图论、LCA

分析

对于何老师拦截的方案，可以简化为两种：

何老师在节点1出等待
何老师中途和同学相遇

那么设 $B->C->1$ 的最短距离为 $disq$ , $A->1$ 的距离为 $dish$ 。

当 $disq>dish$ ，因小Q还未到达节点1，所以老师必定可以在A点等待
当 $disq<dish$ ，老师没有小Q走的快，必定拦截
当：
- 如果 $lca(C,A)=1$ ，那么C和A分别属于节点 $1$ 的两个子树，不定不会相遇，无法拦截
- 如果 $lca(C,A)!=1$ ，因为 $disq=dish$ ，所以从必定会在LCA处相遇

本题需要快速查询，所有最短距离可以通过LCA进行。
复杂度 $O(nlogn)$

PS：本题T组输入有坑，wa了10次，从 $tarjan$ 到 $倍增$ ，最后发现 $dep$ 数组没有清空，真的坑QWQ。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int const maxn = 1e5 + 10;
int vis[maxn];

struct node {
    int v, next;
}e[maxn << 1];
int head[maxn];

int fa[maxn][25];
int dep[maxn], cnt;
int n;

void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
void init() {
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(dep, 0, sizeof(dep));
    memset(fa, 0, sizeof(fa));
    cnt = 0;
}

void dfs(int u, int v) {
    if (vis[u]) return;
    vis[u] = 1;
    fa[u][0] = v;
    for (int i = head[u]; ~i; i = e[i].next) {
        int x = e[i].v;
        if (v == x) continue;
        dep[x] = dep[u] + 1;
        dfs(x, u);
    }
}

void doubly() {
    dfs(1, 1);
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    for (int i = 20; i >= 0; i--) {
        if ((dep[v] - (1 << i)) >= dep[u]) {
            v = fa[v][i];
        }
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[v][0];
}
int main(void) {
    FAST_IO;

    int t;
    cin >> t;
    while (t--) {
        init();
        int q;
        cin >> n >> q;
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        doubly();
        while (q--) {
            int a, b, c;
            cin >> a >> b >> c;
            // cout << x << endl;
            int disq = abs(dep[b] - dep[1]) + 2 * abs(dep[lca(b, c)] - dep[c]);
            int dish = abs(dep[a] - dep[1]);
            int x = lca(c, a);
            if (dish > disq || (dish == disq && x == 1)) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        }
    }

    return 0;
}

D - 景区路线规划

推迟是概率DP，等待明天大佬题解，先留个坑。。

E - 幸运数字Ⅱ

tags: 打表，二分查找

分析

对于满足条件的数字，可以由 $x*10+4$ 和 $x*10+7$ 获得。需要求 $\sum_{i=l}^{i\leq r}next[i]$ ，可以通过二分找next[i]的边界范围。再通过尺取的方式取 $next[i]$ 个数。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int const maxn = 1e5 + 10;

vector<ll> v = {4, 7};

void bfs() {
    queue<ll> q;
    q.emplace(4);
    q.emplace(7);
    while (!q.empty()) {
        if (v.back() >= 1000000000) return;
        auto x = q.front();
        q.pop();
        q.emplace(x * 10 + 4);
        q.emplace(x * 10 + 7);
        v.emplace_back(x * 10 + 4);
        v.emplace_back(x * 10 + 7);
    }
}

int main() {
    FAST_IO;
    bfs();
    ll l, r;
    cin >> l >> r;
    ll ans = 0;
    int pos1 = lower_bound(v.begin(), v.end(), l) - v.begin();
    int pos2 = lower_bound(v.begin(), v.end(), r) - v.begin();
    if (pos1 == pos2) {
        cout << (r - l + 1) * v[pos1] << endl;
    } else {
        for (int i = pos1; i <= pos2; i++) {
            if (v[i] >= l) {
                while (l != r && l <= v[i]) {
                    ans += v[i];
                    l++;
                } 
                if (l == r) {
                    ans += v[i];
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

[题解]牛客算法周周练1

A - Maximize The Beautiful Value

tags: 贪心、前缀和、推公式

分析

AC代码

B- 身体训练

tags: 数学

分析

AC 代码

C - Borrow Classroom

tags：图论、LCA

分析

AC代码

D - 景区路线规划

E - 幸运数字Ⅱ

tags: 打表，二分查找

分析

参考代码