专栏文章

题解：P11843 [USACO25FEB] The Best Subsequence G

nningyy
P11843题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@min48adw
此快照首次捕获于
2025/12/01 20:18
3 个月前
此快照最后确认于
2025/12/01 20:18
3 个月前
查看原文

题意

有一段 0,10,1 序列，给定一个区间和长度，求区间中所有对应长度的子序列中字典序最大的一个。

思路

首先对应 0,10,1 串的处理，先离散化，然后异或差分，最后前缀和一下就可以得到对应的每段序列了。
考虑贪心选取子序列，如果 11 的个数大于序列长度，那么全选 11 即可，否则选完所有 11 之后再从后往前挑选一些 00 放进去，这样一定是不劣的。
所以我们可以在区间里二分，取 l∼mid−1l\sim mid-1 里的 11 以及 mid∼rmid\sim r 里的所有数，11 的个数可以提前前缀和预处理。
最后输出答案，前面全为 11 的部分直接快速幂即可，后面的部分可以用类似哈希的方法预处理，然后这题就做完了，但是代码不好写。

代码

有点难调，代码写的很屎（尤其是取模这一块），将就着看吧。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,Planetary_system=1e9+7;
int n,m,q,nm;
struct node{
	int l,r,x;
}Q[N],M[N];
bool a[N<<2];
int cnt[N<<2];
int H[N<<2];
int ls[N<<2];
int Pow(int k){
	if(k<63) return (1ll<<k)%Planetary_system;
	int x=Pow(k>>1ll);
	if(k&1ll) return ((x*x%Planetary_system)<<1ll)%Planetary_system;
	return x*x%Planetary_system;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	// freopen("bestsub.in","r",stdin);
	// freopen("bestsub.out","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>M[i].l>>M[i].r;
		ls[++nm]=M[i].l;ls[++nm]=M[i].r+1;
	}
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r>>Q[i].x;
		ls[++nm]=Q[i].l;ls[++nm]=Q[i].r+1;
	}
	ls[++nm]=n+1;
	ls[++nm]=1;
	sort(ls+1,ls+nm+1);
	nm=unique(ls+1,ls+nm+1)-ls-1;
	for(int i=1;i<=m;i++){
		a[lower_bound(ls+1,ls+nm+1,M[i].l)-ls]^=1;
		a[lower_bound(ls+1,ls+nm+1,M[i].r+1)-ls]^=1;
	}
	for(int i=1;i<=nm;i++){
		a[i]^=a[i-1],cnt[i]=cnt[i-1]+a[i-1]*(ls[i]-ls[i-1]);
		H[i]=((H[i-1]*Pow(ls[i]-ls[i-1])%Planetary_system)+a[i-1]*(Pow(ls[i]-ls[i-1])-1+Planetary_system)%Planetary_system)%Planetary_system;
	}
	for(int i=1,l,r,x;i<=q;i++){
		l=Q[i].l,r=Q[i].r,x=Q[i].x;
		int lsl=lower_bound(ls+1,ls+nm+1,l)-ls;
		int lsr=lower_bound(ls+1,ls+nm+1,r+1)-ls;
		if(cnt[lsr]-cnt[lsl]>=x){
			cout<<(Pow(x)-1+Planetary_system)%Planetary_system<<"\n";
			continue;
		}
		int L=l,R=r,ans;
		while(L<=R){
			int mid=(L+R)>>1;
			int lsmid=upper_bound(ls+1,ls+nm+1,mid)-ls-1;
			if(a[lsmid]*(mid-ls[lsmid])+cnt[lsmid]-cnt[lsl]+(r-mid+1)>=x) ans=mid,L=mid+1;
			else R=mid-1;
		}
		int lsans=upper_bound(ls+1,ls+nm+1,ans)-ls-1;
		cout<<((Pow(a[lsans]*(ans-ls[lsans])+cnt[lsans]-cnt[lsl])-1+Planetary_system)%Planetary_system*Pow(r-ans+1)%Planetary_system
			+(H[lsr]
			-(H[lsans]*Pow(ans-ls[lsans])%Planetary_system+a[lsans]*(Pow(ans-ls[lsans])-1+Planetary_system)%Planetary_system)
			*Pow(r-ans+1)%Planetary_system+Planetary_system)%Planetary_system)%Planetary_system
			<<"\n";
	}
	return 0;
}
/*
*/

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...