牛客算法周周练1 ABCDE题解

A:
图片说明
思路：直接枚举这个交换点就可以了。
$图片说明$

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL a[100005];
LL s[100005];
int main(){
    int t; scanf("%d", &t);
    while(t--){
        int n, k; scanf("%d%d", &n, &k);
        LL ans=0, sum=0;
        for(int i=1; i<=n; i++){
            scanf("%lld", &a[i]);
            s[i]=s[i-1]+a[i];
            sum+=a[i]*i;
        }
        for(LL i=k+1; i<=n; i++){
            ans=max(ans, sum+s[i-1]-s[i-k-1]-i*a[i]+(i-k)*a[i]);
        }
        cout<<ans<<endl;
    }

    return 0;
}

B:
图片说明
思路：枚举每个人的位置计算贡献就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

double c[1005], d[1005];
int main() {
    int n;
    double v, u;
    cin>>n>>v>>u;
    for(int i=1; i<=n; i++){
        scanf("%lf", &c[i]);
    }
    for(int i=1; i<=n; i++){
        scanf("%lf", &d[i]);
    }

    double ans=0;
    for(int i=1; i<=n; i++){
        double t=0;
        for(int j=1; j<=n; j++) t+=n*u/(c[j]-v);
        ans+=t;
        for(int j=1; j<=n; j++) c[j]-=d[j];
    }
    printf("%.3f\n", ans/n);

    return 0;
}

C:
图片说明
思路：简单分析：
dis(1, A)<dis(B, C)+dis(C, 1)
dis(1, A)==dis(B, C)+dis(C, 1)并且LCA(A, C)!=1
就是YES。否则就是NO

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct zzz {
    int t, nex;
}e[100005 << 1]; int head[100005], tot;
void add(int x, int y) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    head[x] = tot;
}
int depth[100005], fa[100005][22], lg[100005], in[100005], out[100005], T=0;
void dfs(int now, int fath) {
    in[now]=++T;
    fa[now][0] = fath; depth[now] = depth[fath] + 1;
    for(int i = 1; i <= lg[depth[now]]; ++i)
        fa[now][i] = fa[fa[now][i-1]][i-1];
    for(int i = head[now]; i; i = e[i].nex)
        if(e[i].t != fath) dfs(e[i].t, now);

    out[now]=++T;
}
int LCA(int x, int y) {
    if(depth[x] < depth[y]) swap(x, y);
    while(depth[x] > depth[y])
        x = fa[x][lg[depth[x]-depth[y]] - 1];
    if(x == y) return x;
    for(int k = lg[depth[x]] - 1; k >= 0; --k)
        if(fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}

int slove(int A, int B, int C){
    int s1=depth[B]+2*depth[C]-2*depth[LCA(B, C)];
    int s2=depth[A];
    if(s2<s1){
        return 1;
    }
    else if(s2==s1&&LCA(A, C)!=1){
        return 1;
    }
    else{
        return 0;
    }
}

int main() {

    for(int i = 1; i < 100005; ++i)
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);

    int t; scanf("%d", &t);
    while(t--){

        memset(head, 0, sizeof(head));
        memset(fa, 0, sizeof(fa));
        tot=0; T=0;
        int n, q;
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n-1; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            add(x, y); add(y, x);
        }
        dfs(1, 0);
        while(q--){
            int A, B, C;
            scanf("%d%d%d", &A, &B, &C);
            if(slove(A, B, C)){
                printf("YES\n");
            }
            else{
                printf("NO\n");
            }
        }
    }
    return 0;
}

D:
图片说明

$图片说明$

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, m, k;
vector<vector<pair<LL, LL> > > v(100005);
LL c[100005], h[2][100005];
double ans[2]={0};
pair<double, double> f[101][505];
//dp[i][j].first表示在i分钟j点的期望,dp[i][j].second表示概率。

void DFS(int x){
    memset(f, 0, sizeof(f));
    for(int i=1; i<=n; i++){
        f[i][c[i]].first=1.0*h[x][i]/n;
        f[i][c[i]].second=1.0/n;
    }
    for(int i=1; i<k; i++){//时间

        for(int u=1; u<=n; u++){//点
            int num=0;//在时间i节点u可以转移的点数量
            int flag=0;
            for(auto x: v[u]){
                int to=x.first, time=x.second+c[to];
                if(i+time<=k){//可以转移
                    num++;
                }
            }

            for(auto X: v[u]){
                int to=X.first, time=X.second+c[to];
                if(i+time<=k&&f[u][i].first){//可以转移
                    flag=1;
                    f[to][i+time].first+=f[u][i].first*(1.0/num)+h[x][to]*f[u][i].second*(1.0/num);
                    f[to][i+time].second+=f[u][i].second*(1.0/num);
                }
            }

            if(!flag){
                f[u][k].first+=f[u][i].first;
                f[u][k].second+=f[u][i].second;
            }
        }
    }
    for(int i=1; i<=n; i++){
        ans[x]+=f[i][k].first;
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld%lld%lld", &c[i], &h[0][i], &h[1][i]);
    }
    LL x, y, z;
    for(int i=1; i<=m; i++){
        scanf("%lld%lld%lld", &x, &y, &z);
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    DFS(0);
    DFS(1);
    printf("%.5f %.5f\n", ans[0], ans[1]);

    return 0;
}

E:
图片说明
思路：把表打出来，就可以遍历一次计算。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<LL> v;
void DFS(LL pos, LL s){
    if(pos>11){
        return ;
    }
    DFS(pos+1, s*10+4);
    v.push_back(s*10+4);
    DFS(pos+1, s*10+7);
    v.push_back(s*10+7);
}

int main(){

    DFS(1, 0);
    sort(v.begin(), v.end());
    LL l, r; cin>>l>>r;
    LL ans=0;
    for(auto x: v){

        if(x>=l){
            ans+=min(r-l+1, (x-l+1))*x;
            l=x+1;
            if(l>r){
                break;
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}