欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客多校第二场(G题)Greater and Greater

程序员文章站 2022-04-02 19:02:14
...

Greater and Greater

------------------------------------------------------------------------

原题

题目描述:给定大小为n的序列A和大小为m的序列B,计算A中所有大小为m的子区间S,满足
2020牛客多校第二场(G题)Greater and Greater
输入描述:
第一行:两个整数n,m(1≤n≤150000,1≤m≤min{n,40000}).
第二行:n个整数A1,A2…An(1≤Ai≤10^9)
第三行:m个整数B1,B2…Bm (1≤Bi≤10^9)

输出描述:
只有一行,表示答案。

样例输入:

6 3
1 4 2 8 5 7
2 3 3

样例输出:

2
------------------------------------------------------------------------

分析:

题解思路:
考虑bitset,对每个A求一个长为m的bitset Si,其中Si[j]=1当且仅当Ai≥Bj。注意到本质只有O(m)种不同的bitset,具体就是把m个数排完序之后,第i个bitset就在第i-1个bitset的基础上在第i大的数对应的位置多一个1,所以预处理这些bitset复杂度是O(m2/w)的。再设n个长为m的bitset,记为curi,其中 curi[j]=1当且仅当∀k∈[ j,m],Ai+k-j ≥Bk。可知有:curi= ((curi+1 >>1)|Im)& Si其中Im表示一个只有第m位为1的bitset。所以只要统计有多少个curi的curi[1]=1即可,这就是最后的答案。写代码的时候可以不用把每个curi都存起来,只弄一个cur然后不断滚动就可以了。
时间复杂度:O(nm/W)
比赛的时候还以为是魔改KMP,结果被出题人预判了我的预判…

------------------------------------------------------------------------

这是出题人给的题解:

#include<bits/stdc++.h>
using namespace std;
#define N 150005
#define M 40005
int n,m,ans,A[N],B[M],Ord[M];
bitset<M> cur,Bs[M];
int cmp(int x,int y)
{
	return B[x]<B[y];
}
int GetRank(int x)
{
	int l=0,r=m;
	while(l<r)
	{
		int mid=l+r>>1;
		if(x<B[Ord[mid]])
			r=mid;
		else l=mid+1;
	}
	return l;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d",A+i);
	for(int i=0;i<m;i++)
	{
		scanf("%d",B+i);
		Ord[i]=i;
	}
	sort(Ord,Ord+m,mcp);
	for(int i=1;i<=m;i++)
	{
		Bs[i]=Bs[i-1];
		Bs[i].set(Ord[i-1]);
	}
	for (int i=n-1;i>=0;i--)
	{
		cur>>=1;
		cur&=Bs[GetRank(A[i])];
		if(A[i]>=B[m-1]) cur.set(m-1);
		ans+=cur[0];
	}
	printf("%d\n",ans);
}
------------------------------------------------------------------------

以下是我自己写的

#include<bits/stdc++.h>
using namespace std;
const int MAXN=15e4+5;
bitset<MAXN> bt,ans;
int n,m,a[MAXN],b[MAXN],ad[MAXN],bd[MAXN];
int cmp1(int x,int y)
{
	return a[x]>a[y];
}
int cmp2(int x,int y)
{
	return b[x]>b[y];
}
int main()
{
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i);
			ad[i]=i;
		}
    for(int i=1;i<=n-m+1;i++)
		ans[i]=1;
    for(int i=1;i<=m;i++)
		{
			scanf("%d",b+i);
			bd[i]=i;
		}
    sort(ad+1,ad+n+1,cmp1);
	sort(bd+1,bd+m+1,cmp2);
    for(int i=1,j=1;i<=m;i++)
	{
        while(j<=n&&a[ad[j]]>=b[bd[i]])
		{
            bt[ad[j]]=1;
			j++;
        }
		ans&=bt>>bd[i]-1;
    }
	printf("%d\n",ans.count());
}
相关标签: 动态规划 bitset