自动搬运

查看原文

来自洛谷，原作者为

	Hope2075 时间的流沙，淹没梦境里的夏

搬运于2025-08-24 22:05:50，当前版本为作者最后更新于2019-04-02 21:58:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出两种做法

1.双指针

首先每个人取出的牌的组合很有限，最多2001000个

所以求出每个人的组合就行

求出前缀和，然后枚举两个端点作差就可以

求完后，对两个人的所有组合排序

然后用双指针扫一遍

具体是这样的：

枚举i，随后移动j，如果j指向一个更大的元素，就停止移动

随后计数器加上j

这样就能求出所有能胜利的方案数

最后求答案就简单了，直接用合法方案数除以总方案数就行

这样时间复杂度是$O(N^2\log N)$的

如果排序改成基数排序，就可以做到$O(n^2)$

我就是这么干的

然后总用时1749ms（氧化），但是内存开销比较大

记录

就这样成为了最优解第一名

2.二分

对一个数组排序，然后枚举另一个

随后二分一个位置，使得在另一个数组中满足要求

这样时间复杂度是$O(N^2\log N)$的

总用时5372ms（氧化），明显较慢，但能过

记录

最后是代码

双指针法：

#include<cstdio>
using namespace std;
const int N=2048;
const long long M=998244353;
int n,m;
long long a[N],b[N];
long long p[N*N/2],q[N*N/2];
int read(){
	int n=0;char c;
	c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		n=n*10+c-'0';
		c=getchar();
	}
	return n;
}
void sort(long long *beg,long long *end){
	long long* s=new long long[end-beg];
	long long* t=s+(end-beg);
	long long*ss;
	int* cnt=new int[65537];
	for(int p=0;p<4;p++){
		long long r=((1ll<<((p+1)*16))-1);
		for(int i=0;i<=65536;i++)cnt[i]=0;
		cnt++;
		for(long long *i=beg;i<end;i++)cnt[((*i)&r)>>(p*16)]++;
		cnt--;
		for(int i=1;i<65536;i++)cnt[i]+=cnt[i-1];
		for(long long *i=beg;i<end;i++)s[cnt[((*i)&r)>>(p*16)]++]=(*i);
		ss=beg;beg=s;s=ss;
		ss=end;end=t;t=ss;
	}
	delete[] s;
	delete[] cnt;
}
long long cnt;
long long arc(long long a){
	int p=M-2;
	long long ans=1;
	while(p){
		if(p&1)ans=ans*a%M;
		p>>=1;
		a=a*a%M;
	}
	return ans;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read()+a[i-1];
	}
	for(int i=1;i<=m;i++){
		b[i]=read()+b[i-1];
	}
	int t1=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<i;j++){
			p[t1++]=a[i]-a[j];
		}
	}
	int t2=0;
	for(int i=0;i<=m;i++){
		for(int j=0;j<i;j++){
			q[t2++]=b[i]-b[j];
		}
	}
	sort(p,p+t1);
	sort(q,q+t2);
	int i,j;
	i=0;j=0;
	while(i<t1){
		while(p[i]>q[j]&&j<t2)j++;
		cnt+=j;
		cnt%=M;
		i++;
	}
	printf("%lld\n",cnt);
	cnt=cnt*arc(t1)%M*arc(t2)%M;
	printf("%lld\n",cnt);
}

二分法

#include<cstdio>
using namespace std;
const int N=2048;
const long long M=998244353;
int n,m;
long long a[N],b[N];
long long p[N*N/2],q[N*N/2];
int read(){
    int n=0;char c;
    c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        n=n*10+c-'0';
        c=getchar();
    }
    return n;
}
void sort(long long *beg,long long *end){
    long long* s=new long long[end-beg];
    long long* t=s+(end-beg);
    long long*ss;
    int* cnt=new int[65537];
    for(int p=0;p<4;p++){
        long long r=((1ll<<((p+1)*16))-1);
        for(int i=0;i<=65536;i++)cnt[i]=0;
        cnt++;
        for(long long *i=beg;i<end;i++)cnt[((*i)&r)>>(p*16)]++;
        cnt--;
        for(int i=1;i<65536;i++)cnt[i]+=cnt[i-1];
        for(long long *i=beg;i<end;i++)s[cnt[((*i)&r)>>(p*16)]++]=(*i);
        ss=beg;beg=s;s=ss;
        ss=end;end=t;t=ss;
    }
    delete[] s;
    delete[] cnt;
}
long long cnt;
long long arc(long long a){
    int p=M-2;
    long long ans=1;
    while(p){
        if(p&1)ans=ans*a%M;
        p>>=1;
        a=a*a%M;
    }
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read()+a[i-1];
    }
    for(int i=1;i<=m;i++){
        b[i]=read()+b[i-1];
    }
    int t1=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++){
            p[t1++]=a[i]-a[j];
        }
    }
    int t2=1;
    for(int i=0;i<=m;i++){
        for(int j=0;j<i;j++){
            q[t2++]=b[i]-b[j];
        }
    }
    sort(q+1,q+t2);
    q[t2]=0x7fffffffffffffffLL;
    for(int i=1;i<=t1;i++){
        int l=1,r=t2+1,mid;
        while(l!=r){
            mid=((l+r)>>1);
            if(q[mid]>=p[i]){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        cnt+=l-1;
        cnt%=M;
    }
    cnt=cnt*arc(t1-1)%M*arc(t2-1)%M;
    printf("%lld\n",cnt);
}