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

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);
	}
}