2020-04-07 23:17 已编辑华南农业大学 C++

关注

牛客算法周周练1（ABCDE题解）

A.Maximize The Beautiful Value（贪心，前缀和）

题目：

一个单调不减的序列 $a$ ，进行一次操作后使 $\sum_{i=1}^{n}i*a_i$ 值最大。
操作：选一个 $a_j$ 往前挪至少 $k$ 位。

做法：

不难发现每个 $a_j，j∈[k+1,n]$ 有合法操作，而且多往前挪几位不会使答案更优。
所以贪心枚举 $a_j，j∈[k+1,n]$ 计算 $a_j$ 往前挪 $k$ 位的值，取 $max$ 即可。
算 $\sum_{i=1}^{n}i*a_i$ 用前缀和优化。具体看代码。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, k, a[N];
ll prefix[N];
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> k;
        ll sum = 0;
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
            sum += i*a[i];
            prefix[i] = prefix[i-1]+a[i];
        }
        ll ans = 0;
        for (int i = k+1; i <= n; ++i){
            ans = max(ans, sum-k*a[i]+(prefix[i-1]-prefix[i-k-1]));
        }
        cout << ans << endl;
    }
    return 0;
}

B.身体训练(数学期望)

题目：

美团外卖的配送员用变速跑的方式进行身体训练。
他们训练的方式是：n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i] 米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。
n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？

做法：

分每个人最开始处于每个位置算这个人的时间期望。
对于第 $i$ 个人，他等概率地作为第 $j，j∈[1，n]$ 个人向前跑。
速度 $k_j$ 我们可以算出来： $k_j=c[i]-(j-1)*d[i]$ 。
所花的时间 $t_j = \frac{n*u}{k_j-v}$ 。
第 $i$ 个人时间期望 $d_i=\frac{\sum_{j=1}^{n}t_j}{n}=\sum_{j=1}^{n}{\frac{u}{k_j-v}}$ 。
那么总用时期望 $d=\sum_{i=1}^{n}{d_i}$

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;
int n;
double v, u, c[N], d[N];
int main(void){
    IOS;
    cin >> n >> v >> u;
    for (int i = 1; i <= n; ++i){
        cin >> c[i];
    }
    for (int i = 1; i <= n; ++i){
        cin >> d[i];
    }
    double ans = 0;
    for (int i = 1; i <= n; ++i){
        double tmp = 0;
        for (int j = 1; j <= n; ++j){
            double k = c[i]-(j-1)*d[i];
            tmp += u/(k-v);
        }
        ans += tmp;
    }
    cout << setprecision(3) << fixed << ans << endl;
    return 0;
}

C.Borrow Classroom(最近公共祖先lca)

题目：

一棵有根树，根为1。学生1从B结点走到C找学生2，学生2从C结点走到根去交表。老师发现表有问题，要在C走到根之前拦截拿着表的学生。问能否拦截成功。

做法：

一遍 $dfs$ 求出每个结点的深度 $dis[u]$ ，预处理 $lca$ 的倍增数组 $fa$ 。
B要去找C，然后C再往根走。用时我们可以快速得出： $dis[B]+2*dis[C]-2*dis[lca(B,C)]。$ （画图很好理解的）
对于从A出发的老师来说。我直接去根蹲守就好了。。
老师走到根的用时： $dis[A]$ 。
1、若 $dis[A]<dis[B]+2*dis[C]-2*dis[lca(B,C)]$ 说明老师先到根。拦截成功。(注意没有等于号！)
2、若 $dis[A]=dis[B]+2*dis[C]-2*dis[lca(B,C)]$ ，此时再加个判断：若 $lca(A,C)!=1$ ，则拦截成功，否则不成功。（因为老师和C同时到达1，拦截算失败，而如果 $lca(A,C)!=1$ ，老师将和C在某个非根祖先相遇，阻止C光速交表。。）
3、若 $dis[A]>dis[B]+2*dis[C]-2*dis[lca(B,C)]$ ，拦截失败。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
vector<int> g[N];
int n, q, dis[N], fa[N][20];
void dfs(int u, int p){
    fa[u][0] = p;
    dis[u] = dis[p]+1;
    for (int i = 1; i <= 19; ++i){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if (dis[u] < dis[v]) swap(u, v);
    for (int i = 19; i >= 0; --i){
        if (dis[fa[u][i]] >= dis[v]){
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i){
        if (fa[u][i] != fa[v][i]){
            u = fa[u][i], v = fa[v][i];
        }
    }
    return fa[u][0];
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> q;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 0; i < n-1; ++i){
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        while (q--){
            int A, B, C; cin >> A >> B >> C;
            if (dis[A] < dis[B]+2*dis[C]-2*dis[lca(B, C)]){
                cout << "YES" << endl;
            }else{
                if (lca(A, C) != 1 && dis[A] == dis[B]+2*dis[C]-2*dis[lca(B, C)]){
                    cout << "YES" << endl;
                }else cout << "NO" << endl;
            }
        }
    }
    return 0;
}

D.景区路线规划(记忆化搜索，数学期望)

题目：

美团旅行团队最近打算推出一项新服务，为景区的各个景点规划游览路线，提升游客满意度。其中一个重要的问题是对于一个景区道路网，求出游客的满意度的期望值。基于用户的喜好差异，我们需要对男性游客和女性游客的满意度分别计算。
景区被描述成一张n个点、m条边的无向图（无重边，无自环）。每个点代表一个景点，第i个景点游览需要耗费ci分钟，会让男性游客和女性游客的满意度分别增加h1i和h2i（满意度初始值都为0）。每条边代表一条路，第i条边连接编号为xi,yi的两个景点，从景点xi走到yi和从yi走到xi的时间都是ti分钟。
每个游客在景区中最长可以游览k分钟，最开始会随机的通过不同大门进入到一个景点开始游览，每游览完一个项目，游客会等概率随机选择一个可以从当前景点直达且来得及游览的景点作为下一个游览目标（已经游览过的景点也会因为有各种新活动而让游客再次考虑，所以我们这里不区分景点是否已经游览过）。如果游览完一个景点后，周围没有来得及游览的景点，本次游玩就结束了。
请你分别计算小y和妹子在游玩结束后开心度的期望。

做法：

我们发现 $k$ 和 $n$ 狠小。考虑暴力。
设 $dp[0/1][u][t]$ 为男生\女生在 $u$ 结点游玩后剩余 $t$ 时间的开心度期望。
我们分开男生和女生进行记忆化搜索。游完一个景点 $u$ 之后，枚举所有能到达的景点 $v$ ，看时间 $t$ 能否来得及到达 $v$ 进行游览。若能，搜下去。
深搜的姿势看代码吧，相信还是比较好懂得。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 100 + 7;
const int M = 6*80 + 7;
int n, m, k, boy[N], girl[N], cost[N];
double dp[2][N][M];
vector<pair<int,int> > g[N];
double dfs(int u, int tim, int op){
    if (dp[op][u][tim] != -1) return dp[op][u][tim];
    double& ans = dp[op][u][tim] = 0;
    int cnt = 0;
    double tmp = 0;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (cost[v]+w <= tim){
            cnt++;
            tmp += dfs(v, tim-cost[v]-w, op);
        }
    }
    if (cnt) tmp /= cnt;
    if (op == 0) ans = boy[u]+tmp;
    else ans = girl[u]+tmp;
    return ans;
}
int main(void){
    IOS;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i){
        cin >> cost[i] >> boy[i] >> girl[i];
    }
    for (int i = 1; i <= m; ++i){
        int u, v, k;
        cin >> u >> v >> k;
        g[u].push_back(make_pair(v, k));
        g[v].push_back(make_pair(u, k));
    }
    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= k; ++j){
            dp[0][i][j] = dp[1][i][j] = -1;
        }
    }
    double ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; ++i){
        ans1 += dfs(i, k-cost[i], 0);
        ans2 += dfs(i, k-cost[i], 1);
    }
    printf("%.5f %.5f\n", ans1/n, ans2/n);
    return 0;
}

E.幸运数字Ⅱ(找规律，预处理)

题目：

定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如说，47、744、4都是幸运数字而5、17、467都不是。
定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。

做法：

稍微手算一下找到构造规律：
1位数(2)：4、7
2位数(4)：44、47、74、77
3位数(8)：444、447、474、477、744、747、774、777
...以此类推
我们发现最大得 $r$ 也不过 $2e9$ 10位数。加起来也不过2000多个数。先全部构造出来。
当我们要构造 $x$ 位数的幸运数字时，我们用 $x-1$ 位数的幸运数字，每个数后面加4或7来构造就行了。
然后用前缀和预处理，第i个幸运数字记为 $a_i$ ， $prefix[i]表示\sum_{i=1}^{a_i}{next(i)}$
查询的 $[L,R]$ 区间我们拆成2个区间的差来做。 $ans=solve(1,R)-solve(1,l-1)$
$solve(1，R)$ 函数简单说一下就是二分一下第1个比 $R$ 大的幸运数字，用 $prefix$ 数组+末尾残缺部分的 $next()$ 来更新。
~~大家还是看代码理解比较好~~

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 5010;
vector<ll> v[11], a;
ll prefix[N];
void init(void){
    v[1].push_back(4), v[1].push_back(7);
    a.push_back(4), a.push_back(7);
    for (int i = 2; i <= 10; ++i){
        for (int j = 0; j < v[i-1].size(); ++j){
            v[i].push_back(v[i-1][j]*10+4);
            v[i].push_back(v[i-1][j]*10+7);
            a.push_back(v[i-1][j]*10+4);
            a.push_back(v[i-1][j]*10+7);
        }
    }
    int pre = 1;
    for (int i = 0; i < a.size(); ++i){
        prefix[i+1] = prefix[i]+1ll*(a[i]-pre+1)*a[i];
        pre = a[i]+1;
    }
}
ll solve(int R){
    int id = lower_bound(a.begin(), a.end(), R) - a.begin();
    if (id == 0) return R*4;
    id--;
    ll ans = prefix[id+1]+1ll*(R-a[id])*a[id+1];
    return ans;
}
int main(void){
    IOS;
    init();
    int l, r; cin >> l >> r;
    cout << solve(r)-solve(l-1) << endl;
    return 0;
}