题解 P4978 【赌神：决斗】

· · 题解

给出两种做法

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);
}