2025-01-19 22:33 幼儿园中班 C++ 发布于福建

关注

牛客周赛77文字版题解

A.时间表

把所有时间存在字符串数组中，输出对应的下标。

时间复杂度: $\mathcal{O(1)}$

void solve(){
    vector<string>a{
        "20250121",
        "20250123",
        "20250126",
        "20250206",
        "20250208",
        "20250211"
    };
    int x;cin>>x;
    cout<<a[x-1];
}

B.数独数组

对于此类数独，一定存在连续的周期使得每个数字的出现次数相同，然后最后存在一段连续的数字都恰好出现一次。故只要判断数字的最少次数和最多次数差距不大于 $1$ 即可。

时间复杂度: $\mathcal{O(n)}$

void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    vector<int>cnt(10);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    for(int i=1;i<=9;i++){
        for(int j=i+1;j<=9;j++){
            if(abs(cnt[i]-cnt[j])>1){
                cout<<"NO\n";
                return ;
            }
        }
    }
    cout<<"YES\n";
}

C. 小红走网格

对于行列移动本质上是分离的。

考虑行移动，每次能向上移动 $a$ 个单位或向下移动 $b$ ，那么对于 $\gcd(a,b)$ 的倍数都可以达到，所以只需要判断 $y$ 是否是 $\gcd(a,b)$ 的倍数即可。

对于列移动同理。

时间复杂度: $\mathcal{O(T\times log(n))}$ ，其中 $n$ 是移动的距离。

void solve(){
    i64 a,b,c,d,x,y;
    cin>>x>>y>>a>>b>>c>>d;
    i64 g1=gcd(c,d);
    i64 g2=gcd(a,b);
    if(x%g1==0&&y%g2==0){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

D.隐匿社交网络

假设两个数字在二进制位上存在某位都是 $1$ ，那么其必然满足 $x \operatorname{AND} y≥1$ 。

我们可以按位分成 $63$ 个类，若一个数在对应位上是 $1$ ，则把它放进对应的容器里。

那么就可以考虑按位并查集，先把可以合并的位合并，然后合并对应容器里的数字，再归纳去重即可。

最后比较容器里的数字个数，最多的便是答案。

时间复杂度: $\mathcal{O(n\times log(max(a)))}$

void solve(){
    int n;
    cin>>n;
    vector<i64>a(n+1);
    vector<int>p(64);
    iota(p.begin(),p.end(),0);
    auto find=[&](auto &&self,int x)->int {
        if(p[x]==x) return x;
        p[x]=self(self,p[x]);

        return p[x];
    };
    vector<vector<int>>vv(64);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vector<int>v;
        for(int j=0;j<=63;j++){
            if(a[i]>>j&1){
                v.push_back(j);
            }
        }  
        vv[v[0]].push_back(i);
        for(int j=1;j<v.size();j++){
            vv[v[j]].push_back(i);
            int f1=find(find,p[v[j]]);
            int f2=find(find,p[v[j-1]]);
            if(f1!=f2){
                p[f1]=p[f2];
                
            }
        }
    }
    vector<vector<int>>ans(64);
    for(int i=0;i<=63;i++){
        int fa=find(find,i);
        for(auto t:vv[i]){
            ans[fa].push_back(t);
        }
    }
    int res=0;
    for(int i=0;i<=63;i++){
        sort(ans[i].begin(),ans[i].end());
        ans[i].erase(unique(ans[i].begin(),ans[i].end()),ans[i].end());
        res=max(res,(int)ans[i].size());
    }
    cout<<res<<"\n";
}

E.1or0

题意转化为求询问区间有多少个子区间包含 $1$ 。

那么我们可以转化为询问区间的子区间个数减去区间中不包含 $1$ 的区间个数。

先使用前缀和统计到 $i$ 时全是 $0$ 的子区间个数。

再用序列自动机预处理对于任意 $i$ 其前缀和后缀中最远的 $0$ 的位置，使得 $i$ 到该位置的字符全是 $0$ 。

对于 $[l,r]$ ，如果 $s_l=1$ ，那么说明答案便可以直接用 $r-l+1-(ans_r-ans_{l-1})$ ，因为该区间是不会存在 $0$ 和前面的位置产生新的全 $0$ 区间。 alt

如果 $s_l=0$ ，说明我们多减去了如果红色乘以蓝色的区间个数，再加上即可，当然蓝色区间可能超过 $r$ ，所以还要对 $r$ 取一下较小值。

时间复杂度: $\mathcal{O(n)}$

void solve(){
    int n;
    string s;
    cin>>n>>s;
    s=" "+s;
    vector<i64>ans(n+2);
    int idx=-1;
    vector<int>pre(n+5,-1);
    vector<int>suf(n+5,-1);
    for(int i=1;i<=n;i++){
        ans[i]=ans[i-1];
        pre[i]=pre[i-1];
        if(s[i]=='0'){
            if(idx==-1){
                ans[i]+=1;
            }else{
                ans[i]+=(i-idx+1);
            }
            if(idx==-1) idx=i;
        }else{
            idx=-1;
        }
        if(s[i]=='0'&&(s[i-1]=='1'||i-1==0)){
            pre[i]=i;
        }
    }
    suf[n]=(s[n]=='0'?n:-1);
    for(int i=n-1;i>=1;i--){
        suf[i]=suf[i+1];
        if(s[i]=='0'&&s[i+1]=='1'){
            suf[i]=i;
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l=-1,r=-1;
        cin>>l>>r;
        i64 len=r-l+1;
        i64 sum=(1+len)*len/2;
        sum-=ans[r]-ans[l-1];
        if(s[l]=='0'){
            int right=min(suf[l],r);
            int left=pre[l];
            sum+=1LL*(right-l+1)*(l-left);
        }
        cout<<sum<<"\n";
    }
}

F.计树

首先我们先记录哪些结点为给定的目标结点，接着对每个结点 $u$ 考虑它作为目标结点 $LCA$ 的次数。

同时记录对于第 $i$ 个结点的子树下的目标结点数量为 $num_i$ 。

对于任意一个 $u$ 的子结点 $v$ ，我们考虑对于已经遍历的 $v$ 的兄弟结点的子树下的目标结点数量为 $x$ ，那么此时 $u$ 作为 $LCA$ 新增的次数就是 $num_v\times x$ 。

特别地，若该结点是目标结点，可作为自身的 $LCA$ 。

时间复杂度: $\mathcal{O(n)}$

void solve(){
    int n;
    cin>>n;
    vector<vector<int>>e(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int k;
    cin>>k;
    vector<bool>ok(n+1,false);
    for(int i=1;i<=k;i++){
        int s;
        cin>>s;
        ok[s]=true;
    }
    vector<i64>ans(n+1);
    vector<i64>num(n+1);
    auto dfs=[&](auto &&self,int u,int fa)->void {
        i64 temp=0;
        if(ok[u]) temp++;
        for(auto v:e[u]){
            if(v==fa) continue;
            self(self,v,u);
            ans[u]+=num[v]*temp*2;
            temp+=num[v];
            num[u]+=num[v];
        }
        if(ok[u]) num[u]++;
        if(ok[u]) ans[u]++;
        
    };
    dfs(dfs,1,-1);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
}