自动搬运

查看原文

来自洛谷，原作者为

	TruchyR ¿啥你问了我我问了你啥?

搬运于2025-08-24 23:10:56，当前版本为作者最后更新于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$。

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

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

$\begin{aligned} 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;
}