A. Maximize The Beautiful Value
Solution
看了半天才看懂,forward向前是从右往左挪动,我们知道一个数字往前挪动k个位后,位置为i - k。
注意到i - k 到 i - 1 这个范围的数字他们都会相应往后挪,即我们的答案会加上sum[i - 1] - sum[i - k - 1]
因此,只需要从k + 1位开始枚举每一位,求最大值就行了
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
std::ios::sync_with_stdio(false); // turn off sync
std::cin.tie(nullptr); // untie in/out streams
return 0;
}();
ll a[N];
ll sum[N];
int main(){
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
ll ans = 0;
for(int i = 1; i <= n; i++) ans += i * a[i], sum[i] = sum[i - 1] + a[i];
ll res = 0;
for(int i = k + 1; i <= n; i++){
int now = i - k; //往前k位
res = max(res, ans - i * a[i] + now * a[i] + sum[i - 1] - sum[i - 1 - k]); //减去原来的贡献 加上现在的贡献和中间数字往前挪得到的贡献
}
cout << res << "\n";
}
return 0;
} B. 身体训练
Solution
对于一个配送员,它在每个位置的概率是, 位置只会改变配送员的速度,要走的距离永远是u*n。
我们计算每个配送员在每个位置所需的时间并累加，最后除以n就是答案
得到
Code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
std::ios::sync_with_stdio(false); // turn off sync
std::cin.tie(nullptr); // untie in/out streams
return 0;
}();
double c[N], d[N];
int main(){
int n;
double v, u;
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++){
for(int j = 1; j <= n; j++){
ans += u / (c[i] - (j - 1) * d[i] - v);
}
}
cout << fixed << setprecision(3) << ans << "\n";
return 0;
} C. Borrow Classroom
Solution
树上距离的问题首先想到LCA,我们先求出B -> C -> 1的距离 dist1 和 A -> 1的距离 dist2
如果 dist1 < dist2 显然抓不到
如果 dist1 > dist2 显然老师直接去1堵他了hhh
如果 dist1 == dist2 就要讨论一下了
1.若 lca(a,c) == 1 则他们俩最终会在1相遇,由题意知小Q同学手速很快,老师gg
2.否则老师可以到lca(a, c)点堵他
Code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
std::ios::sync_with_stdio(false); // turn off sync
std::cin.tie(nullptr); // untie in/out streams
return 0;
}();
struct Edge{
int to, nextz;
}edge[N << 1];
int tot, head[N];
void addedge(int u, int v){
edge[tot].to = v;
edge[tot].nextz = head[u];
head[u] = tot++;
}
void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
int fa[N][DEG];
int dist[N];
int deg[N];
void bfs(int root){
fa[root][0] = root;
deg[root] = 0;
dist[root] = 0;
queue<int> que;
que.push(root);
while(!que.empty()){
int tmp = que.front();
que.pop();
for(int i = 1; i < DEG; i++){
fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
}
for(int i = head[tmp]; i != -1; i = edge[i].nextz){
int v = edge[i].to;
if(v == fa[tmp][0]) continue;
que.push(v);
deg[v] = deg[tmp] + 1;
dist[v] = dist[tmp] + 1;
fa[v][0] = tmp;
}
}
}
int LCA(int u, int v){
if(deg[u] > deg[v]) swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for(int det = hv - hu, i = 0; det; det >>= 1, i++){
if(det & 1){
tv = fa[tv][i];
}
}
if(tu == tv){
return tu;
}
for(int i = DEG - 1; i >= 0; i--){
if(fa[tu][i] == fa[tv][i]) continue;
tu = fa[tu][i];
tv = fa[tv][i];
}
return fa[tu][0];
}
int main(){
int t;
cin >> t;
while(t--){
init();
int n, q;
cin >> n >> q;
for(int i = 1; i <= n - 1; i++){
int u, v;
cin >> u >> v;
addedge(u, v);
addedge(v, u);
}
bfs(1);
while(q--){
int a, b, c;
cin >> a >> b >> c;
if(b == c && b == 1){
cout << "NO\n";
continue;
}
int dist1 = dist[b] + dist[c] - 2 * dist[LCA(b, c)] + dist[c]; // b -> c -> 1
int dist2 = dist[a];
if(dist1 < dist2){
cout << "NO\n";
}
else if(dist1 > dist2){
cout << "YES\n";
}
else {
if(LCA(c, a) == 1) cout << "NO\n";
else cout << "YES\n";
}
}
}
return 0;
} D. 景区路线规划
Solution
这题比赛的时候做的人挺少的,赛后补题的人也挺少,比赛的时候没看题,以为是个图论+期望挺难的
其实不是很复杂，我们考虑对于每个点,统计当前能到达的其他点的可行方案并计算期望
因为到达其他的概率是相同的,所以只需要一边统计方案数,一边统计ans,最后令ans / cnt 即可
注意到n, k的数据范围,可以记忆化搜索,至于一开始怎么取点,我们可以考虑建立一个超级源点0
令0点到任意一个点的时间都是0即可
Code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
std::ios::sync_with_stdio(false); // turn off sync
std::cin.tie(nullptr); // untie in/out streams
return 0;
}();
struct node{
int c, h1, h2;
}a[N];
struct Edge{
int v, nextz;
int w;
}edge[N << 1];
int head[N], tot;
void addedge(int u, int v, int w){
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nextz = head[u];
head[u] = tot++;
}
int n, m, k;
double dp[1005][1005];
bool vis[1005][1005];
double dfs(int u, int t, int x){
if(vis[u][t]) return dp[u][t]; // 记忆化
vis[u][t] = true;
int p = (x == 0) ? a[u].h1 : a[u].h2; // 该点对男/女的满意度
double ans = 0;
double cnt = 0;
for(int i = head[u]; i != -1; i = edge[i].nextz){
int cost = edge[i].w;
int v = edge[i].v;
if(cost + a[v].c <= t){
cnt++;
ans += dfs(edge[i].v, t - (cost + a[v].c), x); // 统计答案
}
}
if(cnt){
ans /= cnt; // 如果存在方案,除以方案数
}
ans += p; // 不要忘记加上这个点本身的贡献
dp[u][t] = ans; // 记忆化
return ans;
}
double solve(int x){ // x = 0 男 x = 1 女
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
return dfs(0, k, x);
}
int main(){
tot = 0;
memset(head, -1, sizeof(head));
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> a[i].c >> a[i].h1 >> a[i].h2;
}
while(m--){
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
for(int i = 1; i <= n; i++){
addedge(0, i, 0); // 0作为超级源点
}
cout << fixed << setprecision(5) << solve(0) << ' ' << solve(1) << "\n";
return 0;
} E. 幸运数字Ⅱ
Solution
日常梦游,先打个表,把所有幸运数字列出来,也就几千个数字。
然后我们可以分成一个个块。
这些块的贡献为块的大小 * 大于等于这个块的幸运数字
注意打表最好多打几个,不然可能会跟我一样RE,还以为是dfs爆栈
模拟即可,具体看代码
Code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
std::ios::sync_with_stdio(false); // turn off sync
std::cin.tie(nullptr); // untie in/out streams
return 0;
}();
ll dp[N];
int cnt = 0;
void bfs(){
queue<ll> q;
q.push(4);
q.push(7);
while(!q.empty()){
ll now = q.front();
q.pop();
if(now > 1e12) continue; // 这里要多打几个 不然会RE 我还以为dfs爆栈了
dp[++cnt] = now;
q.push(now * 10 + 4);
q.push(now * 10 + 7);
}
}
ll solve(ll x){
int now = 1;
ll p = min(dp[now], x); // 块的终点
ll res = 0;
ll last = 1;
while(p < x){
res += (p - last + 1) * dp[now]; // 完整的块贡献 比如 5 - 7 8 - 44
last = dp[now] + 1;
if(dp[now + 1] < x){
now++;
p = dp[now];
}
else p = x;
}
if(!res) now--; //如果res == 0, 说明循环都没进去 则这个 x 小于等于4, 要特判下
res += (p - last + 1) * dp[now + 1]; // x作为块的终点
return res;
}
int main(){
bfs(); // 打表
sort(dp + 1, dp + 1 + cnt);
ll l, r;
cin >> l >> r;
cout << solve(r) - solve(l - 1) << "\n";
} 
京公网安备 11010502036488号