牛客算法周周练1 【题解】
A、Maximize The Beautiful Value
解题思路：
如果你可以观察到给定的序列是递增的，这道题就是水题了，我们要求max，考虑到题目意思，那肯定是就移动K个位置，我们先求到 后面在预处理出前缀和。之和我们就可以从第K+1个位置（下标从1开始），依次向后枚举，计算F(n)的最大值。向前移动K个位置，就表明前面K项和全部多算一遍，第K+1个位置少算K遍。
时间复杂度 O(N)
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e5 + 7;
ll a[N];
ll sum[N];
int main() {
int T = read();
while (T--) {
int n = read(), k = read();
ll tot = 0;
for (int i = 1; i <= n; ++i) {
a[i] = read();
tot += a[i] * i;
}
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
ll ans = -(1 << 29);
for (int i = k + 1; i <= n; ++i) {
ll tmp = tot + (sum[i - 1] - sum[i - 1 - k]) - a[i] * k;
ans = max(ans, tmp);
}
printf("%lld\n", ans);
}
return 0;
}B、身体训练
解题思路：
枚举每一个人(i)，再枚举出发时间(j)，那么时间总和就是路程除以相对速度 因为每个人概率都是1/n所以最后求和公式里面u*n可以抵消一个n
时间复杂度 O(N*N)
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e3 + 5;
double c[N], d[N];
int main() {
int n;
double v, u;
scanf("%d %lf %lf", &n, &v, &u);
for (int i = 0; i < n; ++i) scanf("%lf", c + i);
for (int i = 0; i < n; ++i) scanf("%lf", d + i);
double ans = 0.0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ans += u / (c[i] - j * d[i] - v);
printf("%.3f\n", ans);
return 0;
}C、Borrow Classroom
解题思路
需要前导知识LCA：不懂的可以康康这位大佬写的博客：
https://blog.csdn.net/qq_43549984/article/details/100144030?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2
通过一次dfs求出以1为根的全部节点的深度，并且预处理出全部的fa数组。
1、同学A->教室 == deep[A]
2、同学B->同学C->教室 == deep[B]+2deep[C]-2deep[lca(b,c)] (如果觉得这个有点难理解的可以画图体会一下)
我们记式子1为ans1,式子2为ans2。
如果ans1<ans2一定可以拦截成功；
如果ans1==ans2;需要判断A、C是不是在同一棵子树上 即lca（a,c）是否等于1，如果等于1说明同时到达教室，手速跟不上，拦截失败，如果不是1说明在同一棵子树上，可以提前拦截下来。
如果ans1>ans2一定拦截失败。
时间复杂度 O(N * log(N)+q * log(N))
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e5 + 7;
vector<int> p[N];
int deep[N];
int fa[N][20]; //log2(100000) = 16.
void dfs(int x, int y) { //dfs求到深度以及预处理x的倍增数组
fa[x][0] = y;
deep[x] = deep[y] + 1;
for (int i = 1; i < 20; ++i)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = 0; i < p[x].size(); ++i) {
int tmp = p[x][i];
if (tmp != y)
dfs(tmp, x);
}
}
int lca(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 19; i >= 0; --i)
if (deep[fa[x][i]] >= deep[y])
x = fa[x][i]; //调整到同一深度
if (x == y) return x;
for (int i = 19; i >= 0; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int main() {
int T = read();
while (T--) {
for (int i = 0; i < N; ++i) p[i].clear();
int n = read(), m = read();
for (int i = 1; i < n; ++i) {
int x = read(), y = read();
p[x].push_back(y);
p[y].push_back(x);
}
dfs(1, 0);
while (m--) {
int a = read(), b = read(), c = read();
int len1 = lca(b, c);
int len2 = lca(a, c);
int ans1 = deep[a];
int ans2 = deep[b] + 2 * deep[c] - 2 * deep[len1];
if (ans1 < ans2) puts("YES");
else {
if (len2 != 1 && ans1 == ans2) puts("YES");
else puts("NO");
}
}
}
return 0;
}
D、景区路线规划
解题思路
考查知识点记忆化搜索+dfs。
通过dfs，依次从底向上处理，累加计算出子节点的平均期望，加上这个可去地点的h值，除以去过的地点数目，就是该节点的平均期望值。因为过程中涉及大量的重复时间计算，可以通过记忆化进行优化，因为涉及男女两个方面，需要写2个dfs，修改一下累加的期望值就ok了，也可以不用结构体变量保存，看个人。
时间复杂度 O（
）
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 105;
const double eps = 1e-6;
struct Node {
int c, h1, h2;
}a[N];
int n, m, k, e[N][N];
double f1[N][500], f2[N][500]; //1男2女
double dfs1(int u, int t) {
if (f1[u][t] > eps) return f1[u][t];
int cnt = 0; //去过的子节点数量
double ans = 0.0;
for (int i = 1; i <= n; ++i) {
if (e[u][i] && t >= e[u][i] + a[i].c) { //存在足够的时间去到并且游玩完毕
++cnt;
ans += dfs1(i, t - e[u][i] - a[i].c);
}
}
if (cnt) ans /= cnt;
ans += a[u].h1;
f1[u][t] = ans;
return ans;
}
double dfs2(int u, int t) {
if (f2[u][t] > eps) return f2[u][t];
int cnt = 0; //去过的子节点数量
double ans = 0.0;
for (int i = 1; i <= n; ++i) {
if (e[u][i] && t >= e[u][i] + a[i].c) { //存在足够的时间去到并且游玩完毕
++cnt;
ans += dfs2(i, t - e[u][i] - a[i].c);
}
}
if (cnt) ans /= cnt;
ans += a[u].h2;
f2[u][t] = ans;
return ans;
}
int main() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; ++i)
a[i].c = read(), a[i].h1 = read(), a[i].h2 = read();
for (int i = 1; i <= m; ++i) {
int u = read(), v = read(), t = read();
e[u][v] = t;
e[v][u] = t;
}
double ans1 = 0.0, ans2 = 0.0;
for (int i = 1; i <= n; ++i) {
if (k >= a[i].c) {
ans1 += dfs1(i, k - a[i].c);
ans2 += dfs2(i, k - a[i].c);
}
}
ans1 /= n; ans2 /= n;
printf("%.5f %.5f\n", ans1, ans2);
return 0;
}E、幸运数字Ⅱ
解题思路
可以通过观察在一段区间内的next值是相同的 1-3->4;4-6->7。
我们通过预处理将可能的next值升序放在一个vector容器内，注意一点要把4444444444放进去，<-当输入1e9时。
给定l,r；我们通过lower_bound(it,it,l)，查找l在容器中的位置。一步步往下去取区间，注意特判临界情况，即第一个区间的右边界>r，最后一个区间左边界是不是要全拿。
时间复杂度 O(N)
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int maxn = 1e9 + 3;
vector<ll> p; //存放4 7 44 47 74...
queue<ll> que;
void init() {
p.push_back(4);
p.push_back(7);
que.push(4);
que.push(7);
while (que.size()) {
ll x = que.front();
que.pop();
ll tmp1 = (x << 3) + (x << 1) + 4, tmp2 = (x << 3) + (x << 1) + 7;
if (tmp1 < maxn) {
p.push_back(tmp1);
que.push(tmp1);
}
if (tmp2 < maxn) {
p.push_back(tmp2);
que.push(tmp2);
}
}
p.push_back(4444444444);
}
int main() {
init();
int l = read(), r = read();
int pos = lower_bound(p.begin(), p.end(), l) - p.begin();
ll sum = 0;
if (p[pos] <= r) sum = (p[pos] - l + 1) * p[pos];
else {
sum = (r - l + 1) * p[pos];
printf("%lld\n", sum);
return 0;
}
for (++pos; p[pos] <= r; ++pos) sum += (p[pos] - p[pos - 1]) * p[pos];
if (p[pos] > r && p[pos - 1] != r) //r不在边界上 7777
sum += (r - p[pos - 1]) * p[pos];
printf("%lld\n", sum);
return 0;
}
查看18道真题和解析
