CSP S 策略游戏

novax · 2022-10-30 22:14:33 · 题解

闲话：我是没有代码能力的小丑/dk。

考场思路，但赛时没写完。

题意

给定两个区间，先手在 A 序列给定区间内选择一个数，后手在 B 序列给定区间内选另一个数。两人所选数字乘积为得分。先手希望得分尽量大，后手希望得分尽量小。

部分分

特殊性质一：“权值为正”

因为不存在相乘正负性改变的问题。由双方策略可知，先手必然选择区间内最大值，后手必然选择区间内最小值。因此使用线段树/ST表维护区间内最大值和最小值即可。

特殊性质二：存在一方的操作区间长度为 1

若先手操作区间长度为 1，则有如下几种情况：

1. 先手必须选的数是 0，此时答案是 0。

2. 先手必须选的数是正数，此时后手策略为选择其区间内的最小数。

3. 先手必须选的数是负数，此时后手策略为选择其区间内的最大数。

后手同理：

1. 后手必须选的数是 0，此时答案是 0。

2. 后手必须选的数是正数，此时先手策略为选择其区间内的最大数。

3. 后手必须选的数是负数，此时后手策略为选择其区间内的最小数。

可以证明，按照上述规则选数可以达成两人的最优策略。

使用线段树/ST表维护区间最大值和最小值，按照上述规则讨论即可。

正解

此时双方的操作区间内都有多个数，其中双方的最优策略会使相乘的正负号改变。因此，我们应该按照双方操作区间内的正负数存在情况进行讨论。

我的做法将所有情况分为八类。以下的“最小”“最大”均指数本身的值而不是绝对值。

1. 后手无负数。

   1.1 若此时先手有正数，则先手应选择区间内最大的正数来使结果尽可能大。若后手有区间内 0，则后手应选择 0 使得答案最小；否则他会选择区间内最小的正数。

   1.2 若此时先手无正数，则若先手有 0 则一定会选择 0，否则相乘结果为负，他会选择区间内最大的负数来使相乘的结果尽量大。此时后手选择区间内最大的正数。

2. 后手无正数。

   2.1 若此时先手有负数，他一定会选择区间内最小的负数，负负得正来使结果最大化。后手区间如果有 0 则一定优先选择 0，否则选择区间内最大的负数。

   2.2 若此时先手无负数，则结果必然不大于 0，先手区间若有 0 则必定优先选 0，否则选择其区间内最小的正数；后手则选择其区间内的最小负数来最小化结果。

3. 后手既有正数又有负数

   3.1 先手有 0，则先手选 0。除 0 以外，先手无论选什么，后手都有应对策略使结果为负。

   3.2 先手无正数。此时先手选择区间内最大的负数，而后手选择区间内最大的正数。

   3.3 先手无负数。此时先手选择区间内最小的正数，而后手选择区间内最小的负数。

   3.4 先手既有正数也有负数。此时先手可能如3.2中选择区间内最大的负数，也可能如3.3中选择区间内最小的正数。由于先手有优先决策的权力，所以他会会选择3.2和3.3两种结果中更大的那一个。即答案为 \max(\text{先手最大负数}\times \text{后手最大正数},\text{先手最小正数}\times \text{后手最小负数})。

自此，我们的八种情况就讨论完了。

另外以上还有一种情况没有考虑在内：后手操作区间内只有 0，此时答案一定为 0。程序中可以将这种情况并入到以上的情况中。

为进行以上的分类讨论，我们需要维护以下信息：区间最大/最小正数、区间最大/最小负数、区间是否有 0。使用线段树或ST表维护上述信息，按上述分类讨论即可。

假设 n,m 同级，使用线段树的时间复杂度为 O(n+q\log n)，ST表的时间复杂度为 O(n\log n +q)。均可通过本题。

代码

#include <cstdio>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
const int Nx=100010;
int N,M,Q,A[Nx],B[Nx];
struct node{long long maz,miz,maf,mif,zro;};
node As[4*Nx],Bs[4*Nx];
void pushnode(node &a,int val)
{
    if(val==0)
        a.zro=1;
    else if(val>0)
        a.maz=a.miz=val;
    else if(val<0)
        a.maf=a.mif=val;
}
node merge(node x,node y)
{
    node ret;
    ret.zro=x.zro||y.zro;
    if(!x.maz||!y.maz)
    {
        ret.maz=x.maz+y.maz;
        ret.miz=x.miz+y.miz;
    }
    else
    {
        ret.maz=max(x.maz,y.maz);
        ret.miz=min(x.miz,y.miz);
    }
    if(!x.maf||!y.maf)
    {
        ret.maf=x.maf+y.maf;
        ret.mif=x.mif+y.mif;
    }
    else
    {
        ret.maf=max(x.maf,y.maf);
        ret.mif=min(x.mif,y.mif);
    }
    return ret;
}
void build(int ll,int rr,int p,node seg[],int C[])
{
    if(ll==rr)
    {
        pushnode(seg[p],C[ll]);
        return;
    }
    int mid=(ll+rr)>>1;
    build(ll,mid,ls(p),seg,C);
    build(mid+1,rr,rs(p),seg,C);
    seg[p]=merge(seg[ls(p)],seg[rs(p)]);
}
node query(int ll,int rr,int p,int L,int R,node seg[])
{
    if(L<=ll&&rr<=R)
        return seg[p];
    int mid=(ll+rr)>>1;
    if(L>mid)
        return query(mid+1,rr,rs(p),L,R,seg);
    if(R<=mid)
        return query(ll,mid,ls(p),L,R,seg);
    return merge(query(ll,mid,ls(p),L,R,seg),query(mid+1,rr,rs(p),L,R,seg));
}
long long get_ans(node ax,node bx)
{
    long long ret;
    //printf("%d %d %d %d %d   %d %d %d %d %d\n",ax.maz,ax.miz,ax.maf,ax.mif,ax.zro,bx.maz,bx.miz,bx.maf,bx.mif,bx.zro);
    if(bx.mif!=0&&bx.miz==0)//后手无正数
    {
        if(ax.mif!=0)//先手有负数
            ret=(bx.zro)?0:ax.mif*bx.maf;
        else//先手无负数
            ret=(ax.zro)?0:ax.miz*bx.mif;
    }
    else if(bx.mif==0&&bx.miz!=0)//后手无负数
    {
        if(ax.miz!=0)//先手有正数
            ret=(bx.zro)?0:ax.maz*bx.miz;
        else//先手无正数
            ret=(ax.zro)?0:ax.maf*bx.maz;
    }
    else//后手正负都有/后手只有0
    {
        if(ax.zro)
            ret=0;
        else if(ax.mif!=0&&ax.miz==0)//先手无正数
            ret=ax.maf*bx.maz;
        else if(ax.mif==0&&ax.miz!=0)//先手无负数
            ret=ax.miz*bx.mif;
        else//先手正负都有
            ret=max(ax.miz*bx.mif,ax.maf*bx.maz);
    }
    return ret;
}
int main()
{
    scanf("%d%d%d",&N,&M,&Q);
    int i,j,k,la,ra,lb,rb;
    for(i=1;i<=N;i++)
        scanf("%d",&A[i]);
    for(i=1;i<=M;i++)
        scanf("%d",&B[i]);
    build(1,N,1,As,A);
    build(1,M,1,Bs,B);
    node ax,bx;
    while(Q--)
    {
        scanf("%d%d%d%d",&la,&ra,&lb,&rb);
        ax=query(1,N,1,la,ra,As);
        bx=query(1,M,1,lb,rb,Bs);
        printf("%lld\n",get_ans(ax,bx));
    }
}