牛客算法周周练1

https://ac.nowcoder.com/acm/contest/5086

A、Maximize The Beautiful Value

暴力枚举移动哪个数字，代价就是减去这个数字的 k 倍再加上这个数字所有 k 个数字的和

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
ll a[MAXN];
ll pre[MAXN];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, k;
		sc("%d%d", &n, &k);
		ll ans = 0, sum = 0;
		for (int i = 1; i <= n; i++)
		{
			sc("%lld", &a[i]);
			pre[i] = pre[i - 1] + a[i];
			sum += a[i] * i;
		}
		for (int i = k + 1; i <= n; i++)
			ans = max(ans, sum + (pre[i - 1] - pre[i - k - 1]) - a[i] * k);
		pr("%lld\n", ans);
	}
}

B、身体训练

阅读理解题。

大概就是求 n 个人位置随机，求每个人在队尾超过队首的人 u 米需要的时间的期望。

实际上就是枚举队尾队首，然后求时间的总和，除 n

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e3 + 5;
double c[MAXN], d[MAXN];
int main()
{
    int n; double v, u;
    sc("%d%lf%lf", &n, &v, &u);
    for (int i = 1; i <= n; i++)
        sc("%lf", &c[i]);
    for (int i = 1; i <= n; i++)
        sc("%lf", &d[i]);
    double ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans += (u * n) / (c[i] - (j - 1) * d[i] - v);
    pr("%.3lf", ans / n);
}

C、Borrow Classroom

首先 B 肯定要走到 C，如果 A 可以在 B 走到 C 之前找到 B，那么也一定可以在 B 走到 C 之后拦截 B。

然后考虑 A 和 C 的关系，如果他们 lca = 1，说明他们在不同的子树内，此时若 A 到 1 的距离等于 B 到 C 的距离加上 C 到 1 的距离，则拦截失败

反之 lca != 1，说明他们在同一子树中，若两个距离相等，则说明老师可以在到达 1 之前拦截 C

由于不会倍增 lca，上个树剖

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
struct edge
{
    int to;
    int nex;
}e[MAXN * 2];
int head[MAXN], tot;
int son[MAXN], fa[MAXN], sz[MAXN], deep[MAXN];
int p[MAXN], fp[MAXN], top[MAXN], pos;
void init()
{
    memset(head, -1, sizeof(head));
    tot = 1;
    memset(son, -1, sizeof(son));
    pos = 1;
}
void add(int a, int b)
{
    e[tot] = edge{ b,head[a] };
    head[a] = tot++;
}
void dfs1(int u, int f)
{
    sz[u] = 1;
    fa[u] = f;
    deep[u] = deep[f] + 1;
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (son[u] == -1 || sz[son[u]] < sz[v])
            son[u] = v;
    }
}
void dfs2(int u, int tp)
{
    top[u] = tp;
    p[u] = pos;
    fp[pos] = u;
    pos++;
    if (son[u] == -1)
        return;
    dfs2(son[u], tp);
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
int lca(int a, int b)
{
    int f1 = top[a], f2 = top[b];
    while (f1 != f2)
    {
        if (deep[f1] < deep[f2])
        {
            swap(f1, f2);
            swap(a, b);
        }
        a = fa[f1];
        f1 = top[a];
    }
    if (deep[a] > deep[b])
        swap(a, b);
    return a;
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        init();
        int n, m;
        sc("%d%d", &n, &m);
        for (int i = 1; i < n; i++)
        {
            int a, b;
            sc("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        dfs1(1, 0);
        dfs2(1, 1);
        while (m--)
        {
            int a, b, c;
            sc("%d%d%d", &a, &b, &c);
            if (lca(a, c) == 1)
            {
                int dep1 = deep[a];
                int dep2 = deep[c] + deep[b] + deep[c] - 2 * deep[lca(b, c)];
                if (dep1 < dep2)
                    pr("YES\n");
                else
                    pr("NO\n");
            }
            else
            {
                int dep1 = deep[a];
                int dep2 = deep[c] + deep[b] + deep[c] - 2 * deep[lca(b, c)];
                if (dep1 <= dep2)
                    pr("YES\n");
                else
                    pr("NO\n");
            }
        }
    }
}

D、景区路径规划

记忆化搜索

考虑枚举起点开始搜索，然后搜索可以走的点，将这些可以走的点的答案加起来，除以可以走的点的个数就得到了以起点开始搜索的价值。

关于复杂度，100 个点，最多 480 时间，所以记忆化的状态只有 48000 个，每个一点最多搜索 n 次，所以大概是 4.8e6 的复杂度？然后加个map复杂度差不多就 O(能过)。

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
#define Pair pair<int,int>
#define Pdd pair<double,double>
const int MAXN = 105;
struct node
{
    int time;
    int a;
    int b;
}que[MAXN];
struct edge
{
    int to;
    int w;
    int nex;
}e[MAXN * MAXN + MAXN + 5];
int head[MAXN], tot;
void init()
{
    memset(head, -1, sizeof(head));
    tot = 1;
}
void add(int a, int b, int c)
{
    e[tot] = edge{ b,c,head[a] };
    head[a] = tot++;
}
map<Pair, Pdd>mp;
Pdd dfs(int u, int time)
{
    Pdd ans = Pair{ 0,0 };
    if (time < 0)
        return ans;
    if (mp.count(Pair{ u,time }))
        return mp[Pair{ u,time }];
    int cnt = 0;
    for (int i = head[u]; i + 1; i = e[i].nex)
    {
        int v = e[i].to;
        if (time >= e[i].w + que[v].time)
            cnt++;
        Pdd tt = dfs(v, time - e[i].w - que[v].time);
        ans.first += tt.first;
        ans.second += tt.second;
    }
    if (cnt)
    {
        ans.first = 1.0 * ans.first / cnt;
        ans.second = 1.0 * ans.second / cnt;
    }
    ans.first += que[u].a;
    ans.second += que[u].b;
    mp[Pair{ u,time }] = ans;
    return ans;
}
int main()
{
    init();
    int n, m, t;
    sc("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++)
        sc("%d%d%d", &que[i].time, &que[i].a, &que[i].b);
    while (m--)
    {
        int a, b, c;
        sc("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    Pdd ans = Pair{ 0,0 };
    for (int i = 1; i <= n; i++)
    {
        Pdd tt = dfs(i, t - que[i].time);
        ans.first += tt.first;
        ans.second += tt.second;
    }
    pr("%.5lf %.5lf", ans.first * 1.0 / n, ans.second * 1.0 / n);
}

E、幸运数字Ⅱ

打表出所有 4 7 组合的数字，排个序，然后每两个相邻数字构成的区间内数字的答案全部都是右端点，算区间个数即可

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
vector<ll>v;
int main()
{
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 0; j < (1 << i); j++)
        {
            ll num = 0;
            for (int k = 0; k < i; k++)
            {
                if (j & (1 << k))
                    num = num * 10 + 7;
                else
                    num = num * 10 + 4;
            }
            v.push_back(num);
        }
    }
    v.push_back(4444444444);
    sort(v.begin(), v.end());
 
    ll l, r;
    sc("%lld%lld", &l, &r);
    int i = 0;
    for (; i < v.size(); i++)
    {
        if (v[i] >= l)
            break;
    }
    ll ans = 0, pre = l;
    for (; i < v.size(); i++)
    {
        if (r <= v[i])
        {
            ans += 1LL * (r - pre + 1) * v[i];
            break;
        }
        else
        {
            ans += 1LL * (v[i] - pre + 1) * v[i];
            pre = v[i] + 1LL;
        }
    }
    pr("%lld\n", ans);
}