牛客算法周周练1

A.
Solution
因为是非递减数列，所以只移动k位是最佳的，那么对于原数列的美丽值来说移动k位所造成的变化是增加了 $s[i-1]-s[i-k-1]$ 而减少了 $a[i]*k$ ，所以遍历大于k的部分， $图片说明$ = $s[i-1]-s[i-k-1]-a[i]*k$ ，那 $ans$ 遍历取max即可。
Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=1e5+10;

ll mod=1000000000+7;

ll a[manx],s[manx];

int main(){
    ll p=read();
    while(p--){
        ll n=read(),k=read(),mi=0;
        for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i],mi+=a[i]*i;
        ll ans=0;
        for(int i=k+1;i<=n;i++){
            ll res=mi-a[i]*k+(s[i-1]-s[i-k-1]);
            ans=max(ans,res);
       //     printf("%lld\n",res);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

B.
Solution
关于B题的话是在上面的那些题解中得到收获的，本题最重要的是文中的一句话:

当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。

那么既然是等概率出现就依次计算每个人在第几次从最后加速跑计算即可。
题目给了最高的速度： $x=a[i]-(j-1)*b[i];$
那么追上前面的人并领先 u 米所需要的时间: $n*u / (x-v)$
最后乘上概率 $1/n$ 即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=1e5+10;

ll mod=1000000000+7;

double a[manx],b[manx];
int main(){
    double u,v,n; cin>>n>>v>>u;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    double ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            double x=a[i]-(j-1)*b[i];
            ans+=(n*u)/(x-v)*(1/n);
        }
    }
    printf("%.3f\n",ans);
    return 0;
}

C.
Solution
考虑用LCA求两点距离，那么很明显，只有两种情况才可以拦截：

即老师跑到教务处的时间更短，就有可能拦截，即： $dis(a,1)<dis(b,c)+dis(c,1)$
而当两者相同时，就要考虑两者的最近公共祖先是否为教务处，因为同时到达的话也无法拦截小Q同学的手快，而不是的话说明他们会在教务处的子结点碰面即可以拦截，即判断： $dis(a,1)==dis(b,c)+dis(c,1)$ && $lca(a,c)!=1$

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }

const int manx=1e5+10;

ll mod=1000000000+7;
vector<ll>g[manx];
ll d[manx],f[manx][25];

void init(){
    for(int i=0;i<manx;i++) d[i]=0,g[i].clear();
    memset(f,0,sizeof(f));
}
void dfs(ll u,ll pre){
    d[u]=d[pre]+1; f[u][0]=pre;
    for(int i=1;(1<<i)<=d[u];i++)
        f[u][i]=f[ f[u][i-1] ][i-1];
    for(auto v: g[u]){
        if(v==pre) continue;
        dfs(v,u);
    }
}
ll lca(ll u,ll v){
    if(d[u]>d[v]) swap(u,v);
    for(int i=20;i>=0;i--)
        if(d[v]-d[u]>=(1<<i)) v=f[v][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(f[u][i]==f[v][i]) continue;
        u=f[u][i]; v=f[v][i];
    }
    return f[u][0];
}
ll dis(ll u,ll v){
    return d[u]+d[v]-2*d[lca(u,v)];
}
int main(){
    ll p=read();
    while(p--){
        init();
        ll n=read(),q=read();
        for(int i=1;i<n;i++){
            ll u=read(),v=read();
            g[u].pb(v); g[v].pb(u);
        }
        dfs(1,0);
        while(q--){
            ll a=read(),b=read(),c=read();
            if(dis(a,1)<dis(b,c)+dis(c,1)) put1();
            else if(dis(a,1)==dis(b,c)+dis(c,1)&&lca(a,c)!=1) put1();
            else put2();
        }
    }
    return 0;
}

E.
Solution
依然记得上次CF出了一道题，大概的解题思路就是因为在一个大范围里面满足条件的元组太少，所以可以直接暴力，因为这道题的话是每一位都是4/7，所以在1-1e9的范围里面其实是很少的，所以可以暴力dfs求出来，
然后遍历求出来的元素进行答案累加就可以了。
坑点：求出来的数组记得排序。
Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }
const int manx=1e6+10;
ll mod=1000000000+7;
vector<ll>q;
void dfs(ll x,ll y){
    if(y) return ;
    if(x>1000000000) y=1;
    ll x1=x*10+4,x2=x*10+7;
    q.pb(x1),q.pb(x2);
    dfs(x1,y),dfs(x2,y);
}
int main(){
    ll l=read(),r=read();
    dfs(0,0);
    ll ans=0;
    sort(q.begin(),q.end());
    for(auto x: q){
        if(x<l) continue;
        if(x<=r) ans+=(x-l+1)*x;
        else{
            ans+=(r-l+1)*x;
            break;
        }
        l=x+1;
    }
    printf("%lld",ans);
    return 0;
}