NOIP试题解析 by QTY_YTQ
noip2010关押罪犯（并查集）
题意是有n个罪犯关在两个监狱中，其中有m对罪犯有仇恨关系，如果有仇恨的罪犯关在一起会产生一定影响力的事件，要求安排罪犯位置使产生影响力最大的事件影响最小。
可以用并查集来做，每个罪犯抽象为两个点，一个表示该罪犯关押在1监狱，另一个表示该罪犯关押在2监狱，我们将罪犯仇恨关系按影响的大小排序，每次选取影响力最大的一对罪犯(x,y)，尽可能不让它们在一个监狱内，将x1和y2合并，将x2和y1合并，继续往后做，知道两个罪犯已经在同一集合内，这时不能让这两个罪犯在不同监狱中，则他们之间的影响力就是最小的最大影响力，
代码：
program prison;
var
a,b,c:array[..]of longint;
f:array[..]of longint;
n,i,m,x,y,v,x1,y1,x2,y2:longint;
function find(x:longint):longint;
var i,j,k:longint;
begin
i:=x; j:=i;
while f[i]<>i do i:=f[i];
while j<>i do
begin k:=f[j];f[j]:=i; j:=k; end;
exit(i);
end;
procedure qsort(l,r:longint);
var i,j,m,t:longint;
begin
i:=l; j:=r; m:=c[(l+r) div ];
repeat
while c[i]>m do inc(i);
while c[j]<m do dec(j);
if i<=j then
begin
t:=c[i]; c[i]:=c[j]; c[j]:=t;
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
inc(i); dec(j);
end;
until i>j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
readln(n,m);
for i:= to n* do f[i]:=i;
for i:= to m do
begin
readln(x,y,v);
a[i]:=x; b[i]:=y; c[i]:=v;
end;
qsort(,m);
for i:= to m do
begin
x1:=find(a[i]); x2:=find(a[i]+n);
y1:=find(b[i]); y2:=find(b[i]+n);
if (x1<>y1)and(x2<>y2) then begin f[x2]:=y1; f[y2]:=x1; end
else begin writeln(c[i]); n:=-;break; end;
end;
if n>= then writeln();
end.
noip2011选择客栈（思考+rmq）
题意是有n个客栈排成一排，每种客栈有一个颜色，共k种颜色，有两个人要住在同种颜色的不同客栈中，并且要到这两个客栈之间（包括这两个客栈）的某家客栈喝咖啡，并且花费不超过p，求满足该条件的住宿方案数。
主要思路是，先rmqst算法得到任意两客栈之间客栈喝咖啡的最小花费，可以看出，如果选择i客栈和j客栈最小花费不超过p，则选择i客栈和j以后客栈的最小花费必然不超过p，选择i之前客栈和j客栈的最小花费也不超过p，那么我们从1做到n，对于客栈i，对应颜色x，先判断它左边最靠近它的颜色是x一个客栈与该客栈之间的最小花费是否超过p，超过则计数器直接加上之前满足某一方案且颜色为x的客栈数，没超过则加上i之前颜色为x的客栈总数，得到答案。
代码：
program hotel;
var
h:array[..,..]of longint;
a,b:array[..]of longint;
pl:array[..]of longint;
r,c,u:array[..]of longint;
n,i,m,j,k,p,x,s:longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function find(x,y:longint):longint;
var j:longint;
begin
j:=trunc(ln(y-x+)/ln());
exit(min(h[j,x],h[j,y-pl[j]+]));
end;
begin
assign(input,'hotel.in');
reset(input);
assign(output,'hotel.out');
rewrite(output);
readln(n,k,p);
for i:= to n do
readln(b[i],a[i]);
pl[]:=;
for i:= to trunc(ln(n)/ln()) do pl[i]:=pl[i-]*;
for i:= to n do h[,i]:=a[i];
for i:= to trunc(ln(n)/ln()) do
for j:= to n+-*i do
h[i,j]:=min(h[i-,j],h[i-,j+pl[i-]]);
for i:= to n do
begin
x:=b[i];
if u[x]= then begin r[x]:=i;u[x]:=; end
else
begin
k:=find(r[x],i);
if k<=p then begin c[x]:=u[x];u[x]:=u[x]+;s:=s+c[x];r[x]:=i; end
else begin s:=s+c[x]; u[x]:=u[x]+; r[x]:=i; end;
end;
end;
writeln(s);
close(input); close(output);
end.
noip2011聪明的质监员（二分）
题意什么的按题目来，需要注意的每个区间的值是由该区间上重量超过w矿石个数乘上该区间重量超过w矿石的价值和。
二分答案，然后前缀和得到区间上超过w矿石的价值和与数量和，然后判断比s大还是小，利用w越大，y越小的单调性变换上下界。
代码：
program qc;
var
w,v,x,y,s1,s2:array[..]of int64;
n,i,m,l,r,mid:longint; s,x1,x2:int64;
function find(k:longint):int64;
var i,j:longint; sum:int64;
begin
sum:=;
fillchar(s1,sizeof(s1),); fillchar(s2,sizeof(s2),);
for i:= to n do
begin s1[i]:=s1[i-]+ord(w[i]>=k)*v[i];s2[i]:=s2[i-]+ord(w[i]>=k); end;
for i:= to m do
sum:=sum+(s1[y[i]]-s1[x[i]-])*(s2[y[i]]-s2[x[i]-]);
exit(sum);
end;
begin
assign(input,'qc.in');
reset(input);
assign(output,'qc.out');
rewrite(output);
readln(n,m,s);
for i:= to n do
begin readln(w[i],v[i]); if w[i]>r then r:=w[i]; end;
for i:= to m do
readln(x[i],y[i]);l:=;
while l<=r do
begin
mid:=(l+r) div ;
if find(mid)<=s then r:=mid- else l:=mid+;
end;
x1:=find(l); x2:=find(r);
if abs(x1-s)<abs(x2-s) then writeln(abs(x1-s)) else writeln(abs(x2-s));
close(input); close(output);
end.
noip2012借教室（二分+前缀和）
题意是每天有一些教室可以租借，有m份请求分别要租借一定数量教室一段时间，输出最先无法满足的请求序号。
二分答案，利用前缀和记录不同时间租借教室的个数，判断是否满足。
代码:
program classroom;
var
f,d,s,t,b:array[..]of int64;
n,i,m,k,l,r,mid,ans:longint; sum:int64;
begin
assign(input,'classroom.in');
reset(input);
assign(output,'classroom.out');
rewrite(output);
readln(n,m);
for i:= to n do read(f[i]);
for i:= to m do
readln(d[i],s[i],t[i]);
l:=; r:=m;
while l<=r do
begin
mid:=(l+r) div ;
fillchar(b,sizeof(b),);
for i:= to mid do
begin
inc(b[s[i]],d[i]);inc(b[t[i]+],-d[i]);
end;
sum:=; k:=;
for i:= to n do
begin
sum:=sum+b[i]; if sum>f[i] then begin k:=; break; end;
end;
if k= then r:=mid-
else begin ans:=mid; l:=mid+; end;
end;
if ans>=m then writeln()
else begin writeln(-); writeln(ans+); end;
close(input); close(output);
end.
noip2013火柴排队（贪心+逆序对）
题意两组火柴，同组火柴高度不同，分别将两组火柴以两两交换形式得到新序列，使两组火柴同位置火柴高度差绝对值和最小，求最少交换次数。
显然1组第一高的火柴要对应2组第一高的火柴，第二高也对应第二高，以此类推，我们对火柴高度离散化后，以一组火柴为参照，求另一组火柴高度逆序对个数即可。
代码：
program match;
type
arr=array[..]of longint;
var
a,b,u,v,bit:arr;
n,i,m:longint; t:int64;
procedure add(i,x:longint);
begin
while i<=n do
begin
bit[i]:=bit[i]+x; inc(i,i and -i);
end;
end;
function sum(i:longint):longint;
var s:longint;
begin
s:=;
while i> do
begin
s:=s+bit[i]; dec(i,i and -i);
end;
exit(s);
end;
procedure qsort(l,r:longint; var a,u:arr);
var i,j,t,m:longint;
begin
i:=l; j:=r; m:=a[(i+j) div ];
repeat
while a[i]<m do inc(i);
while m<a[j] do dec(j);
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=u[i]; u[i]:=u[j]; u[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r,a,u);
if l<j then qsort(l,j,a,u);
end;
begin
assign(input,'match.in');
reset(input);
assign(output,'match.out');
rewrite(output);
readln(n);
for i:= to n do begin read(a[i]);u[i]:=i; end; readln;
for i:= to n do begin read(b[i]);v[i]:=i; end;
qsort(,n,a,u); qsort(,n,b,v);
for i:= to n do
begin
a[i]:=i; b[v[i]]:=u[i];
end;
for i:=n downto do
begin
inc(t,sum(b[i]));add(b[i],);
end;
writeln(t mod );
close(input); close(output);
end.
noip2014联合权值
题意很简单，不说了（其实是我懒得写）。
记录下每个点与之相邻所有点的权值和，权值平方和，最大值，次大值，所有点最大次大值乘积的最大值就是最大联合权值，权值和平方减权值平方和的和就是联合权值和。
代码：
program link;
var
a,b,v,max1,max2,sum,num:array[..]of int64;
n,i:longint; m,ans:int64;
begin
assign(input,'link.in');
reset(input);
assign(output,'link.out');
rewrite(output);
readln(n);
for i:= to n- do
readln(a[i],b[i]);
for i:= to n do read(v[i]);
for i:= to n- do
begin
if v[b[i]]>max1[a[i]] then begin max2[a[i]]:=max1[a[i]];max1[a[i]]:=v[b[i]]; end
else if v[b[i]]>max2[a[i]] then max2[a[i]]:=v[b[i]];
if v[a[i]]>max1[b[i]] then begin max2[b[i]]:=max1[b[i]];max1[b[i]]:=v[a[i]]; end
else if v[a[i]]>max2[b[i]] then max2[b[i]]:=v[a[i]];
inc(sum[a[i]],v[b[i]]); inc(num[a[i]],sqr(v[b[i]]));
inc(sum[b[i]],v[a[i]]); inc(num[b[i]],sqr(v[a[i]]));
end;
for i:= to n do
if max1[i]*max2[i]>m then m:=max1[i]*max2[i];
for i:= to n do
begin
ans:=(ans+(sqr(sum[i])-num[i]) mod ) mod ;
end;
writeln(m,' ',ans);
close(input); close(output);
end.
noip2014寻找道路
题意很简单不解释。
看清题意很重要，起点终点是由输入提供的，另外符合要求的点其所有出边指向的点与终点联通，无解输出-1.
做起来很简单，所有边反过来求一边终点到各点最短路径，判断每个点是否符合，然后在符合要求的点中求起点到终点最短路。
代码：
program road;
var
c,a:array[..,..]of longint;
q:array[..]of longint;
dis:array[..]of longint;
g,r:array[..]of boolean;
n,i,m,j,t,x,y,z,h,u,v:longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
begin
assign(input,'road.in');
reset(input);
assign(output,'road.out');
rewrite(output);
readln(n,t);
for i:= to t do
begin
readln(x,y);
a[x,]:=a[x,]+; a[x,a[x,]]:=y;
c[y,]:=c[y,]+; c[y,c[y,]]:=x;
end; readln(x,y);
for i:= to n do dis[i]:=maxlongint div ;
fillchar(g,sizeof(g),false);
h:=; t:=; dis[y]:=; q[]:=y; g[y]:=true;
while h<t do
begin
h:=h+; u:=q[h]; g[u]:=false;
for i:= to c[u,] do
begin
v:=c[u,i];
if dis[u]+<dis[v] then
begin
dis[v]:=dis[u]+;
if g[v]=false then
begin
t:=t+; q[t]:=v; g[v]:=true;
end;
end;
end;
end;
for i:= to n do
begin
r[i]:=true;
for j:= to a[i,] do
if dis[a[i,j]]>=maxlongint div then begin r[i]:=false; break; end;
end;
for i:= to n do dis[i]:=maxlongint div ;
fillchar(g,sizeof(g),false);
h:=; t:=; dis[x]:=; q[]:=x; g[x]:=true;
while h<t do
begin
h:=h+; u:=q[h]; g[u]:=false;
for i:= to a[u,] do
begin
v:=a[u,i];
if (dis[u]+<dis[v])and(r[v]=true) then
begin
dis[v]:=dis[u]+;
if g[v]=false then
begin
t:=t+; q[t]:=v; g[v]:=true;
end;
end;
end;
end; if (r[x]=false)or(dis[y]>=maxlongint div ) then writeln(-) else writeln(dis[y]);
close(input); close(output);
end.