牛客周赛77文字版题解

A.时间表

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

时间复杂度:

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

B.数独数组

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

时间复杂度:

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. 小红走网格

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

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

对于列移动同理。

时间复杂度:,其中 是移动的距离。

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.隐匿社交网络

假设两个数字在二进制位上存在某位都是 ,那么其必然满足

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

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

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

时间复杂度:

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

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

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

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

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

对于 ,如果 , 那么说明答案便可以直接用 ,因为该区间是不会存在 和前面的位置产生新的全 区间。 alt

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

时间复杂度:

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.计树

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

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

对于任意一个 的子结点 ,我们考虑对于已经遍历的 的兄弟结点的子树下的目标结点数量为 ,那么此时 作为 新增的次数就是

特别地,若该结点是目标结点,可作为自身的

时间复杂度:

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]<<" ";
    }
}
全部评论
交作业:
2 回复 分享
发布于 01-20 16:16 江苏
那个E题涉及啥知识点呀,萌新看不懂
1 回复 分享
发布于 01-20 08:51 江西
有python题解吗
点赞 回复 分享
发布于 01-20 18:58 河南

相关推荐

Java抽象带篮子:你这实习经历没突出亮点啊,怎么包装实习经历可以看看我的置顶帖子。冲春招可以看看我的置顶帖子[偷笑R]帖子里写了怎么改简历,怎么包装实习经历,还有2个高质量可速成的项目话术,和我的牛客八股笔记专栏
点赞 评论 收藏
分享
评论
8
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务