A题:
一开始想着直接想k + 1往前面移动,然后直接输出,因为这个答案是图片说明 使得它最大化,那么一种贪心的想法就是直接移动k + 1移动到第一个,这样可以保证k + 2的答案是最优的,但是样例2就给了我一巴掌,这样是不行的,可能移动后面产生价值更好,所以我们需要从[k + 1,n]枚举往前面移动,但是n = 1e5 只能用o(n)的时间复杂度。注意到每次只会移动一段长度为k的序列,那么我们可以先统计出来i*a[i] = tot的和,然后因为那一段长度为k向后面移动1位实际上是对他们的和加大一倍,我们可以用前缀和直接计算这段区间和,然后tot + sum[i - 1] - sum[i - k - 1],就可以计算将那段区间向前面移动一位的值,然后因为i * a[i]被覆盖了所以需要剪掉,然后a[i]放到i - k的位置产生的价值就是a[i] * (i - k),然后不断更新答案即可。
这个题目的难点就是这个:tot - i * a[i] + sum[i - 1] - sum[i - 1 - k] + a[i] * (i - k)
代码:

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

const int maxn = 1e5 + 10;
typedef long long int ll;
ll a[maxn];
ll sum[maxn];
void solved(){
    int t;cin>>t;
    while(t--){
        ll n,k;cin>>n>>k;
        ll tot = 0;
        for(int i = 1; i <= n; i++){
            scanf("%lld",&a[i]);
            sum[i] = sum[i - 1] + a[i];
            tot += a[i] * i;
        }
        ll ans = -1e9 + 10;
        for(int i = k + 1; i <= n; i++){
            ans = max(ans,tot - i * a[i] + sum[i - 1] - sum[i - 1 - k] + a[i] * (i - k));
        }
        cout<<ans<<endl;
    }
}
int main(){
    solved();
    return 0;
} 

B:
直接计算每个人超越n个人时间和 / n即可
每个人超越n个人时间和 图片说明
代码:

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

const int maxn = 1e4 + 10;
//u:两两相隔距离
//v:每个人的匀速 
double c[maxn],d[maxn]; 
void solved(){
    int n;cin>>n;
    double v,u;cin>>v>>u;
    for(int i = 1; i <= n; i++)cin>>c[i],c[i]-=v;
    for(int i = 1; i <= n; i++)cin>>d[i];
    double time = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            time += n * u / (c[i] - (j - 1) *d[i]); 
        }
    }
    printf("%.3lf\n",time / n);
}
int main(){
    solved();
    return 0;
} 

E:
这题我用bfs写的,之前在abc写过类似的。
先bfs出所有由4,7组成的数字,然后求和即可。
一开始是打算存在vector,然后遍历[l,r]求和但是超时了,然后注意到其实在bfs的时后就可以计算答案了,就是不断的维护左端点。然后用乘法去乘就行了,这样几次就能求出答案了。。。具体看代码把,if是关键。
代码:

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

typedef long long int ll;
const int maxn = 1e8;
int a[maxn];
void solved(){
    queue<ll>st;
    st.push(4);
    st.push(7);
    vector<ll>ve;
    ll l,r;cin>>l>>r;
    ll ans = 0;
    while(!st.empty()){
        ll cur = st.front();st.pop();
        ve.push_back(cur);
        if(cur >= l){
            if(r >= cur)
            ans += (cur - l + 1) * cur;
            else {
                ans += (r - l + 1) * cur;break;
            }
            l = cur + 1;
        }
        if(l > r)break;
        if(cur > 1e9 +10)break;
        st.push(cur * 10 + 4);
        st.push(cur * 10 + 7);
    }
    cout<<ans<<endl; 
}
int main(){
    solved();
    return 0;
} 

C:a:何老师,b:sk同学,c:小c同学
如果 dis(a,1) < dis(b,c) + dis(c,1) 这样肯定可以输出yes即可
如果 dis(a,1) == dis(b,c) + dis(c,1)这个时候需要判断一下a,c是否lca是根节点的一个儿子,如果是,则a老师显然只需要花费dis(a,lca(a,c))的时间,并不需要再往上面走了,就是它可以在lca等同学,这个时候输出YES,如果lca(a,c) = 1则老师始终慢同学一步,输出no即可
如果dis(a,1) > dis(b,c) + dis(c,1)输出no
这是第一次写lca也是第一次学lca,感觉lca可以处理树上的两个节点最短距离。
代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1e6 + 100;
struct edge{
    int v,next;
    edge(){}
    edge(int a,int b):v(a),next(b){}
}e[maxn << 1];
int head[maxn],tot;
int dep[maxn],f[maxn][25];
void add(int u,int v){
    e[++tot].v = v;
    e[tot].next = head[u];
    head[u] = tot;
}
void dfs(int v,int fa){
    dep[v] = dep[fa] + 1;
    for(int i = 1; (1 << i) <= dep[v] ;i ++){
        f[v][i] = f[f[v][i - 1]][i - 1];
    }
    for(int i = head[v];i;i = e[i].next){
        if(e[i].v != fa){
            f[e[i].v][0] = v;
            dfs(e[i].v,v);
        }
    }
}
int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(int i = 20; i >= 0; i--){
        if(dep[f[x][i]] >= dep[y]) x = f[x][i];
        if(x == y)return x;
    }
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void solved(){
    int t;scanf("%d",&t);
    while(t--){
        memset(head,0,sizeof(head));
        memset(dep,0,sizeof(dep));
        memset(f,0,sizeof(f));
        int n,q;scanf("%d%d",&n,&q);
        for(int i = 1; i < n; i++){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        dfs(1,0);
        while(q--){
            int a,b,c;scanf("%d%d%d",&a,&b,&c); 
            int la = dep[a] - dep[1];
            int LCA = lca(b,c);
            int b_c = dep[b] - dep[LCA] + dep[c] - dep[LCA];
            int ld = b_c + dep[c] - dep[1];  
            if(la < ld)printf("YES\n");
            else if(la == ld){
                if(lca(a,c) == 1){//不在同一棵子树上,老师总是慢学生一步 
                    printf("NO\n");
                }else printf("YES\n");//在同一子树上,虽然距离相同,但是但是可以先到lca等同学就行了 
            }else printf("NO\n");
        }
    }
}
int main(){
    solved();
    return 0;
}