牛客挑战赛42题解

A:小睿睿的数列
我们注意到一个区间内的数字全部相同这种贡献是可以单独算的
那么我们可以把它们都缩在一起
然后我们发现我们每个点的gcd要使找得到，一定是下一次是这一次的约数，然后我们不断向两边扩展，由于是约数而且我们规定了它们不同，所以每次至少是上次的两倍，这样最多是log次的
我们找一个起点作为gcd然后向两边枚举即可，不断更新取max然后计数就可以了
因此总复杂度是一个log的，代码里只有些去重的技巧，还是比较好写的
代码：

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=2e6+5;
int n,a[N],len,lst=1,ma,ans;pii b[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)if(i!=1&&a[i]!=a[i-1])b[++len]=pii(lst,i-1),lst=i;
    b[++len]=pii(lst,n);
    for(int i=1;i<=len;i++){
        int res=b[i].second-b[i].first+1;
        for(int j=i-1;j;j--){
            if(a[b[j].first]%a[b[i].first]!=0)break;
            res+=b[j].second-b[j].first+1;
        }
        for(int j=i+1;j<=len;j++){
            if(a[b[j].first]%a[b[i].first]!=0)break;
            res+=b[j].second-b[j].first+1;
        }
        if(res>ma)ma=res,ans=1;else if(res==ma)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

B:小睿睿的伤害
不太会题解的做法，考试的时候没多想直接码就可以了
我们考虑质因数不会太多，因此我们用一个vector记录一下
然后每个vector枚举每个约数我们用一个虚树维护一下这个部分点的树结构，然后虚树上dfs一遍更新答案就可以了，好像有点卡常加上卡常选项就好了，O(能过)

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
struct Edge{int to,nxt;}e[N<<1];
int n,fst[N],tote,dep[N],id[N],fa[N][21],dfn,st[N],tp,siz[N],a[N],now,ans[N];
bool usd[N],vis[N];LL cnt[N];
vector<int>edg[N],vec[N],cle;set<int>s;
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
void dfs(int u,int f) {
    id[u]=++dfn;dep[u]=dep[f]+1;fa[u][0]=f;
    for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=f)dfs(v,u);
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=20;i>=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
bool cmp(int x,int y){return id[x]<id[y];}
void insert(int u){
    s.insert(u);
    if(tp==1){if(u!=st[tp])st[++tp]=u;return;}
    int pos=lca(st[tp],u);
    while(tp>1&&id[pos]<=id[st[tp-1]]){
        if(!vis[st[tp-1]])vis[st[tp-1]]=true,cle.pb(st[tp-1]);
        edg[st[tp-1]].pb(st[tp]);tp--;
    }
    if(st[tp]!=pos){
        if(!vis[pos])vis[pos]=true,cle.pb(pos);
        edg[pos].pb(st[tp]);st[tp]=pos;
    }
    st[++tp]=u;
}
void dfs2(int u){
    if(usd[u])siz[u]=1;else siz[u]=0;
    LL res=0;
    for(auto v:edg[u]){
        dfs2(v);
        //if(now==12)printf("siz:%d %d %d %d\n",u,v,siz[u],siz[v]);
        res+=(LL)siz[u]*siz[v];siz[u]+=siz[v];
    }
    //if(now==12)printf("res:%lld\n",res);
    if(res)ans[u]=now,cnt[u]=res;
}
void build(int len){
    //memset(siz,0,sizeof(siz));
    //printf("now:%d %d\n",now,len);
    //for(int i=1;i<=len;i++)printf("%d%c",a[i]," \n"[i==len]);
    for(int i=1;i<=len;i++)usd[a[i]]=true;
    sort(a+1,a+len+1,cmp);
    cle.clear();cle.pb(1);vis[1]=true;
    for(int i=1;i<=len;i++)insert(a[i]);
    while(tp>1){
        if(!vis[st[tp-1]])vis[st[tp-1]]=true,cle.pb(st[tp-1]);
        edg[st[tp-1]].pb(st[tp]);tp--;
    }
    //puts("edge:");
    //for(int i=1;i<=n;i++)for(auto v:edg[i])printf("%d %d\n",i,v);
    dfs2(1);
    for(auto x:cle)edg[x].clear(),vis[x]=false;
    for(int i=1;i<=len;i++)usd[a[i]]=false;
}

int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        for(int j=1;j*j<=x;j++)if(x%j==0){
            vec[j].pb(i);
            if(j*j!=x)vec[x/j].pb(i);
        }
    }
    dfs(1,0);
    for(int i=1,len;i<N;i++){
        if(vec[i].empty())continue;len=0;now=i;
        for(auto x:vec[i])a[++len]=x;build(len);
    }
    for(int i=1;i<=n;i++)printf("%d %lld\n",ans[i],cnt[i]);
    return 0;
}

C:小睿睿的兄弟
我们发现求k级的关系这些深度都是一样的，然后又是出现在一个子树里面的问题，我们通常会想到dfs序
但是我们发现要求特定深度的dfs序就不是那么好搞
我们对于每个深度按dfs维护一个顺序，然后在一个vector里面存一下，我们按照深度优先，dfs第二优先级的顺序存一下，接着我们就可以直接求一个深度里面连续的第k小了，我们可以在vector上二分然后用跟平常套路一样的主席树维护！
这题有点卡空间，我们尽量要优化空间常数！
代码：

牛客挑战赛42题解

全站热榜