飞起来

TruchyR · 2025-02-06 14:05:58 · 题解

这是一道结论题。结论比较好猜，这里将给出证明。

以下将两人选择视为两个区间。

然后如果两个区间有包含关系，容易发现不管怎么选择，区间短的那一方一定会赢。

所以我们将重心放在剩下的情况，以下作出几个限制来减少分讨个数。

先抛开题目中的字母，设甲选择了区间 [-a,a]，乙选择了区间 [b,b+2l]。
即甲区间长度为 2a，乙区间长度为 2l。
作出限制 a>0，b=ap，l=aq，p>-1，q\ge 1。
即乙的区间在甲右边，区间长度不小于甲。
甲的结果为 y_{甲}=(x+a)(x-a)=x^2-a^2。
乙的结果为 y_{乙}=(x-b)(x-b-2l)=x^2+b^2-2xb-2xl+2bl。

两个线段相对位置在左在右的关系显然没有影响，所以去除包含情况后不重不漏。

将甲的结果减去乙的结果：

y_{差} &= y_{甲}-y_{乙} \\ &= (x^2-a^2)-(x^2+b^2-2xb-2xl+2bl) \\ &= -a^2-b^2+2xb+2xl-2bl \\ &= 2x(p+q)a+a^2(1-p^2-2pq) \\ \end{aligned}

显然有 (p+q)a>0，所以这个式子的值随着 x 的增大而增大。

所以甲会尽可能往右选择，乙会尽可能往左选择；即一人选 a，一人选 b。

当 x=\dfrac{a+b}{2} 时式子可以化简为 y_{差}=-a^2(p-1)(q-1)。

当 q=1 时一定有 y_{差}=0，即平局。

当 p>1 时两区间不交，且区间更长的赢。

当 -1<p<1 时两区间有交，且区间更短的赢。

保证了两个序列互不相同所以 p≠0。

总结以上所有内容，于是我们有：

区间长度相同必定平局。
否则，两个区间线段不交时，线段长的获胜。
否则，两个区间有交时，线段短的获胜。

于是考虑枚举小 C 的左端点：

如果两端点中间有至少两个小 T 的选择点那么会造成包含局面。
所以小 C 右端点有一个最大值。
如果中间没有小 T 的选择点那么两区间一定不交，两人都尽量选区间大的。
如果中间恰有一个小 T 的选择点那么小 T 可交可不交，小 C 选择的区间大小有范围。

排序后进行二分即可，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
#define MX 1000005
#define CKE if(CHECK)
#define FRE if(FIL)
using namespace std;
const int CHECK=0,FIL=0;int read();
int Tt,F,ansL,ansR,n,C[MX],T[MX];
void update(int op,int cl,int cr){
    if(cl==cr) return;
    if(!F || op==2) F=op,ansL=cl,ansR=cr;}
int check(int cl,int cr,int tl,int tr){
    //小C选择 C[cl],C[cr]   小T选择 T[tl],T[tr] 
    //相等必平局 
    int Xc=C[cr]-C[cl],Xt=T[tr]-T[tl];
    if(Xc==Xt) return 1;
    //有交短的赢 无交长的赢 
    if(C[cr]<T[tl] || T[tr]<C[cl]) swap(Xc,Xt);
    if(Xc<Xt) return 2;
    return 0;
}
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("segment.in","r",stdin);
    FRE freopen("segment.out","w",stdout);
    Tt=read();while(Tt--){
        n=read();
        for(int i=1;i<=n;i++) C[i]=read();
        sort(C+1,C+1+n);C[n+1]=3e18,C[0]=-3e18;
        for(int i=1;i<=n;i++) T[i]=read();
        sort(T+1,T+1+n);T[n+1]=3e18,T[0]=-3e18;
        F=0,ansL=1,ansR=2;
        //0->T  1->Dr  2->C
        for(int cl=1;cl<n;cl++){//枚举小C区间的左端点 
            int ti=upper_bound(T+1,T+1+n,C[cl])-T;
          //找右侧离这个点最近的小T选择点 
          //如果没有，一定不交 
            if(ti>n){
                update(check(cl,n,1,n),cl,n);
                continue;
            }
          //如果有
            //找小C区间右端点的最小值 
            int cr=upper_bound(C+1,C+1+n,T[ti+1])-C-1;
            if(cr==cl) continue;//形如 C,T,T,C，小C必败
              //1: T,T,[C],..,C,T,T，此时一定不交
            int cmr=upper_bound(C+1,C+1+n,T[ti])-C-1;
            update(min(check(cl,cmr,1,ti-1)
                      ,check(cl,cmr,ti,n)),cl,cmr);
              //2: T,T,[C],T,C,..,C,T,T
                //如果小T选择和小C不交，小C选择长度有最小值 
            int Xcl=max(T[ti-1]-T[1],T[n]-T[ti+1]);
            cmr=max(cmr+1,(int)(lower_bound(C+1,C+1+n,C[cl]+Xcl)-C));
            if(cmr>cr) continue;
                //小T还可以选择和小C相交
            update(min(
                    min(check(cl,cmr,1,ti-1)
                       ,check(cl,cmr,ti+1,n)),
                    min(check(cl,cmr,ti-1,ti)
                       ,check(cl,cmr,ti,ti+1))),cl,cmr);
                //这里还有可能平局还得再逝逝 
            if(cmr+1<=cr) cmr++; 
            update(min(
                    min(check(cl,cmr,1,ti-1)
                       ,check(cl,cmr,ti+1,n)),
                    min(check(cl,cmr,ti-1,ti)
                       ,check(cl,cmr,ti,ti+1))),cl,cmr);
        }
        if(F==0) printf("T ");
        if(F==1) printf("Draw ");
        if(F==2) printf("C ");
        printf("%lld %lld\n",C[ansL],C[ansR]);
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=' ';int Cf=1;
    while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
    while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}