牛客算法周练1

A题：
这个题目直接贪心就好了，题目要求最大值
那么我们来考虑一下，由于是非递减的序列，那么我们若走k步以上就会更小，不满足题意，所以我们只要枚举哪个点向前走k步。取所有可能情况的max,就可以快乐ac~~

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],sum[100010];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
        int ans=-1;
        int ma=0;
        for(int i=1;i<=n;i++) ma+=i*a[i];
     //   cout<<ma<<endl;
        for(int i=k+1;i<=n;i++)
        {
            ans=max(ans,ma+sum[i-1]-sum[i-1-k]-k*a[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

B题：这个题目是求概率期望的，我们可以发现如果完完全全按照题目意思，时间复杂度很高，你还要列出来所有可能的全排列1000！很可怕的数字，我们其实可以枚举每一个快递员，计算他每一轮花的时间，全部加起来，除以n，就可以得到最终答案，注意使用double的输入输出要规范

#include<bits/stdc++.h>
using namespace std;
typedef double db;
db c[1010],d[1010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    db u,v;
    cin>>n>>v>>u;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    db ans=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n-1;j++)
            ans+=(1.0*n*u)/(c[i]-j*(d[i])-v);

    }
    ans/=n;

    printf("%.3lf",ans);
    return 0;
}

E题
这个题目是打表＋判断的题目。我们用dfs或者bfs都可以实现预处理出我们可能用到的幸运数字，然后计算1-r中所有幸运数字的和，最后输出f(r)-f(l-1)就可以了~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[5000];int cnt=0;
void bfs()
{
    queue<ll> q;

    q.push(4);
    q.push(7);
    while(!q.empty())
    {
        ll t=q.front();q.pop();
        if(t>1e11) break;
        //cout<<"okk"<<endl; 
        q.push(t*10+4);
        q.push(t*10+7);
        dp[++cnt]=t;
    }
   // cout<<'o'<<endl;
}

ll f(ll r)
{
    int now=1;
    ll res=0;
    while(1){
        if(dp[now]>=r){
            res+=(r-dp[now-1])*dp[now];
            break;
        }
        if(dp[now]<r){
            res+=(dp[now]-dp[now-1])*dp[now];
        }
        ++now;

    }
    //cout<<res<<endl;
    return res;
}
ll l,r;
int main()
{
    bfs();
    sort(dp+1,dp+cnt+1);
    cin>>l>>r;
    cout<<f(r)-f(l-1)<<endl;
    return 0;
}