牛客算法周周练1 A,C,E

A题题意：给你一个按升序排好的序列，你需要交换ai和ai+m，问交换后这个序列最大权值算法是多少图片说明

样例这个图告诉我们交换后的权值变化是ai-m到ai-1这个区间加上ai*m，所以我们只要求出这个区间的值就行了，因为没有修改，所以我们只需要用前缀和即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
        if(c=='P')return 1;
        else if(c=='H')return 0;
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555;
ll n,m,k,a[N],s[N],sum,ans;
int main(){
    int T=read();
    while(T--){
        n=read(),m=read();
        sum=ans=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            s[i]=s[i-1]+a[i];
            sum+=a[i]*i;
        }
        for(int i=m;i<n;i++){
            ans=max(ans,sum+s[i]-s[i-m]-a[i+1]*m);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C题：题目要你求老师是否能在小Q到达办公室前够拦截小Q。
拦截方式有2种，在SK到达小Q之前拦下SK或者在小Q到达办公室之前拦下小Q。
因此我们只要比较SK到小Q的距离与老师到小Q的距离和SK到办公室的距离与SK到小Q的距离加上小Q到办公室的距离即可。
因为数据范围比较大，所以我们要用LCA来求距离。
找到他们的最近公共祖先，然后用他们两个的深度减去两个最近公共祖先的深度即为距离。
注意题目说的如果是同时到达办公室也是输出NO，还有组数据输出完后要清零，不然会影响下一组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
        if(c=='P')return 1;
        else if(c=='H')return 0;
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555;
int n,m,k,deth[N],ans,f[N][22],l,r;
vector<int>q[N];
void dfs(int u,int fa,int deep){
    f[u][0]=fa;
    deth[u]=deep;
    for(int i=1;(1<<i)<=deep;i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=0;i<q[u].size();i++){
        int t=q[u][i];if(t==fa)continue;
        dfs(t,u,deep+1);
    }
}
int lca(int x,int y){
    if(deth[x]<deth[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(deth[x]-(1<<i)>=deth[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];
}
int main(){
    int T=read();
    while(T--){
        memset(q,0,sizeof(q));
        memset(f,0,sizeof(f));
        memset(deth,0,sizeof(deth));
        n=read(),m=read();
        for(int i=1;i<n;i++){
            int x=read(),y=read();
            q[x].push_back(y);
            q[y].push_back(x);
        }
        dfs(1,1,0);
        while(m--){
            int x=read(),y=read(),z=read();
            int k=lca(y,z),l=lca(x,z);
            if(deth[x]-deth[l]-deth[l]<=deth[y]-deth[k]-deth[k]||deth[x]<deth[z]+deth[z]-deth[k]+deth[y]-deth[k]){
                printf("YES\n");
            }
            else if(deth[x]+(deth[k]<<1)==(deth[z]<<1)+deth[y]){
                if(lca(x,z)!=1){
                    printf("YES\n");
                }
                else{
                    printf("NO\n");
                }
            }
            else{
                printf("NO\n");
            }
        }
    }
    return 0;
}

E题：题目说定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
只有2个数，很明显的2进制。我们提前打好表，把小于1000000000的数都记录下来，总共10位数大概有2^10-1种可能。
然后从1开是暴力枚举即可。

牛客算法周周练1 A,C,E

全站热榜