THUSC Day 2 (Contest Day)

今天参加了THUSC.
第一题是在BFS树上乱搞，可以做到O(NM).
第二题裸KD-tree，但我不会。对时间分治+线段树可以50分。
第三题没时间看了，写了个10分的按格DP。正解貌似是考虑某格水的高度，然后肯定连成一片。于是水池的覆盖关系组成一个树形结构，做树形DP。要高精，而且据说要FFT才能不被卡。
然后被拉去参加面试。考官问我“厚德载物”的内涵。不吐槽。
见到了kAc等众神犇。
晚上本来想夜游北京然后买个烤鸭带回去的。但似乎今天走的路太多了，身体条件不支持继续玩了。
下面是我考试时提交的代码。纯纪念意义。不保证正确。

code

type
      list=object
                  a:array[0..1000000] of longint;
                  n:longint;
                  procedure init();
                  procedure add(x:longint);
                  procedure sort(l,r:longint);
                  procedure merge();
                  procedure sort();
                  function find(x:longint):longint;
            end;
 
procedure list.init();
begin n:=0; end;
 
procedure list.add(x:longint);
begin inc(n); a[n]:=x; end;
 
procedure list.sort(l,r:longint);
var i,j,x,y:longint;
begin i:=l; j:=r;
      x:=a[l+random(r-l+1)];
      repeat
            while a[i]<x do inc(i);
            while x<a[j] do dec(j);
            if not(i>j) then
            begin y:=a[i]; a[i]:=a[j]; a[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
procedure list.merge();
var i,cur:longint;
begin cur:=1;
      for i:=2 to n do
            if a[i]<>a[cur] then
            begin inc(cur);
                  a[cur]:=a[i];
            end;
      n:=cur;
end;
 
procedure list.sort();
begin sort(1,n);
      merge();
end;
 
function list.find(x:longint):longint;
var left,right,mid:longint;
begin left:=1; right:=n;
      while true do
      begin mid:=(left+right)>>1;
            if a[mid]=x then exit(mid);
            if x>a[mid] then left:=mid+1 else right:=mid-1;
      end;
end;
 
type
      atype=record x,y,tp,where:longint; end;
var
p,d:array[0..200010] of atype;
 
procedure sort(l,r: longint);
var i,j: longint; x,y:atype;
begin i:=l; j:=r;
      x:=d[l+random(r-l+1)];
      repeat
            while (d[i].x<x.x)or((d[i].x=x.x)and(d[i].tp=1)and(x.tp=0)) do inc(i);
            while (x.x<d[j].x)or((d[j].x=x.x)and(x.tp=1)and(d[j].tp=0)) do dec(j);
            if not(i>j) then
            begin y:=d[i]; d[i]:=d[j]; d[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
function cmp(const a,b:atype):boolean;
begin if a.x<>b.x then exit(a.x<b.x);
      if a.y<>b.y then exit(a.y<b.y);
      exit((a.tp=0)and(b.tp=1));
end;
 
procedure sort2(l,r: longint);
var i,j: longint; x,y:atype;
begin i:=l; j:=r;
      x:=p[l+random(r-l+1)];
      repeat
            while cmp(p[i],x) do inc(i);
            while cmp(x,p[j]) do dec(j);
            if not(i>j) then
            begin y:=p[i]; p[i]:=p[j]; p[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort2(l,j);
      if i<r then sort2(i,r);
end;
 
type
      pack=array[1..3] of extended;
 
var
ans:array[0..200000] of pack;
a:array[0..524288] of record
                              left,right,mid:longint;
                              max:pack;
                        end;
ninit,Q,PW:longint;
w:array[0..200000] of longint;
 
function mg(const a,b:pack):pack;
var i,i1,i2:longint;
begin i1:=1; i2:=1;
      for i:=1 to 3 do
            if a[i1]>b[i2] then
            begin mg[i]:=a[i1];
                  inc(i1);
             end
            else begin
                  mg[i]:=b[i2];
                  inc(i2);
            end;
end;
 
function mgs(const a,b:pack):pack;
var i,i1,i2:longint;
begin i1:=1; i2:=1;
      for i:=1 to 3 do
            if a[i1]<b[i2] then
            begin mgs[i]:=a[i1];
                  inc(i1);
             end
            else begin
                  mgs[i]:=b[i2];
                  inc(i2);
            end;
end;
 
procedure build(i,bg,ed:longint);
begin with a[i] do
      begin left:=bg; right:=ed; mid:=(bg+ed)>>1;
            max[1]:=-1e100; max[2]:=-1e100; max[3]:=-1e100;
            if bg=ed then exit;
            build(i<<1,bg,mid); build(i<<1 or 1,mid+1,ed);
      end;
end;
 
procedure serere(i,where,dt:longint);
var temp:pack;
begin with a[i] do
      begin if left=right then
            begin temp[1]:=dt; temp[2]:=-1e100; temp[3]:=-1e100;
                  max:=mg(max,temp);
                  exit;
            end;
            if where<=mid then serere(i<<1,where,dt) else serere(i<<1 or 1,where,dt);
            max:=mg(a[i<<1].max,a[i<<1 or 1].max);
      end;
end;
 
function query(i,bg,ed:longint):pack;
var r1,r2:pack;
begin with a[i] do
      begin if (bg<=left)and(right<=ed) then exit(max);
            if ed<=mid then exit(query(i<<1,bg,ed));
            if mid<bg then exit(query(i<<1 or 1,bg,ed));
            r1:=query(i<<1,bg,ed); r2:=query(i<<1 or 1,bg,ed);
            exit(mg(r1,r2));
      end;
end;
 
var
yl:list;
 
procedure doit(all:longint);
var i,j:longint; tmp:pack;
begin sort(1,all);
      yl.init();
      for i:=1 to all do yl.add(d[i].y);
      yl.sort();
      build(1,1,yl.n);
      for i:=1 to all do
            if d[i].tp=0 then
                  serere(1,yl.find(d[i].y),d[i].x+d[i].y)
            else begin
                  tmp:=query(1,1,yl.find(d[i].y));
                  for j:=1 to 3 do tmp[j]:=d[i].x+d[i].y-tmp[j];
                  ans[d[i].where]:=mgs(ans[d[i].where],tmp);
            end;
end;
 
procedure solve(lt,rt:longint);
var i,mid,all:longint; f:boolean;
begin if rt<=ninit then exit;
      if lt=rt then exit;
      mid:=(lt+rt)>>1; solve(lt,mid); solve(mid+1,rt);
      all:=0;
      for i:=lt to mid do
            if p[i].tp=0 then
            begin inc(all);
                  d[all]:=p[i];
            end;
      if all=0 then exit;
      f:=false;
      for i:=mid+1 to rt do
            if p[i].tp=1 then
            begin inc(all); f:=true;
                  d[all]:=p[i]; d[all].where:=i;
            end;
      if not f then exit;
      doit(all);
end;
 
procedure brute_force();
var min:pack;
    i,x,y,j:longint;
    ch:char;
    z:extended;
begin for i:=1 to ninit do readln(p[i].x,p[i].y);
      for i:=1 to Q do
      begin repeat read(ch); until ch in ['A','Q'];
            readln(x,y);
            if ch='Q' then
            begin min[1]:=1e100; min[2]:=1e100; min[3]:=1e100;
                  for j:=1 to ninit do
                  begin z:=sqrt(int64(x-p[j].x)*(x-p[j].x)+int64(y-p[j].y)*(y-p[j].y));
                        if z<min[1] then
                        begin min[3]:=min[2]; min[2]:=min[1];
                              min[1]:=z;
                         end
                        else  if z<min[2] then
                              begin min[3]:=min[2];
                                    min[2]:=z;
                               end
                              else  if z<min[3] then
                                          min[3]:=z;
                  end;
                  for j:=1 to PW-1 do write(min[j]:0:4,' ');
                  writeln(min[PW]:0:4);
             end
            else begin
                  inc(ninit);
                  p[ninit].x:=x; p[ninit].y:=y;
            end;
      end;
end;
 
procedure lemon();
var MODE,i,j,x,y,cur,last:longint; ch:char; flag:boolean;
begin readln(ninit,Q,MODE,PW);
      if MODE=2 then begin brute_force(); exit; end;
      for i:=1 to ninit do
      begin readln(p[i].x,p[i].y);
            p[i].tp:=0;
      end;
      for i:=ninit+1 to ninit+Q do
      begin repeat read(ch); until ch in ['A','Q'];
            readln(p[i].x,p[i].y);
            if ch='Q' then p[i].tp:=1 else p[i].tp:=0;
      end;
      for i:=1 to ninit+Q do ans[i,1]:=1e100; ans[i,2]:=1e100; ans[i,3]:=1e100;
      for j:=1 to 4 do
      begin
            solve(1,ninit+Q);
            for i:=1 to ninit+Q do
            begin x:=p[i].x; y:=p[i].y;
                    p[i].x:=-y; p[i].y:=x;
            end;
      end;
      for i:=1 to ninit+Q do p[i].where:=i;
      sort2(1,ninit+Q);
      cur:=1;
      while cur<=ninit+Q do
      begin flag:=(p[cur].tp=0);
            last:=cur; inc(cur);
            while (cur<=ninit+Q)and(p[cur].x=p[last].x)and(p[cur].y=p[last].y) do
            begin if (flag)and(p[last].where<=p[cur].where) then
                  begin ans[p[cur].where,3]:=ans[p[cur].where,2];
                        ans[p[cur].where,2]:=ans[p[cur].where,1];
                        ans[p[cur].where,1]:=0;
                  end;
                  inc(cur);
            end;
      end;
      for i:=1 to ninit+Q do
            if p[i].tp=1 then
                  w[p[i].where]:=1;
 
      for cur:=1 to ninit+Q do
      begin i:=w[cur];
            if i>0 then
            begin for j:=1 to PW-1 do write(ans[cur,j]:0:4,' ');
                  writeln(ans[cur,PW]:0:4);
            end;
      end;
end;
 
begin
lemon();
end.

code

const INF=1000000000;
var
ep:longint;
b:array[0..500000] of record id,next:longint; end;
_tail:array[0..10010] of longint;
 
function Create(x:longint):longint;
begin inc(ep);
      with b[ep] do
      begin id:=x;
            next:=-1;
      end;
      exit(ep);
end;
 
procedure add(x,y:longint);
begin b[_tail[x]].next:=Create(y);
      _tail[x]:=ep;
end;
 
const MD=200000;
var
      gdis,gpre,ganc,ls:array[0..2010,0..2010] of longint;
      count,dis,pre,inque,anc,d,where:array[0..2010] of longint;
      q:array[0..MD+1] of longint;
      all,n,cl2:longint;
      final:array[0..10010] of int64;
 
procedure prework(root:longint);
var i,head,tail,now,x:longint;
begin for i:=1 to n do dis[i]:=INF; dis[root]:=0;
      fillchar(pre,sizeof(pre),0);
      fillchar(anc,sizeof(anc),255);
      head:=1; tail:=2; q[head]:=root;
      while head<tail do
      begin x:=q[head]; inc(head);
            now:=x;
            while b[now].next<>-1 do
            begin now:=b[now].next;
                  if dis[x]+1<dis[b[now].id] then
                  begin dis[b[now].id]:=dis[x]+1; pre[b[now].id]:=x;
                        if x=root then anc[b[now].id]:=b[now].id else anc[b[now].id]:=anc[x];
                        q[tail]:=b[now].id; inc(tail);
                  end;
            end;
      end;
      for i:=1 to n do gdis[root,i]:=dis[i];
      for i:=1 to n do gpre[root,i]:=pre[i];
      for i:=1 to n do if anc[i]=i then anc[i]:=-1;
      for i:=1 to n do ganc[root,i]:=anc[i];
end;
{
procedure dfs(cur,_rt:longint);
var now:longint;
begin now:=cur;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            if pre[b[now].id]=cur then
            begin anc[b[now].id]:=_rt;
                  inc(count[all]); ls[all,count[all]]:=b[now].id;
                  dfs(b[now].id,_rt);
            end;
      end;
end;
}
 
type
      atype=record
                  dt,where:longint;
            end;
var
      cd:array[0..2010] of atype;
 
procedure sort(l,r: longint);
var i,j: longint; x,y:atype;
begin i:=l; j:=r;
      x:=cd[l+random(r-l+1)];
      repeat
            while cd[i].dt<x.dt do inc(i);
            while x.dt<cd[j].dt do dec(j);
            if not(i>j) then
            begin y:=cd[i]; cd[i]:=cd[j]; cd[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
procedure calc(root,dk,cal:longint);
var i,x,y,now,head,tail,ki:longint;
begin for i:=1 to count[cal] do d[ls[cal,i]]:=INF;
      anc[dk]:=dk;
      for i:=1 to count[cal] do
      begin x:=ls[cal,i]; now:=ls[cal,i]; //cd[i].dt:=INF;
            while b[now].next<>-1 do
            begin now:=b[now].next;
                  if anc[b[now].id]=dk then continue;
                  if dis[b[now].id]+1<d[ls[cal,i]] then
                        d[ls[cal,i]]:=dis[b[now].id]+1;
            end;
      end;
      anc[dk]:=-1;
      inc(cl2); head:=1; tail:=1;
      for i:=1 to count[cal] do
            if d[ls[cal,i]]<>INF then
            begin inc(tail); q[tail]:=ls[cal,i];
                  inque[ls[cal,i]]:=cl2;
            end;
      //sort(1,count[cal]);
      ki:=1;
      while (head<>tail) do
      begin inc(head); if head=MD then head:=0;
            x:=q[head]; inque[x]:=-1;
            now:=x;
            while b[now].next<>-1 do
            begin now:=b[now].next;
                  if anc[b[now].id]<>dk then continue;
                  y:=b[now].id;
                  if d[x]+1<d[y] then
                  begin d[y]:=d[x]+1;
                        if inque[y]<>cl2 then
                        begin inque[y]:=cl2;
                              inc(tail); if tail=MD then tail:=0;
                              q[tail]:=y;
                        end;
                  end;
            end;
      end;
      for i:=1 to count[cal] do
            if dis[ls[cal,i]]=2 then
                  final[dk]:=final[dk]+d[ls[cal,i]]-gdis[root,ls[cal,i]];
end;
 
procedure solve(root:longint);
var i,now,cz:longint;
begin for i:=1 to n do dis[i]:=gdis[root,i];
      for i:=1 to n do pre[i]:=gpre[root,i];
      for i:=1 to n do anc[i]:=ganc[root,i];
              {
            fillchar(anc,sizeof(anc),255);
            now:=root; all:=0;
            while b[now].next<>-1 do
            begin now:=b[now].next;
                  inc(all); count[all]:=0;
                  dfs(b[now].id,b[now].id);
            end;
              }
      fillchar(count,sizeof(count),0);
      all:=0;
      for i:=1 to n do
            if (anc[i]=-1)and(i<>root) then
            begin inc(all);
                  where[i]:=all;
            end;
      for i:=1 to n do
            if anc[i]<>-1 then
            begin inc(count[where[anc[i]]]);
                  ls[where[anc[i]],count[where[anc[i]]]]:=i;
            end;
      now:=root; cz:=0;
      while b[now].next<>-1 do
      begin now:=b[now].next;
            calc(root,b[now].id,where[b[now].id]);
      end;
end;
 
procedure lemon();
var m,i,x,y:longint;
begin readln(n,m); ep:=0; cl2:=0;
      for i:=1 to n do _tail[i]:=Create(i);
      for i:=1 to m do begin readln(x,y); add(x,y); add(y,x); end;
      fillchar(final,sizeof(final),0);
      for i:=1 to n do prework(i);
      for i:=1 to n do solve(i);
      for i:=1 to n do writeln(final[i] div 2);
end;
 
begin
lemon();
end.

code

var
ans:int64;
i,j,x,cur,next,ms,state,h,k,m,n:longint;
w:array[0..20,0..20] of longint;
dp:array[0..1,0..10000] of int64;
ex,s:array[0..10000] of longint;
 
function check(x:longint; x1:boolean; y:longint; y1:boolean; z:longint; z1:boolean):boolean;
begin if z1 then
      begin if not x1 then if z<x then exit(false);
            if not y1 then if z<y then exit(false);
            exit(true);
      end;
      if not x1 then if z<>x then exit(false);
      if x1 then if z>x then exit(false);
      if not y1 then if z<>y then exit(false);
      if y1 then if z>y then exit(false);
      exit(true);
end;
 
begin
readln(n,m);
for i:=0 to n+1 do
      for j:=0 to n+1 do
            w[i,j]:=m;
 
for i:=1 to n do
      for j:=1 to n do
            read(w[i,j]);
 
fillchar(dp,sizeof(dp),0);
cur:=1; next:=0;
x:=0; for i:=1 to n do x:=x*(m+1)+m;
ex[0]:=1;
for i:=1 to n do ex[i]:=ex[i-1]*(m+1);
ms:=x;
 
dp[cur,x]:=1;
for i:=1 to n+1 do
begin fillchar(dp[next],sizeof(dp[next]),0);
      for state:=0 to ms do
            if dp[cur,state]>0 then
            begin x:=state; for k:=n downto 1 do begin s[k]:=x mod (m+1); x:=x div (m+1); end;
                  for h:=w[i,1] to m do
                        if ((s[1]=w[i-1,1])and(s[1]>=h))or((h=w[i,1])and(h>=s[1]))or(s[1]=h) then
                              inc(dp[next,state-ex[n-1]*s[1]+ex[n-1]*h],dp[cur,state]);
            end;
      cur:=1-cur; next:=1-next;
 
      for j:=2 to n do
      begin fillchar(dp[next],sizeof(dp[next]),0);
            for state:=0 to ms do
                  if dp[cur,state]>0 then
                  begin x:=state; for k:=n downto 1 do begin s[k]:=x mod (m+1); x:=x div (m+1); end;
                        for h:=w[i,j] to m do
                              if check(s[j-1],s[j-1]=w[i,j-1],s[j],s[j]=w[i-1,j],h,h=w[i,j]) then
                                    inc(dp[next,state-ex[n-j]*s[j]+ex[n-j]*h],dp[cur,state]);
                  end;
            cur:=1-cur; next:=1-next;
      end;
end;
 
ans:=0;
for state:=0 to ms do inc(ans,dp[cur,state]);
writeln(ans);
end.