问一个做法

看起来大多数选手是对 ai 直接排序，枚举+双指针就做完了。

不过少部分选手（比如我），最开始的转化是将 ai 和 ai/2 放一起排序，并变成一个 1/2 序列，再去枚举，要统计很多种 pattern，比如 L_1_2_R，1_L_2_R，1_2_L_R，L_(2)_R 等，代码就非常难写，我在场上也是最后四五十分钟才调过。这里两种不同做法实现难度的比较，大家可以感受一下！

先是短做法（直接排序）：

CPP

sort(a+1,a+n+1);
for(int i=1,j=1;i<=n;i++)
{
	while(j<=n&&a[j]*2<=a[i])j++;
	for(int k=j,l=j;a[k]!=a[i];k++)
	{
		while(a[l]+a[k]>=a[i])l--;
		(ans+=pw[l]*C(n-k-1,m-n+i-2))%=mod;
	}
}
cout<<((pw[n]-ans)%mod+mod)%mod<<'\n';

下面是我的场上代码（核心部分）：

CPP

int nn=n+n;
sort(e+1,e+nn+1);
for(int i=1;i<=nn;++i){
	if(e[i].y==1)p1[e[i].x]=i;
	else p2[e[i].x]=i;
}
for(int i=1;i<=n;++i)pp[p1[i]]=p2[i],pp[p2[i]]=p1[i],ok[i]=0;
int he=0;
for(int i=1;i<=nn;++i){
	a1[i]=a1[i-1]+(e[i].y==1),a2[i]=a2[i-1]+(e[i].y==2);
	if(e[i].y!=2){
		continue;
	}
	int k=i+1,h1=0;
	int sx=m-2,bx=0,B1=0,B2=0;
	for(int j=i-1;j>=1;--j){
		while(1){
			if(pp[j]==i)break;
			if(e[j].y!=1||e[j].w>=e[i].w)break;
			int d1=a1[j-1]-(pp[i]<j),d2=a2[j-1]+B2-(pp[j]<i);
			int x=d2,y=d1-d2,cj=sx-x;
			if(cj<0||cj>y+x)break;
			while(k<=nn&&e[j].w+e[k].w>=e[i].w)h1+=(e[k].y==1),++k;
			int hb=x+y+h1+B1+bx+(pp[i]<j)+(pp[j]>i);
			he=(he+1ll*em[n-hb]*C[y+x][cj])%mod;
			break;
		}
		if(ok[e[j].x]==i)sx-=2,++bx,--B1,--B2;
		else{
			ok[e[j].x]=i;
			if(e[j].y==1)++B1;
			else ++B2;
		}
	}
}
he=(he+mod)%mod;
int ans=(em[n]-he+mod)%mod;
printf("%d\n",ans);

讨论操作

回复

相关推荐

问一个做法