THUSC Day 3 训练日记

THUSC结束了。终于回到了南京。祝贺HYM神犇直签THU～
本菜因为面试实在太悲剧只搞到了NOI前60高考分数线降60的协议。
今天在火车上花了2.5h捉了NOI2011 Day1. 我对历届NOI题目几乎没有印象，不过这个反而成有利条件了，这样能以全真模拟的方式来捉往年试题真心好玩，或许训练效果也能好一些。
第一题兔农不会正解，直接乱搞暴力75分

code

procedure lemon();
var n,k,p,k1,k2,k3,p1,p2,p3,i:longint;
begin readln(n,k,p);
      if n<=2 then begin writeln(1); exit; end;
      if n=3 then begin writeln(2 mod p); exit; end;
      k1:=1; k2:=2 mod k;
      p1:=1; p2:=2 mod p;
      for i:=4 to n do
      begin k3:=(k1+k2) mod k;
            p3:=(p1+p2) mod p;
            if k3=1 then begin dec(k3); dec(p3); if p3<0 then inc(p3,p); end;
            k1:=k2; p1:=p2;
            k2:=k3; p2:=p3;
      end;
      writeln(p2);
end;
 
begin
assign(input,'rabbit.in');
reset(input);
lemon();
end.

第二题智能车。明显是找关键点然后最短路。我YY了一下，想象一下就会发现，最优解可以用一根软绳子连接起点终点，矩形就是障碍物，然后用力拉绳子，就能 得到最短路。YY一下这个物理过程就可以发现绳子拐弯处必然是矩形顶点。于是如果暴力建图，O(N)判边是否可行，是O(N^3)的。但YY一下可以发 现，绳子必然不会出现“拐回去”的情况，也就是关键点x轴是严格递增的。于是我们只要考虑对每个顶点快速连出可行边。我们发现，实际可行边始终是一个角度 区间，而且这个角度区间随着x轴增加逐渐变小。于是我们枚举顶点后从小到大枚举x轴关键点（就是矩形的顶点），然后维护可行角度区间，这样就能O(1)判 出一条边是否可行。于是就O(N^2)了。N=8000,看上去压力很大，但因为一旦角度区间不存在了就可以直接跳出循环了，实际速度还是可以接受的。代 码有点小麻烦。我因为边界问题挂了几次。

code

const eps=1e-9;
var
xl,xr,yd,yu,dis,dx,dy:array[0..8010] of extended;
n:longint;
 
function getcut(sx,sy,ex,ey,x:extended):extended;
begin exit((ey-sy)/(ex-sx)*(x-sx)+sy); end;
 
function checkline(sx,sy,ex,ey:extended):boolean;
var i:longint; y:extended;
begin if abs(sx-ex)<eps then exit(true);
      for i:=1 to n do
            if (xl[i]+eps<=sx)and(ex+eps<=xr[i]) then
                  exit(true)
            else  if (sx<=xl[i]+eps)and(xr[i]<=ex+eps) then
                  begin y:=getcut(sx,sy,ex,ey,xl[i]);
                        if not((yd[i]<=y+eps)and(y<=yu[i]+eps)) then exit(false);
                        y:=getcut(sx,sy,ex,ey,xr[i]);
                        if not((yd[i]<=y+eps)and(y<=yu[i]+eps)) then exit(false);
                   end
                  else  if (xl[i]<=sx+eps)and(sx+eps<=xr[i]) then
                        begin y:=getcut(sx,sy,ex,ey,xr[i]);
                              if not((yd[i]<=y+eps)and(y<=yu[i]+eps)) then exit(false);
                         end
                        else  if (xl[i]+eps<=ex)and(ex<=xr[i]+eps) then
                              begin y:=getcut(sx,sy,ex,ey,xl[i]);
                                    if not((yd[i]<=y+eps)and(y<=yu[i]+eps)) then exit(false);
                              end;
      exit(true);
end;
 
procedure upd(var a:extended; const b:extended);
begin if b<a then a:=b; end;
 
function av(l,r,x:extended):boolean;
begin exit((l<=x+eps)and(x<=r+eps)); end;
 
procedure lemon();
var i,j:longint;
    sx,sy,ex,ey,v,x1,x2,l,r,_d,_x,_y,ans:extended;
begin readln(n);
      for i:=1 to n do readln(xl[i],yd[i],xr[i],yu[i]);
      readln(sx,sy);
      readln(ex,ey);
      readln(v);
      if checkline(sx,sy,ex,ey) then begin writeln(sqrt(sqr(sx-ex)+sqr(sy-ey))/v:0:10); exit; end;
      for i:=5 to 4*n+4 do dis[i]:=1e100;
      for i:=1 to n do
      begin if checkline(sx,sy,xl[i],yd[i]) then dis[i*4+1]:=sqrt(sqr(sx-xl[i])+sqr(sy-yd[i]));
            if checkline(sx,sy,xl[i],yu[i]) then dis[i*4+2]:=sqrt(sqr(sx-xl[i])+sqr(sy-yu[i]));
            if checkline(sx,sy,xr[i],yd[i]) then dis[i*4+3]:=sqrt(sqr(sx-xr[i])+sqr(sy-yd[i]));
            if checkline(sx,sy,xr[i],yu[i]) then dis[i*4+4]:=sqrt(sqr(sx-xr[i])+sqr(sy-yu[i]));
      end;
 
      for i:=1 to n do
      begin _d:=dis[i*4+1]; _x:=xl[i]; _y:=yd[i];
            l:=0; r:=(yu[i]-_y)/(xr[i]-_x);
            upd(dis[i*4+3],_d+xr[i]-_x);
            upd(dis[i*4+4],_d+sqrt(sqr(xr[i]-_x)+sqr(yu[i]-_y)));
            for j:=i+1 to n do
            begin x1:=(yd[j]-_y)/(xl[j]-_x);
                  if x1>l then l:=x1;
                  x2:=(yu[j]-_y)/(xl[j]-_x);
                  if x2<r then r:=x2;
                  if av(l,r,x1) then upd(dis[j*4+1],_d+sqrt(sqr(xl[j]-_x)+sqr(yd[j]-_y)));
                  if av(l,r,x2) then upd(dis[j*4+2],_d+sqrt(sqr(xl[j]-_x)+sqr(yu[j]-_y)));
                  x1:=(yd[j]-_y)/(xr[j]-_x);
                  if x1>l then l:=x1;
                  x2:=(yu[j]-_y)/(xr[j]-_x);
                  if x2<r then r:=x2;
                  if av(l,r,x1) then upd(dis[j*4+3],_d+sqrt(sqr(xr[j]-_x)+sqr(yd[j]-_y)));
                  if av(l,r,x2) then upd(dis[j*4+4],_d+sqrt(sqr(xr[j]-_x)+sqr(yu[j]-_y)));
                  if l>r+eps then break;
            end;
 
            //for j:=5 to 4*n+4 do writeln(dis[j]:0:6);
            //writeln;            
 
            _d:=dis[i*4+2]; _x:=xl[i]; _y:=yu[i];
            l:=(yd[i]-_y)/(xr[i]-_x); r:=0;
            upd(dis[i*4+4],_d+xr[i]-_x);
            upd(dis[i*4+3],_d+sqrt(sqr(xr[i]-_x)+sqr(yd[i]-_y)));
            for j:=i+1 to n do
            begin x1:=(yd[j]-_y)/(xl[j]-_x);
                  if x1>l then l:=x1;
                  x2:=(yu[j]-_y)/(xl[j]-_x);
                  if x2<r then r:=x2;
                  if av(l,r,x1) then upd(dis[j*4+1],_d+sqrt(sqr(xl[j]-_x)+sqr(yd[j]-_y)));
                  if av(l,r,x2) then upd(dis[j*4+2],_d+sqrt(sqr(xl[j]-_x)+sqr(yu[j]-_y)));
                  x1:=(yd[j]-_y)/(xr[j]-_x);
                  if x1>l then l:=x1;
                  x2:=(yu[j]-_y)/(xr[j]-_x);
                  if x2<r then r:=x2;
                  if av(l,r,x1) then upd(dis[j*4+3],_d+sqrt(sqr(xr[j]-_x)+sqr(yd[j]-_y)));
                  if av(l,r,x2) then upd(dis[j*4+4],_d+sqrt(sqr(xr[j]-_x)+sqr(yu[j]-_y)));
                  if l>r+eps then break;
            end;
 
            //for j:=5 to 4*n+4 do writeln(dis[j]:0:6);
            //writeln;            
 
            _d:=dis[i*4+3]; _x:=xr[i]; _y:=yd[i];
            if (i<>n)and(av(yd[i+1],yu[i+1],_y)) then
            begin l:=(yd[i+1]-_y)/(xr[i+1]-_x); r:=(yu[i+1]-_y)/(xr[i+1]-_x);
                  upd(dis[i*4+7],_d+sqrt(sqr(xr[i+1]-_x)+sqr(yd[i+1]-_y)));
                  upd(dis[i*4+8],_d+sqrt(sqr(xr[i+1]-_x)+sqr(yu[i+1]-_y)));
                  for j:=i+2 to n do
                  begin x1:=(yd[j]-_y)/(xl[j]-_x);
                        if x1>l then l:=x1;
                        x2:=(yu[j]-_y)/(xl[j]-_x);
                        if x2<r then r:=x2;
                        if av(l,r,x1) then upd(dis[j*4+1],_d+sqrt(sqr(xl[j]-_x)+sqr(yd[j]-_y)));
                        if av(l,r,x2) then upd(dis[j*4+2],_d+sqrt(sqr(xl[j]-_x)+sqr(yu[j]-_y)));
                        x1:=(yd[j]-_y)/(xr[j]-_x);
                        if x1>l then l:=x1;
                        x2:=(yu[j]-_y)/(xr[j]-_x);
                        if x2<r then r:=x2;
                        if av(l,r,x1) then upd(dis[j*4+3],_d+sqrt(sqr(xr[j]-_x)+sqr(yd[j]-_y)));
                        if av(l,r,x2) then upd(dis[j*4+4],_d+sqrt(sqr(xr[j]-_x)+sqr(yu[j]-_y)));
                        if l>r+eps then break;
                  end;
            end;
 
            //for j:=5 to 4*n+4 do writeln(dis[j]:0:6);
            //writeln;            
 
            _d:=dis[i*4+4]; _x:=xr[i]; _y:=yu[i];
            if (i<>n)and(av(yd[i+1],yu[i+1],_y)) then
            begin l:=(yd[i+1]-_y)/(xr[i+1]-_x); r:=(yu[i+1]-_y)/(xr[i+1]-_x);
                  upd(dis[i*4+7],_d+sqrt(sqr(xr[i+1]-_x)+sqr(yd[i+1]-_y)));
                  upd(dis[i*4+8],_d+sqrt(sqr(xr[i+1]-_x)+sqr(yu[i+1]-_y)));
                  for j:=i+2 to n do
                  begin x1:=(yd[j]-_y)/(xl[j]-_x);
                        if x1>l then l:=x1;
                        x2:=(yu[j]-_y)/(xl[j]-_x);
                        if x2<r then r:=x2;
                        if av(l,r,x1) then upd(dis[j*4+1],_d+sqrt(sqr(xl[j]-_x)+sqr(yd[j]-_y)));
                        if av(l,r,x2) then upd(dis[j*4+2],_d+sqrt(sqr(xl[j]-_x)+sqr(yu[j]-_y)));
                        x1:=(yd[j]-_y)/(xr[j]-_x);
                        if x1>l then l:=x1;
                        x2:=(yu[j]-_y)/(xr[j]-_x);
                        if x2<r then r:=x2;
                        if av(l,r,x1) then upd(dis[j*4+3],_d+sqrt(sqr(xr[j]-_x)+sqr(yd[j]-_y)));
                        if av(l,r,x2) then upd(dis[j*4+4],_d+sqrt(sqr(xr[j]-_x)+sqr(yu[j]-_y)));
                        if l>r+eps then break;
                  end;
            end;
            //for j:=5 to 4*n+4 do writeln(dis[j]:0:6);
            //writeln;            
      end;
      {
      for i:=1 to n do
      begin dx[i*4+1]:=xl[i]; dy[i*4+1]:=yd[i];
            dx[i*4+2]:=xl[i]; dy[i*4+2]:=yu[i];
            dx[i*4+3]:=xr[i]; dy[i*4+3]:=yd[i];
            dx[i*4+4]:=xr[i]; dy[i*4+4]:=yu[i];
      end;
      for i:=5 to n*4+4 do
            for j:=i+1 to n*4+4 do
                  if checkline(dx[i],dy[i],dx[j],dy[j]) then
                        upd(dis[j],dis[i]+sqrt(sqr(dx[i]-dx[j])+sqr(dy[i]-dy[j])));
      }                  
      ans:=1e100;
      for i:=1 to n do
      begin if checkline(xl[i],yd[i],ex,ey) then upd(ans,dis[i*4+1]+sqrt(sqr(ex-xl[i])+sqr(ey-yd[i])));
            if checkline(xl[i],yu[i],ex,ey) then upd(ans,dis[i*4+2]+sqrt(sqr(ex-xl[i])+sqr(ey-yu[i])));
            if checkline(xr[i],yd[i],ex,ey) then upd(ans,dis[i*4+3]+sqrt(sqr(ex-xr[i])+sqr(ey-yd[i])));
            if checkline(xr[i],yu[i],ex,ey) then upd(ans,dis[i*4+4]+sqrt(sqr(ex-xr[i])+sqr(ey-yu[i])));
      end;
      writeln(ans/v:0:10);
end;
 
begin
assign(input,'car.in');
reset(input);
lemon();
end.

第三题阿狸的打字机。我觉得这题是很有趣的题目。首先观察到，打字的操作实际就是建立了一棵trie树。然后我们要回答某个单词在另一个单词中出现了多少 次。首先肯定要把fail指针树建立出来。然后暴力做法就是，对每个单词，枚举前缀，然后通过fail指针判定这个前缀的后缀是否是想要找的单词。一个改 进的想法是，我们可以对于某个母串离线回答所有有关这个母串出现了多少次字串的询问。这实际就是，把母串的所有前缀在fail树上标记出来，然后查询就是 查询某个子树有多少被标记的结点。这显然可以树状数组维护。然后我们可以很自然的想到，在DFS trie树的过程中维护fail树上被标记的结点的树状数组。于是问题得到了解决。这题解题思路还是很有趣的。

code

type
      graph=object
                  b:array[0..300000] of record id,where,next:longint; end;
                  tail:array[0..100010] of longint;
                  ep:longint;
                  function Create(x,y:longint):longint;
                  procedure add(x,y,z:longint);
                  procedure init(n:longint);
            end;
 
function graph.Create(x,y:longint):longint;
begin inc(ep);
      with b[ep] do
      begin id:=x; where:=y;
            next:=-1;
      end;
      exit(ep);
end;
 
procedure graph.add(x,y,z:longint);
begin b[tail[x]].next:=Create(y,z);
      tail[x]:=ep;
end;
 
procedure graph.init(n:longint);
var i:longint;
begin ep:=0;
      for i:=1 to n do tail[i]:=Create(i,0);
end;
 
type
      node=record
                  ch:array[1..26] of record
                                          solid:boolean;
                                          next:longint;
                                    end;
                  fail,parent:longint;
            end;
var
t:array[0..200000] of node;
ek,root:longint;
 
function newnode(p:longint):longint;
var i:longint;
begin inc(ek);
      with t[ek] do
      begin for i:=1 to 26 do begin ch[i].solid:=false; ch[i].next:=-1; end;
            parent:=p; fail:=-1;
      end;
      exit(ek);
end;
 
var
ft,gq:graph;
q:array[0..200000] of longint;
 
procedure buildfailtree();
var head,tail,i,x:longint;
begin ft.init(ek);
      head:=1; tail:=1;
      for i:=1 to 26 do
            if t[root].ch[i].solid then 
            begin q[tail]:=t[root].ch[i].next; inc(tail);
                  t[t[root].ch[i].next].fail:=root;
             end 
            else  t[root].ch[i].next:=root;
      while head<tail do
      begin x:=q[head]; inc(head);
            for i:=1 to 26 do
                  if t[x].ch[i].solid then 
                  begin q[tail]:=t[x].ch[i].next; inc(tail);
                        t[t[x].ch[i].next].fail:=t[t[x].fail].ch[i].next
                   end
                  else  t[x].ch[i].next:=t[t[x].fail].ch[i].next;
      end;
      for i:=2 to ek do ft.add(t[i].fail,i,0);
end;
 
var
ec:longint;
l,r:array[0..200000] of longint;
 
procedure dfs(cur:longint);
var now:longint;
begin inc(ec); l[cur]:=ec;
      now:=cur;
      with ft do
            while b[now].next<>-1 do
            begin now:=b[now].next;
                  dfs(b[now].id);
            end;
      r[cur]:=ec;
end;
 
var
ta:array[0..200000] of longint;
 
procedure serere(x,y:longint);
begin while x<=ek do
      begin inc(ta[x],y);
            inc(x,x and -x);
      end;
end;
 
function query(x:longint):longint;
begin query:=0;
      while x>0 do
      begin inc(query,ta[x]);
            dec(x,x and -x);
      end;
end;
 
var
ch:array[0..200000] of char;
final,where:array[0..200000] of longint;
 
procedure lemon();
var n,Q,i,all,x,y,cur,now,ca,pa:longint;
begin n:=0;
      while not seekeoln(input) do begin inc(n); read(ch[n]); end;
      all:=0;
      for i:=1 to n do if ch[i]='P' then inc(all);
      gq.init(all);
      readln(Q);
      for i:=1 to Q do
      begin readln(x,y);
            gq.add(y,x,i);
      end;
      ek:=0; root:=newnode(-1); cur:=root; pa:=0;
      for i:=1 to n do
      begin if ch[i]='B' then begin cur:=t[cur].parent; continue; end;
            if ch[i]='P' then begin inc(pa); where[pa]:=cur; continue; end;
            if t[cur].ch[ord(ch[i])-96].next=-1 then 
            begin t[cur].ch[ord(ch[i])-96].next:=newnode(cur);
                  t[cur].ch[ord(ch[i])-96].solid:=true;
            end;
            cur:=t[cur].ch[ord(ch[i])-96].next;
      end;
      buildfailtree();
      ec:=0; dfs(1); ca:=0;
      fillchar(ta,sizeof(ta),0);
      cur:=root;
      for i:=1 to n do
      begin if ch[i]='B' then begin serere(l[cur],-1); cur:=t[cur].parent; continue; end;
            if ch[i]='P' then 
            begin inc(ca);
                  now:=ca;
                  with gq do
                        while b[now].next<>-1 do
                        begin now:=b[now].next;
                              final[b[now].where]:=query(r[where[b[now].id]])-query(l[where[b[now].id]]-1);
                              //writeln(ca,' ',b[now].id,' ',b[now].where);
                        end;
                  continue;
            end;
            cur:=t[cur].ch[ord(ch[i])-96].next;
            serere(l[cur],1);
      end;
      for i:=1 to Q do writeln(final[i]);
end;
 
begin
assign(input,'type.in');
reset(input);
lemon();
end.