如果公式炸了，可以去这里看： https://www.luogu.com.cn/blog/taiqi/niu-ke-suan-fa-zhou-zhou-lian-1-post （后台好好的，一到前台就炸。。）

A-Maximize The Beautiful Value

Solution

由题目中的计算公式可以发现，越向后的数所占的比重越大。因为给出的序列是单调不降的，所以给出的顺序一定是和最大的。

所以只需要移动最少的距离使影响最小，即移动 个单位。之后考虑移动每个数对总和产生的影响。

若将第 个数左移 位，设序列前缀和数组为 ，则序列 的总和 的变化量为 。

在所有的 中取最大值即可。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll ans,sum,t,n,k,a[maxn],s[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        ans=0,sum=-1e14;
        memset(s,0,sizeof(s));
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s[i]=a[i]+s[i-1];
            ans+=i*a[i];
        }
        for(int i=k+1;i<=n;i++)
            sum=max(sum,s[i-1]-s[i-k-1]-a[i]*k);
        ans+=sum;
        cout<<ans<<endl;
    }
    return 0;
}

B-身体训练

Solution

根据期望的可加性可以将问题转化为所有人期望时间之和。

设第 个人在第 次起跑，路程为 ，相对速度为 ，所需时间为 。又因为在每个位置起跑的概率都是 ，故所有人期望总时间为

使用两层循环枚举即可。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e3+10;
int n;
double ans,u,v,c[maxn],d[maxn];
int main(){
    cin>>n>>v>>u;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=n;i++)
        cin>>d[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ans+=u/(c[i]-(j-1)*d[i]-v);
    printf("%.3f",ans);
    return 0;
}

C-Borrow Classroom

Solution

由题意可知有两种拦截方法：拦截 SK 或拦截小 Q 。

  1. 拦截 SK ：先求出 与 ， 与 的 ，设分别为 和 。
  • 若 与 不相等，则何老师必须赶在 SK 之前到达小 Q 处。
  • 若 与 相等，则何老师只需和 SK 同时到达 处即可。
  1. 拦截小 Q ：先求出 与 的 ，设为 。
  • 若 等于根节点 ，则何老师必须赶在小 Q 之前到达根节点处。
  • 若 与 不相等，则何老师只需和小 Q 同时到达 处即可。

由于是树形结构，所以两点之间的距离可以通过求 得出，即 。

可以通过重链剖分求出 ，依次判断每条询问即可。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
struct edge{
    int t;
    int v;
}e[maxn<<1];
int T,n,q,cnt,hd[maxn];
int dep[maxn],top[maxn],fa[maxn],son[maxn],size[maxn];
void add(int x,int y){
    cnt++;
    e[cnt].t=hd[x];
    e[cnt].v=y;
    hd[x]=cnt;
}
void dfs1(int u,int f){
    size[u]=1;
    dep[u]=dep[f]+1;
    fa[u]=f;
    int sum=0;
    for(int i=hd[u];i!=0;i=e[i].t){
        if(e[i].v==f)
            continue;
        dfs1(e[i].v,u);
        size[u]+=size[e[i].v];
        if(size[e[i].v]>sum)
            sum=size[e[i].v],son[u]=e[i].v;
    }
    return;
}
void dfs2(int u,int x){
    if(x)
        top[u]=top[fa[u]];
    else
        top[u]=u;
    if(son[u])
        dfs2(son[u],1);
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=fa[u]&&e[i].v!=son[u])
            dfs2(e[i].v,0);
    return;
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    return x;
}
void init(){
    cnt=0;
    memset(hd,0,sizeof(hd));
    memset(dep,0,sizeof(dep));
    memset(son,0,sizeof(son));
}
int main(){
    cin>>T;
    int x,y,z,u,m,a,b;
    while(T--){
        init();
        cin>>n>>q;
        for(int i=1;i<n;i++){
            cin>>x>>y;
            add(x,y),add(y,x);
        }
        dfs1(1,1);
        dfs2(1,0);
        for(int i=1;i<=q;i++){
            cin>>x>>y>>z;
            u=lca(x,z);
            a=dep[x]+dep[z]-2*dep[u];
            m=lca(y,z);
            b=dep[y]+dep[z]-2*dep[m];
            if(a<b||(a==b&&u==m)){
                puts("YES");
                continue;
            }
            a=dep[x];
            if(a<b+dep[z]||(a==b+dep[z]&&u!=1))
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}

D-景区路线规划

Solution

由于去各个景点的概率相等，所以可以枚举出发的节点，每个节点通过 求出期望，之后相加除以 即可。

可以发现搜索的每一层都只有两个状态：当前节点与剩余时间。因为 与 较小，所以可以利用数组将每个状态的答案存下来。设 为当前游览完景区 ，剩余时间 的期望满意度，进行记忆化搜索，再次搜到时直接返回答案即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=110;
struct node{
    int h1,h2,c;
}a[maxn];
int n,m,k,e[maxn][maxn];
double ans1,ans2,f1[maxn][510],f2[maxn][510];
double dfs1(int u,int t){
    if(f1[u][t])
        return f1[u][t];
    double sum=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(e[u][i]&&t>=e[u][i]+a[i].c){
            cnt++;
            sum+=dfs1(i,t-e[u][i]-a[i].c);
        }
    if(cnt)
        sum/=cnt;
    sum+=a[u].h1;
    f1[u][t]=sum;
    return sum;
}
double dfs2(int u,int t){
    if(f2[u][t])
        return f2[u][t];
    double sum=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(e[u][i]&&t>=e[u][i]+a[i].c){
            cnt++;
            sum+=dfs2(i,t-e[u][i]-a[i].c);
        }
    if(cnt)
        sum/=cnt;
    sum+=a[u].h2;
    f2[u][t]=sum;
    return sum;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].c>>a[i].h1>>a[i].h2;
    int x,y,z;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        e[x][y]=e[y][x]=z;
    }
    for(int i=1;i<=n;i++)
        if(k>=a[i].c)
            ans1+=dfs1(i,k-a[i].c);
    ans1/=n;
    for(int i=1;i<=n;i++)
        if(k>=a[i].c)
            ans2+=dfs2(i,k-a[i].c);
    ans2/=n;
    printf("%.5f %.5f",ans1,ans2);
    return 0;
}

E-幸运数字Ⅱ

Solution

由于每位只有两种选择，所以 内的数字个数十分有限，直接通过 构造即可。

对于询问的区间，可以先二分确定第一个大于等于区间左端点 的数，之后枚举加上每个数对答案的贡献即可，注意不能超过右端点。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll ans,l,r,a[maxn],cnt;
void dfs(ll x){
    if(x>r*10+4)
        return;
    if(x)
        a[++cnt]=x;
    dfs(x*10+4);
    dfs(x*10+7);
}
int main(){
    cin>>l>>r;
    dfs(0);
    sort(a+1,a+cnt+1);
    ll x=1,y=cnt,mid;
    while(x<y){
        mid=(x+y)>>1;
        if(a[mid]>=l)
            y=mid;
        else
            x=mid+1;
    }
    for(int i=x;i<=cnt;i++){
        ans+=(min(r,a[i])-l+1)*a[i];
        l=min(r,a[i])+1;
        if(l>r)
            break;
    }
    cout<<ans;
    return 0;
}