重生之我要当分子

发布于昨天 21:04 河南

+ 关注

牛客周赛72文字版题解

周赛72

写在前面

这期的周赛感觉难度偏高了， $B,C,D$ 难度整体高了一个档次。

在验题时虽然 $F$ 偏典，为了不用 $\text{lazybitset}$ ，想用 $segtree$ ，所以也写了老久，建议都写写这个 $F$ ，使用左边右开的技巧和 $lazy$ 标记的转化个人感觉还是不错的。

如果存在疑问，留言评论区，看到会及时回复的，赛时写了题解，饿了，先吃饭去了喵。

A.小红的01串(一)

直接遍历一遍，求 $s_i \neq s_{i-1}$ 的个数即可。

void solve(){
    string s;
    cin>>s;
    int ans=0;
    for(int i=1;i<s.size();i++){
        ans+=s[i]!=s[i-1];
    }
    cout<<ans<<'\n';
}

B.小红的01串(二)

不难发现如果一个子串满足题意，那么它的所有子串都会满足题意，所以对于每个 $i$ ，找到最右边的 $j(j>i)$ 使得该串满足题意，对于这段区间的答案就是 $(j-i)*(1+j-i)/2$ ，然后找到后把 $i$ 跳到 $j$ 的位置，继续找即可。

void solve(){
    string s;
    cin>>s;
    i64 ans=0;
     
    for(int i=0;i<s.size();i++){
        int r=i;
        while(r+1<s.size()&&s[r+1]!=s[r]) r++;
        if(r>i)ans=ans+1LL*(r-i)*(1+r-i)/2;
        i=r;
    }
    cout<<ans<<'\n';
}

C.小红的01串(三)

当使用最少的 $0、1$ 构造时，只有两种情况，即 $010101...$ 和 $101010...$ 。

对于第一种情况，最少所需 $0$ 的个数就是 $(k+1)/2$ ，最少所需 $1$ 的个数就是 $k/2$ 。对于剩下的 $0$ 可以直接放在最前面，对于剩下的 $1$ 可以放在任意一个 $1$ 的后面。

对于第二种情况，跟 $1$ 同理。

对于这样的做法，需要特判 $k=0$ 时，无解。

void solve(){
    int a,b,k;
    cin>>a>>b>>k;
    bool ok=true; 
    if(k==0){
        if(a&&b){
            cout<<"-1\n";
            return ;
        }
    }
    if(a>=(k+1+1)/2&&b>=(k+1-(k+1+1)/2)){
        for(int i=1;i<=a-(k+1+1)/2;i++) cout<<0;
        for(int i=1;i<=k+1;i++){
            if(i&1) {
                cout<<0;
            }
            else{
                if(ok){
                    ok=false;
                    for(int j=1;j<=b-(k+1-(k+1+1)/2);j++) cout<<1;
                }
                cout<<1;
            }
        }
        cout<<'\n';
    }else if(a>=(k+1-(k+1+1)/2)&&b>=(k+1+1)/2){
        for(int i=1;i<=b-(k+1+1)/2;i++) cout<<1;
        for(int i=1;i<=k+1;i++){
            if(i&1) {
                cout<<1;
            }
            else{
                if(ok){
                    ok=false;
                    for(int j=1;j<=a-(k+1-(k+1+1)/2);j++) cout<<0;
                }
                cout<<0;
            }
        }
        cout<<'\n';
    }else{
        cout<<"-1\n";
    }
}

D.小红的01串(四)

可以使用图论做法，验题时使用了 $dp$ 做法，所以写 $dp$ 。可以使用序列自动机维护出每个位置 $i$ 后面最近的 $0$ 和 $1$ 的位置，如果单纯使用的话，会出现位置的 $bug$ ，比如 $s_3=0$ ，那么第 $3$ 个位置后面的第一个 $0$ 会变成自己，所以再从前往后做一遍就可以了。

这样 $dp$ 转化成从第 $n$ 个位置出发，到第 $1$ 个位置结束的最小代价。这样对于每个 $i$ 就可以从 $suf_{i,0}$ 和 $suf_{i,1}$ 转移过来，然后取最小值即可。

void solve(){
    int n,x,y;
    cin>>n>>x>>y;
    string s;
    cin>>s;
    s=" "+s;
    vector<vector<int>>suf(n+2,vector<int>(2,-1));
    for(int i=n;i>=1;i--){
        suf[i][0]=suf[i+1][0];
        suf[i][1]=suf[i+1][1];
        if(s[i]=='0') suf[i][0]=i;
        else suf[i][1]=i;
    }
    for(int i=1;i<=n;i++){
        suf[i][0]=suf[i+1][0];
        suf[i][1]=suf[i+1][1];
    }
    vector<i64>dp(n+1,INF);
    dp[n]=0;
    for(int i=n-1;i>=1;i--){
        if(s[i]=='0'){
           if(suf[i][0]!=-1) {
                dp[i]=min(dp[i],dp[suf[i][0]]+x);
           }
           if(suf[i][1]!=-1) {
                dp[i]=min(dp[i],dp[suf[i][1]]+y);
           }
        }
        else{
            if(suf[i][0]!=-1) {
                dp[i]=min(dp[i],dp[suf[i][0]]+y);
           }
           if(suf[i][1]!=-1) {
                dp[i]=min(dp[i],dp[suf[i][1]]+x);
           }
        }
    }
    cout<<dp[1]<<'\n';
}

E.小红的01串(五)

根据数位取模的性质，如果一个数 $x$ 满足 $x \mod k=y$ ，那么其从高位累乘得到 $x$ 边取模 $k$ 的值也等于 $y$ 。

定义 $dp_{i,j}$ 表示前 $i$ 个位置，取模 $k$ 的值为 $j$ 的方案总数。

那么对于 $dp_{i,j}$ 来说：如果 $s_{i+1}=1$ ，那么 $dp_{i+1,(j*10+1)\mod 13}+=dp_{i,j}$ 如果 $s_{i+1}=0$ ，那么 $dp_{i+1,(j*10)\mod 13}+=dp_{i,j}$ 如果 $s_{i+1}=?$ ，那么上面两种情况都做一遍即可。

最后答案便是 $dp_{n,0}$ 。

void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    vector<vector<i64>>dp(n+1,vector<i64>(13,0));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=12;j++){
            if(s[i+1]=='0'){
                dp[i+1][j*10%13]+=dp[i][j];
            }
            else if(s[i+1]=='1'){
                dp[i+1][(j*10+1)%13]+=dp[i][j];
               
            }else if(s[i+1]=='?'){
                dp[i+1][j*10%13]+=dp[i][j];
                dp[i+1][(j*10+1)%13]+=dp[i][j];
            }
            dp[i+1][j*10%13]%=mod;
            dp[i+1][(j*10+1)%13]%=mod;
        }
    }
    cout<<dp[n][0]<<'\n';
}

F.小红的01串(六)

做法 $1$ ：

一眼可以发现是个线段树解决的问题。所以我们可以限制一个区间变成 $010101...$ 的最少次数。值域较大，考虑先离线离散化后再做更新和询问，每个点维护的是 $[i,i+1)$ (离散后的坐标) 的答案。对于合并区间时，当前区间的最少操作次数就等于左边的最少操作次数加上右边的最少操作次数，而此时右边的最少操作次数要根据左区间的长度是奇数还是偶数来确定。

对于操作 $1$ 来说，直接更新即可，最少操作次数就是区间奇数位的个数。

对于操作 $2$ 来说，答案就是更新为此区间的长度减去原有的答案。

$\text{Note}$ :可能存在反复更新的标记，需要引入 $lazy=3$ 的标记。当 $lazy=1$ 时，意思是只有操作 $1$ ，区间变成 $11111..$ ，答案就更新位区间奇数位的个数。当 $lazy=2$ 时， $0\oplus 2$ ，意思是只有操作 $2$ ,答案便是 $0000..$ 更改为 $010101...$ 的答案，便是区间中偶数位的个数。当 $lazy=3$ 时， $1\oplus 2$ ，在操作 $1$ 的基础上做 $2$ ，答案即区间长度减去原来答案，这里之所以没有 $2\oplus 1$ 是因为操作 $1$ 是直接赋值为 $1$ 。

对于操作 $3$ 来说，就是询问一个区间的答案，对于每个子区间，先判断它与询问区间的前缀长度关系，看此区间贡献的答案应该是 $01010...$ 还是 $10101...$ ，然后加上返回，最后比较一下 $01010...$ 和 $10101...$ 哪个更优。

做法 $2$ ：

科技版本的 $lazybitset$ ，可以参考 $\text{lazybitset}$ 的模板。 https://github.com/old-yan/CP-template/blob/4d155ec792ae50691e7cf0c5bd07fbbc935a5057/DS/LazyBitset.h#L691 个人感觉还是线段树好，毕竟赛场上也没时间抄板子，还可能抄错。附上内测时 $ac$ 代码，原理参考线段树，咱也不知道怎么又 $MLE$ 了。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74228311

#include<bits/stdc++.h>
using namespace std;
using i64=long long;
#define ls p<<1
#define rs p<<1|1
struct Map {
  vector<i64> alls;
  void add(i64 x) { alls.push_back(x); }
  void solve() {
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
  }
  int get(i64 x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (alls[mid] >= x)
        r = mid;
      else
        l = mid + 1;
    }
    return l + 1;
  }
};
const int N=2e5+5;
int flsh[N];
struct ASK{
    int op,l,r;
};
struct seg{
    int l,r,fl,fr; // [l,r)
    int ans,len;
    int lz;
}tree[N<<2];
void pushup(int p){
    int len=tree[ls].fr-tree[ls].fl;
    if(len&1){
        tree[p].ans=tree[ls].ans+(tree[rs].fr-tree[rs].fl-tree[rs].ans);
    }else{
        tree[p].ans=tree[ls].ans+tree[rs].ans;
    }
}
void pushdown(int p){
 if(tree[p].lz==1){
    tree[ls].lz=1;
    tree[rs].lz=1;
    tree[ls].ans=(tree[ls].fr-tree[ls].fl+1)/2;
    tree[rs].ans=(tree[rs].fr-tree[rs].fl+1)/2;
 }else if(tree[p].lz==2){
    tree[ls].lz=2;
    tree[rs].lz=2;
    tree[ls].ans=tree[ls].fr-tree[ls].fl-((tree[ls].fr-tree[ls].fl+1)/2);
    tree[rs].ans=tree[rs].fr-tree[rs].fl-((tree[rs].fr-tree[rs].fl+1)/2);
 }else if(tree[p].lz==3){
    tree[ls].lz^=3;
    tree[rs].lz^=3;
    tree[ls].ans=tree[ls].fr-tree[ls].fl-tree[ls].ans;
    tree[rs].ans=tree[rs].fr-tree[rs].fl-tree[rs].ans;
 }
 tree[p].lz=0;
}
void build(int p,int l,int r){
    tree[p].l=l;
    tree[p].r=r;
    if(l==r){
        tree[p].fl=flsh[l];
        tree[p].fr=flsh[r+1];
        //0101010
        tree[p].ans=(tree[p].fr-tree[p].fl)/2;
        tree[p].len=tree[p].fr-tree[p].fl;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[p].fl=tree[ls].fl;
    tree[p].fr=tree[rs].fr;
    tree[p].len=tree[p].fr-tree[p].fl;
    pushup(p);
}
void upt(int p,int l,int r,int op){
    if(tree[p].l>=l&&tree[p].r<=r){
       if(op==1){
        tree[p].lz=1;
        tree[p].ans=(tree[p].fr-tree[p].fl+1)/2;
       }else if(op==2){
        tree[p].lz^=3;
        tree[p].ans=tree[p].fr-tree[p].fl-tree[p].ans;
       }
       return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid)upt(ls,l,r,op);
    if(r>mid)upt(rs,l,r,op);
    pushup(p);
}
pair<int,int> query(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r){
        int L=flsh[l];
        int R=tree[p].fl-1;
        int len=R-L+1;
        len=max(len,0);
        if(len&1){
            return {tree[p].len-tree[p].ans,tree[p].len};
        }else{
            return {tree[p].ans,tree[p].len};
        }
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    auto [ans1,ans2]=make_pair(0,0);
    if(l<=mid){
        auto [ans3,ans4]=query(ls,l,r);
        ans1+=ans3;
        ans2+=ans4;
    }
    if(r>mid){
        auto [ans3,ans4]=query(rs,l,r);
        ans1+=ans3;
        ans2+=ans4;
    }
    return {ans1,ans2};
}
void solve(){
    int n,q;
    cin>>n>>q;
    vector<ASK>a(q);
    Map Z;
    for(int i=0;i<q;i++){
        cin>>a[i].op>>a[i].l>>a[i].r;
        Z.add(a[i].l);
        Z.add(a[i].r+1);
    }
    Z.add(1e9+1);
    //离散化
    Z.solve();
    int Sz=Z.alls.size();
    for(int i=0;i<q;i++){
        int w1=Z.get(a[i].l);
        int w2=Z.get(a[i].r+1);
        flsh[w1]=a[i].l;
        flsh[w2]=a[i].r+1;
    }
    flsh[Sz]=1e9+1;
    build(1,1,Sz-1);
    for(int i=0;i<q;i++){
        int w1=Z.get(a[i].l);
        int w2=Z.get(a[i].r+1);
        if(a[i].op<=2){
            upt(1,w1,w2-1,a[i].op);
        }else{
            auto [ans1,ans2]=query(1,w1,w2-1);
            cout<<min(ans1,ans2-ans1)<<"\n";
        }   
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--) {
        solve();
    }
    return 0;
}

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(2) 回帖

加载中...

话题同步到我的动态回帖

牛客周赛72文字版题解

周赛72

写在前面

A.小红的01串(一)

B.小红的01串(二)

C.小红的01串(三)

D.小红的01串(四)

E.小红的01串(五)

F.小红的01串(六)

做法 $1$ ：

做法 $2$ ：

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

牛客周赛72文字版题解

周赛72

写在前面

A.小红的01串(一)

B.小红的01串(二)

C.小红的01串(三)

D.小红的01串(四)

E.小红的01串(五)

F.小红的01串(六)

做法 ：

做法 ：

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐

做法 $1$ ：

做法 $2$ ：