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);
}
京公网安备 11010502036488号