题解：P10040 [CCPC 2023 北京市赛] 替换

fan_xiaoyi · 2026-05-13 11:19:38 · 题解

P10040 [CCPC 2023 北京市赛] 替换

思路

首先这个题字符串的每一位只有三种情况。
我们考虑用两个 bitset 来存，一个代表当前位是否为 1，另一个代表当前位是否为问号。
有一种暴力做法：先存前 k 位，然后再一组一组往后扩展，逻辑是第 i 位若是问号就改为 i-k 位的值。
这个暴力的时间复杂度是 O(\frac{n^2}{w\times k})，在 k 更大时更优。
还有另一种暴力：直接线性遍历枚举，时间复杂度为 O(n)。
显然这两种都无法单独通过本题，考虑数据分治。
设置阈值 B，当 k>B 时取第一种，否则取第二种。
那么操作总次数为 B\times n+\frac{n^2\ln n}{\ln B\times w}（后半部分是调和级数）。
那么我们考虑常数因子，将 B 取到 \sqrt n，可以通过本题。
莫名其妙地，将 B 取到 0 也可以通过本题，鉴定为数据过水常数优秀。

代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar((x%10)^48);
    }
}
using namespace std;
using namespace FastIO;
const int N=1e5+7;
int n,B;
bitset<N>a,q,now;
void work1(int k){
    rep(i,k+1,n)if(q[i]&&now[i-k])now[i]=1;
    print(now.count());puts("");
}
void work2(int k){
    for(int i=k;i<=n;i+=k)now=now|((now<<k)&q);
    print(now.count());puts("");
}
signed main(){
    read(n);
    rep(i,1,n){
        char c;
        cin>>c;
        if(c=='1')a[i]=1;
        if(c=='?')q[i]=1;
    }
    B=sqrt(n);
    rep(k,1,n){
        now=a;
        if(k<=B)work1(k);
        else work2(k);
    }
}