题解：CF1983F array-value

这里提供一种比较好写的时间复杂度

O(n\log V)

的做法。

套路地，对于求第

k

小问题，通过二分答案转化成求

< x

的方案数问题。直接做并不好做，考虑扫描线，记录每个点为右端点时的最优左端点，于是只需要考虑单个数的匹配。

注意到

a_i \oplus a_j <x

的左侧异或和并不好做，转而对右侧进行拆分，对于其二进制的第

k

位的 1，将贡献拆成“要求异或和的

k

位之前与

x

相同，第

k

位为 0，其余无要求”。

0 的限制是平凡的，只需要这几位都取相同即可；对于 1 的限制，注意到这一位的取 0 或 1 均无关，所以等价于无限制。此时我们只要对于拆成的每个贡献计算只保留元素对应 0 位的二进制值即可，此时问题等价于求等值前驱，容易维护。此时时间复杂度

O(n\log^2 V)

。

考虑在二进制问题中二分答案的另一种表现形式，拆位贪心。当我们从高到低逐位考虑时，每次只会加入 1 条限制，直接在匹配数组上取最大值即可，单次只需要扫一次数组。

用哈希表实现前驱，时间复杂度

O(n\log V)

。

CPP

#include<bits/stdc++.h>
#define maxn 510005
#define int long long
using namespace std;

int n,k,a[maxn],pre[maxn];
unordered_map<int,int>mp;
int check(int x){
	mp.clear();
	int res=0,maxx=0;
	for(int i=1;i<=n;i++){
		int cur=a[i]&x;
		maxx=max(maxx,pre[i]);
		if(mp.count(cur)) maxx=max(maxx,mp[cur]);
		mp[cur]=i;
		res+=maxx;
		if(res>=k) return 0;
	}
	return 1;
}
void update(int x){
	mp.clear();
	for(int i=1;i<=n;i++){
		int cur=a[i]&x;
		pre[i]=max(pre[i],pre[i-1]);
		if(mp.count(cur)) pre[i]=max(pre[i],mp[cur]);
		mp[cur]=i;
	}
}
void solve(){
	int x=0;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),pre[i]=0;
	for(int i=30;i>=0;i--){
		if(check(~(x|((1<<i)-1)))) update(~(x|((1<<i)-1))),x|=(1<<i);
	}
	printf("%lld\n",x);
}
signed main(){
	signed T=1;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

题解：CF1983F array-value

文章操作

相关推荐

评论

题解：CF1983F array-value