自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:02:32，当前版本为作者最后更新于2024-09-14 00:20:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定 $n$ 位 01 串 $S$，其中有一些通配符可以任意换成 $0/1$，求最大的 $k$ 使得存在 $i$ 满足 $S[i,i+k-1]=S[i+k,i+2k-1]$。

数据范围：$n\le 10^5$。

思路分析

这个问题显然很难做到 polylog 或者根号，因此考虑 std::bitset 优化。

从大到小枚举 $k$，某个位置 $i$ 不合法当且仅当 $S_i=0,S_{i+k}=1$ 或 $S_{i}=1,S_{i+k}=0$，std::bitset 维护为 $0/1$ 的位置，用右移和求交并操作可以维护出所有不合法位置 $i$ 的集合。

那么我们检验 $k$ 是否合法只要在这个集合中找到 $\ge k$ 的连续的 $0$。

对于 $k\le \omega$ 的情况可以 $\mathcal O(n)$ 暴力判断每个 $k$ 是否合法，其中 $\omega$ 为 std::bitset 字长。

对于 $k>\omega$ 的情况，这个 $0$ 区间一定跨越了 $>1$ 个长度为 $\omega$ 的块，我们可以遍历每个块并维护当前最长全 $0$ 后缀。

如果一个块非空，那么只有其最长 $0$ 前缀和后缀有可能有贡献，可以 __builtin_clz 和 __builtin_ctz 维护，需要手写 bitset。

时间复杂度 $\mathcal O\left(n\omega+\dfrac{n^2}\omega\right)$

代码呈现

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5,S=1575;
char s[MAXN];
int n;
ull f[S],g[S],t[S];
bool chk(int x) {
	for(int i=0,c=0;i+x<n;++i) {
		if(s[i]!='?'&&s[i+x]!='?'&&s[i]!=s[i+x]) c=0;
		else ++c;
		if(c>=x) return true;
	}
	return false;
}
void solve() {
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	scanf("%d%s",&n,s);
	for(int i=0;i<n;++i) {
		if(s[i]=='0') f[i>>6]|=1ull<<(i&63);
		if(s[i]=='1') g[i>>6]|=1ull<<(i&63);
	}
	for(int i=n/2;i>64;--i) {
		memset(t,0,sizeof(t));
		int ed=(n-i)>>6;
		for(int j=0,b=i>>6,r=i&63;j<=ed;++j) {
			ull F=f[j+b]>>r,G=g[j+b]>>r;
			if(r) F|=f[j+b+1]<<(64-r),G|=g[j+b+1]<<(64-r);
			t[j]=(F&g[j])|(G&f[j]);
		}
		for(int c=(n-i);c<((ed+1)<<6);++c) t[c>>6]|=1ull<<(c&63);
		int x=t[0]?__builtin_clzll(t[0]):64;
		for(int j=1;j<=ed;++j) {
			if(!t[j]) {
				if((x+=64)>=i) return printf("%d\n",i),void();
			} else {
				if(x+__builtin_ctzll(t[j])>=i) return printf("%d\n",i),void();
				x=__builtin_clzll(t[j]);
			}
		}
	}
	for(int i=min(n/2,64);i;--i) if(chk(i)) return printf("%d\n",i),void();
	puts("0");
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}