#C240729B. 周黑鸭(b)

网址（Website）

题目详情 - 周黑鸭(b) - Super

题解 - 周黑鸭(b) - Super

题解（Solution）

$\qquad$把序列中的 $0$ 看成 $-1$ ，$f()$ 函数的判断转化为求一段区间的和 $sum$ 是否大于 $0$ ，直接求前缀和数组 $s[]$ ，则 $f(l,r)=(s_r-s_{l-1}>0)=(s_r>s_{l-1})$ 。转化为定义正整数 $k$ 是好的，当且仅当 $\forall i\in[k,n]$ ，$s_{i-k}<s_i$。

$\qquad$固定左区间 $l$，如果 $(s_{l-1}< s_{l+k-1})== b_r$，则当前的 $k$ 是好的。

$\qquad$由于上述推理，考虑将 $s[]$ 排序，从大到小枚举。令 $tmp[k]$ 表示 $k$ 这个位置有没有被枚举过，如果有，那么所有 $tmp[p]==1$ 的位置的 $s[p]$ 一定大于其他的 $tmp[q]==0$ 的 $s[q]$ ；令当前枚举的 $s[i]$ 的位置为 $i$ ，则对于每一个 $k\in[1,n-i+1]$ ，有：

• 若 $tmp[i+k-1]=1$ ，则 $s_{i+k-1}>s_i$ ，则 $f(i,i+k-1)=1$ ，如果此时 $f$ 的值与 $b[i+k-1]$ 相同，则 $k$ 为好数，否则为坏数。
• 若 $tmp[i+k-1]=0$ ，则 $s_{i+k-1}\le s_i$ ，则 $f(i,i+k-1)=0$ ，如果此时 $f$ 的值与 $b[i+k-1]$ 相同，则 $k$ 为好数，否则为坏数。

$\qquad$易得这样做很明显是 $O(n^2)$ 的时间复杂度，于是考虑用 bitset 优化，因为每次要枚举区间 $[1,n-i+1]$ ，我们可以直接将 $tmp[]$ 用 bitset 存储，令 $ans[k]$ 表示 $k$ 是否为坏数，则对于每一个 $s[i]$ ，有 ans = ans|(tmp^b)>>i ，这样便可通过此题。

$\qquad$时间 $O(\frac{n^2}{\omega})$（bitset的 $\omega$ 大约为 $64$ 左右）。

$\qquad$注意：对于区间 $[1,x]$ ，判断 $f$ 函数应该用 $s_0<s_x$ ，因此需要将 $s_0$ 也计入排序数组中。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define fi first
#define se second
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;

char s1[N],s2[N];
int n;
bitset<N> ans,tmp,b;
struct Wolf{int s,id;}f[N];


signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>(s1+1)>>(s2+1);int Tim = clock();
	For(i,1,n) f[i]={f[i-1].s+(s1[i]=='1'?1:-1), i}, b[i]=s2[i]^'0';
	
	sort(f,f+n+1,[&](Wolf &a,Wolf &b){
		return a.s==b.s?a.id<b.id:a.s>b.s;
	});//要从0开始算 
	
	For(i,0,n){
		ans|=(tmp^b)>>f[i].id;
		tmp[f[i].id] = 1;
	}For(i,1,n) cout<<(!ans[i]);cout<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}