分组赛讲课讲了APIO2015的题，于是回去就做完了
稍微写一点题解吧
bzoj4069 逐位处理的简单题，然后就是bool型dp
然后a=1 的时候可以把一位状态干掉
当一维状态单调且是bool型dp时，我们可以用dp表示这一维状态；类似的思想也在bzoj1937出现过
var s:array[..] of int64;
n,a,b,i,j,k,p:longint;
g,c:array[..] of longint;
f:array[..,..] 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:= to n do
begin
read(c[i]);
s[i]:=s[i-]+c[i];
end;
if a= then
begin
for p:= downto do
begin
now:=now or int64() shl int64(p);
g[]:=;
for i:= to n do
g[i]:=n+;
for i:= to n do
for j:= to i do
begin
if (s[i]-s[j-]) and now> then continue; //当前模板是0就不能为1，是1就随意，这里转化一下方便快速匹配
g[i]:=min(g[i],g[j-]+);
end;
if g[n]>b then
now:=now xor int64() shl int64(p);
end;
end
else begin
for p:= downto do
begin
now:=now or int64() shl int64(p);
fillchar(f,sizeof(f),false);
f[,]:=true;
for i:= to n do
for j:= to n do
for k:= to i do
if f[k-,j-] then
begin
f[i,j]:=((s[i]-s[k-]) and now=);
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() shl int64(p);
end;
end;
for p:= downto do
now:=now xor int64() shl int64(p);
writeln(now);
end.
4069
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=;
type node=record
po,next,num:longint;
end;
point=record
loc,num:longint;
end; var h:array[..] of point;
e:array[..] of node;
p,d,wh:array[..] of longint;
v,c,b,f:array[..] of longint;
w:array[..,..] 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 ;
while j<=tot do
begin
if (j<tot) and (h[j].num>h[j+].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 ;
end
else break;
end;
end; procedure up(i:longint);
var j,x,y:longint;
begin
j:=i shr ;
while j> 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 ;
end
else break;
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(b[i],f[i]);
inc(b[i]);
if i= then st:=b[i];
if i= then en:=b[i];
v[f[i]]:=;
end;
for i:= to n do
if v[i]= then
begin
inc(r);
c[r]:=i;
v[i]:=r;
end; size:=trunc(sqrt(r));
if size> then size:=;
t:=n;
for i:= to size do
begin
for j:= to n do
begin
inc(t);
w[j,i]:=t;
add(t,j,);
end;
for j:= to n-c[i] do
begin
add(w[j,i],w[j+c[i],i],);
add(w[j+c[i],i],w[j,i],);
end;
end; for i:= to m do
if f[i]<=c[size] then
add(b[i],w[b[i],v[f[i]]],)
else begin
j:=;
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:=;
while true do
begin
if b[i]-f[i]*j<= then break;
add(b[i],b[i]-f[i]*j,j);
inc(j);
end;
end; tot:=;
h[].loc:=st;
h[].num:=;
for i:= 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> do
begin
x:=h[].loc;
if x=en then break;
if h[].num=inf then break;
wh[h[tot].loc]:=;
swap(h[],h[tot]);
dec(tot);
sift();
i:=p[x];
while i<> 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(-)
else writeln(d[en]);
end.
4070
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[..] of longint;
b:array[..] of node;
tree:array[..*,..] 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 ];
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 ].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 ;
if c[m]=x then exit(m);
if c[m]>x then r:=m- else l:=m+;
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 ;
if x<=m then add(i*,l,m,w,x,y)
else add(i*+,m+,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 ;
if tree[i*,w].s>=k then exit(get(i*,l,m,w,k))
else exit(tree[i*,w].sum+get(i*+,m+,r,w,k-tree[i*,w].s));
end;
end; function sum(w,n:longint):int64;
begin
exit(tree[,w].sum-*get(,,m,w,n shr ));
end; begin
readln(k,n);
for i:= 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:=;
for i:= to n do
begin
inc(t);
a[t]:=b[i].x;
inc(t);
a[t]:=b[i].y;
end;
sort(,t);
if k= then
begin
x:=a[(t+) shr ];
ans:=;
for i:= to t do
ans:=ans+abs(x-a[i]);
end
else begin
qsort(,n);
m:=;
c[]:=a[];
for i:= to t do
if a[i]<>a[i-] then
begin
inc(m);
c[m]:=a[i];
end;
mid:=a[t shr ];
for i:= to n do
ans:=ans+abs(b[i].x-mid)+abs(b[i].y-mid);
for i:= to n do
begin
b[i].x:=find(,m,b[i].x);
b[i].y:=find(,m,b[i].y);
add(,,m,,b[i].x,);
add(,,m,,b[i].y,);
end;
for i:= to n do
begin
add(,,m,,b[i].x,);
add(,,m,,b[i].y,);
add(,,m,,b[i].x,-);
add(,,m,,b[i].y,-);
min(ans,sum(,i*)+sum(,t-i*));
end;
end;
writeln(ans+s+n);
end.
4071
