APIO2015题解

分组赛讲课讲了APIO2015的题，于是回去就做完了

稍微写一点题解吧

bzoj4069 逐位处理的简单题，然后就是bool型dp

然后a=1 的时候可以把一位状态干掉

当一维状态单调且是bool型dp时，我们可以用dp表示这一维状态；类似的思想也在bzoj1937出现过

var s:array[0..2010] of int64;
    n,a,b,i,j,k,p:longint;
    g,c:array[0..2010] of longint;
    f:array[0..110,0..110] of boolean;
    now:int64;
    can:boolean;

function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end;

begin
  readln(n,a,b);
  for i:=1 to n do
  begin
    read(c[i]);
    s[i]:=s[i-1]+c[i];
  end;
  if a=1 then
  begin
    for p:=40 downto 0 do
    begin
      now:=now or int64(1) shl int64(p);
      g[0]:=0;
      for i:=1 to n do
        g[i]:=n+1;
      for i:=1 to n do
        for j:=1 to i do
        begin
          if (s[i]-s[j-1]) and now>0 then continue;  //当前模板是0就不能为1，是1就随意，这里转化一下方便快速匹配
          g[i]:=min(g[i],g[j-1]+1);
        end;
      if g[n]>b then
        now:=now xor int64(1) shl int64(p);
    end;
  end
  else begin
    for p:=40 downto 0 do
    begin
      now:=now or int64(1) shl int64(p);
      fillchar(f,sizeof(f),false);
      f[0,0]:=true;
      for i:=1 to n do
        for j:=1 to n do
          for k:=1 to i do
            if f[k-1,j-1] then
            begin
              f[i,j]:=((s[i]-s[k-1]) and now=0);
              if f[i,j] then break;
            end;

      can:=false;
      for i:=a to b do
        if f[n,i] then
        begin
          can:=true;
          break;
        end;
      if not can then now:=now xor int64(1) shl int64(p);
    end;
  end;
  for p:=40 downto 0 do
    now:=now xor int64(1) shl int64(p);
  writeln(now);
end.

bzoj4070 听说现场直接爆搜就过了，这……

首先每只狗只会往一个方向跳

当pi大的时候，每只狗跳的次数少，直接建图即可

当pi小的时候，每个点向外走的种类很少，建立辅助点即可

经典的分类思想，设定一个K

当pi>k,直接建图，设n个点为(i,0)

然后每个点i再建立k个辅助点(i,1)~(i,k) 代表对应跳跃能力

然后看每条狗，如果pi<=k则连向对应的辅助点

然后每个辅助点连向(i,0)，表示通过(i,0)可以停下来换狗

然后跑dijkstra即可

注意k不能太大，因为内存卡得比较紧

然后我又tle了，把pi离散化后就过了……

const inf=10000007;
type node=record
       po,next,num:longint;
     end;
     point=record
       loc,num:longint;
     end;

var h:array[0..3100010] of point;
    e:array[0..15000010] of node;
    p,d,wh:array[0..3100010] of longint;
    v,c,b,f:array[0..30010] of longint;
    w:array[0..30010,0..110] of longint;
    r,st,en,size,i,j,tot,t,x,y,n,m,len:longint;

procedure add(x,y,z:longint);
  begin
    inc(len);
    e[len].po:=y;
    e[len].next:=p[x];
    e[len].num:=z;
    p[x]:=len;
  end;

procedure swap(var a,b:point);
  var c:point;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure sift(i:longint);
  var j,x,y:longint;
  begin
    j:=i shl 1;
    while j<=tot do
    begin
      if (j<tot) and (h[j].num>h[j+1].num) then inc(j);
      if h[i].num>h[j].num then
      begin
        x:=h[i].loc;
        y:=h[j].loc;
        wh[x]:=j;
        wh[y]:=i;
        swap(h[i],h[j]);
        i:=j;
        j:=i shl 1;
      end
      else break;
    end;
  end;

procedure up(i:longint);
  var j,x,y:longint;
  begin
    j:=i shr 1;
    while j>0 do
    begin
      if h[i].num<h[j].num then
      begin
        x:=h[i].loc;
        y:=h[j].loc;
        wh[x]:=j;
        wh[y]:=i;
        swap(h[i],h[j]);
        i:=j;
        j:=i shr 1;
      end
      else break;
    end;
  end;

begin
  readln(n,m);
  for i:=1 to m do
  begin
    readln(b[i],f[i]);
    inc(b[i]);
    if i=1 then st:=b[i];
    if i=2 then en:=b[i];
    v[f[i]]:=1;
  end;
  for i:=1 to n do
    if v[i]=1 then
    begin
      inc(r);
      c[r]:=i;
      v[i]:=r;
    end;

  size:=trunc(sqrt(r));
  if size>100 then size:=100;
  t:=n;
  for i:=1 to size do
  begin
    for j:=1 to n do
    begin
      inc(t);
      w[j,i]:=t;
      add(t,j,0);
    end;
    for j:=1 to n-c[i] do
    begin
      add(w[j,i],w[j+c[i],i],1);
      add(w[j+c[i],i],w[j,i],1);
    end;
  end;

  for i:=1 to m do
    if f[i]<=c[size] then
      add(b[i],w[b[i],v[f[i]]],0)
    else begin
      j:=1;
      while true do
      begin
        if b[i]+f[i]*j>n then break;
        add(b[i],b[i]+f[i]*j,j);
        inc(j);
      end;
      j:=1;
      while true do
      begin
        if b[i]-f[i]*j<=0 then break;
        add(b[i],b[i]-f[i]*j,j);
        inc(j);
      end;
    end;

  tot:=1;
  h[1].loc:=st;
  h[1].num:=0;
  for i:=1 to t do
    if i<>st then
    begin
      inc(tot);
      h[tot].loc:=i;
      h[tot].num:=inf;
      d[i]:=inf;
      wh[i]:=tot;
    end;

  while tot>0 do
  begin
    x:=h[1].loc;
    if x=en then break;
    if h[1].num=inf then break;
    wh[h[tot].loc]:=1;
    swap(h[1],h[tot]);
    dec(tot);
    sift(1);
    i:=p[x];
    while i<>0 do
    begin
      y:=e[i].po;
      if d[y]>d[x]+e[i].num then
      begin
        d[y]:=d[x]+e[i].num;
        h[wh[y]].num:=d[y];
        up(wh[y]);
      end;
      i:=e[i].next;
    end;
  end;
  if d[en]=inf then writeln(-1)
  else writeln(d[en]);
end.

bzoj4071 一开始看题的时候想到的是三分套三分……好像听说也能过……

我们只需要考虑起点终点在两侧的

当k=1 大家都会是中位数贪心

当k=2 分类讨论，设第一座桥在S1，第二座桥在S2

不难得到，xi+yi<S1+S2时走S1，否则走S2

这样只要对x+y排序，枚举分割点，分别对两部分求中位数即可然后在求和即可

这我们可以用权值线段树维护

顺便在UOJ上交被叉掉了，没事卡什么快排真是了……

type node=record
       x,y,s:longint;
     end;
     point=record
       s:longint;
       sum:int64;
     end;

var c,a:array[0..200010] of longint;
    b:array[0..100010] of node;
    tree:array[0..200010*4,0..1] of point;
    x,y,n,t,mid,m,i,k:longint;
    ans,s:int64;
    ch1,ch2:char;

procedure min(var a:int64; b:int64);
  begin
    if a>b then a:=b;
  end;

procedure swap(var a,b:longint);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure sort(l,r:longint);
  var i,j,x:longint;
  begin
    i:=l;
    j:=r;
    x:=a[(l+r) shr 1];
    repeat
      while a[i]<x do inc(i);
      while x<a[j] do dec(j);
      if not(i>j) then
      begin
        swap(a[i],a[j]);
        inc(i);
        dec(j);
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

procedure qsort(l,r:longint);
  var i,j,x:longint;
      y:node;
  begin
    i:=l;
    j:=r;
    x:=b[(l+r) shr 1].s;
    repeat
      while b[i].s<x do inc(i);
      while x<b[j].s do dec(j);
      if not(i>j) then
      begin
        y:=b[i]; b[i]:=b[j]; b[j]:=y;
        inc(i);
        dec(j);
      end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
  end;

function find(l,r,x:longint):longint;
  var m:longint;
  begin
    while l<=r do
    begin
      m:=(l+r) shr 1;
      if c[m]=x then exit(m);
      if c[m]>x then r:=m-1 else l:=m+1;
    end;
  end;

procedure add(i,l,r,w,x,y:longint);
  var m:longint;
  begin
    inc(tree[i,w].s,y);
    inc(tree[i,w].sum,y*c[x]);
    if l<>r then
    begin
      m:=(l+r) shr 1;
      if x<=m then add(i*2,l,m,w,x,y)
      else add(i*2+1,m+1,r,w,x,y);
    end;
  end;

function get(i,l,r,w,k:longint):int64;
  var m:longint;
  begin
    if l=r then exit(int64(k)*int64(c[l]))
    else begin
      m:=(l+r) shr 1;
      if tree[i*2,w].s>=k then exit(get(i*2,l,m,w,k))
      else exit(tree[i*2,w].sum+get(i*2+1,m+1,r,w,k-tree[i*2,w].s));
    end;
  end;

function sum(w,n:longint):int64;
  begin
    exit(tree[1,w].sum-2*get(1,1,m,w,n shr 1));
  end;

begin
  readln(k,n);
  for i:=1 to n do
  begin
    read(ch1);
    read(x);
    read(ch2); read(ch2);
    readln(y);
    if ch1=ch2 then s:=s+abs(x-y)
    else begin
      inc(t);
      b[t].x:=x;
      b[t].y:=y;
      b[t].s:=x+y;
    end;
  end;
  n:=t;
  t:=0;
  for i:=1 to n do
  begin
    inc(t);
    a[t]:=b[i].x;
    inc(t);
    a[t]:=b[i].y;
  end;
  sort(1,t);
  if k=1 then
  begin
    x:=a[(t+1) shr 1];
    ans:=0;
    for i:=1 to t do
      ans:=ans+abs(x-a[i]);
  end
  else begin
    qsort(1,n);
    m:=1;
    c[1]:=a[1];
    for i:=2 to t do
      if a[i]<>a[i-1] then
      begin
        inc(m);
        c[m]:=a[i];
      end;
    mid:=a[t shr 1];
    for i:=1 to n do
      ans:=ans+abs(b[i].x-mid)+abs(b[i].y-mid);
    for i:=1 to n do
    begin
      b[i].x:=find(1,m,b[i].x);
      b[i].y:=find(1,m,b[i].y);
      add(1,1,m,1,b[i].x,1);
      add(1,1,m,1,b[i].y,1);
    end;
    for i:=1 to n do
    begin
      add(1,1,m,0,b[i].x,1);
      add(1,1,m,0,b[i].y,1);
      add(1,1,m,1,b[i].x,-1);
      add(1,1,m,1,b[i].y,-1);
      min(ans,sum(0,i*2)+sum(1,t-i*2));
    end;
  end;
  writeln(ans+s+n);
end.