牛客算法周周练1题解
牛客算法周周练1题解
A Maximize The Beautiful Value
题意翻译
给出一个单调不减的数列 ，选择一个数
，将其放置至
至
的任意一个位置
中，并将
到
依次向后移动一位。
求
题解
因为单调不减，所以越往前越吃亏，显然选择的这个数只会移动 位。
设 为移动前的
，如果移动的位置为
，则有移动后的
发现等式右边的 可以前缀和处理。
所以从 到
扫一遍就行了。
时间复杂度
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 身体训练
题解
考虑枚举每个人 和出发时间
。
可以得到答案为
考虑到每个人的概率均为 ，则最后答案为
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。
可以通过求 的LCA
，得到
间的距离
然后对 的 LCA 进行分类讨论。
如果 的 LCA 为 1 ，那 A 就要跨过根，再多走一个，否则追到 LCA 就行了。
通过递送的时间和路程可以轻松判断是否可以追上。
E 幸运数字Ⅱ
题解
发现 的值域比较大，不可能对于
，求
的。
那么发现 的取值数量实际上很小，可以考虑每个
对答案的贡献。
令 为
中第
小的
取值，设
。
则答案为
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;
} 
