跟神犇们搞了一晚上第一题，我YY的一个错误结论的正确的部分被zzm神犇证明了，然后第一题可做。第二题只会30分做法。第三题知道做法，但是估计实现的时候不是很好写，等标程看看。没测完，错了再改。

A Wormhole

      通过反证法可得一定在1建一个虫洞，然后有两种做法。二分答案+一个zzm神犇构造的验证可搞（讨论怎么从1过来点被分成三段满足各一个性质，扫描一遍，如果有这三段外头的点说明mid不够大）。然后就是我的，发现费用关于建造点是凸的，可以三分暴力搞。我果然只会模版题啊，太水了。对拍发现跟zzm神犇一样就交了。

program Wormhole;

uses math;

const FileName='Wormhole';inf=maxlongint;

var ans,t,n:longint;

x:array[0..200000] of longint;

function  f(p:longint):longint;

var i,temp:longint;

begin temp:=-inf;

for i:=2 to n do

temp:=max(temp,min(x[i]-x[1],abs(x[p]-x[i])));

ans:=min(ans,temp);exit(temp);

end;

procedure slove;

var i,l,r,a,b,len,fa,fb:longint;

begin

readln(n);ans:=inf;

for i:=1 to n do read(X[i]);

l:=2;r:=n;

while l

len:=(r-l+1) div 3;

a:=l+len;b:=r-len;

fa:=f(a);fb:=f(b);

if fa

then r:=b

else l:=a;

end;

for i:=l to r do fa:=f(i);

writeln(ans);

end;

begin

readln(T);

while T>0 do begin

slove;dec(T);end;

end.

 

B Dual Matrices

      只会预处理前缀和，然后枚举两个矩形左上角，O((NM)^2)估计是30分。没写。不知道二维RMQ是不是可搞。

C Caculator

      XY教过一种WS的做法，通过先确定每个运算符的优先级然后再计算。没写。