第一题：队爷的新书
题意简述：给定n个闭区间，求出一个数p使它与包含它的区间数的积最大，输出这个积。
分析：使用一个差分数组g，每个区间[l,r]，l位置加1，r+1的位置减1，从前往后统计，得到对于每个p包含它的区间个数，相乘看是否最大。由于数据较大，需要离散化。
program book;
var
a,f,g:array[..]of qword;
l,r:array[..]of longint;
n,i,m:longint; sum,ans:qword;
procedure qsort(l,h:longint);
var i,j,t:longint; m:qword;
begin i:=l; j:=h;
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;
inc(i); dec(j); end; until i>j;
if i<h then qsort(i,h); if j>l then qsort(l,j); end;
function make(x:longint):longint;
var l,r,mid,ans:longint;
begin
l:=;r:=m;
while l<=r do
begin
mid:=(l+r) div ;
if f[mid]<=x then begin ans:=mid; l:=mid+; end
else begin r:=mid-; end;
end;
exit(ans);
end;
procedure fry;
var i:longint;
begin
qsort(,*n);
a[]:=-;
for i:= to *n do
if a[i]<>a[i-] then begin inc(m); f[m]:=a[i]; end;
for i:= to n do
begin
l[i]:=make(l[i]); r[i]:=make(r[i]);
end;
end;
begin
assign(input,'book.in');
reset(input);
assign(output,'book.out');
rewrite(output);
readln(n); m:=;
for i:= to n do
begin
readln(l[i],r[i]);
a[i*-]:=l[i]; a[i*]:=r[i];
end;
fry;
for i:= to n do
begin
inc(g[l[i]]); dec(g[r[i]+]);
end;
for i:= to m do
begin
inc(sum,g[i]);
if sum*f[i]>ans then ans:=sum*f[i];
end;
writeln(ans);
close(input); close(output);
end.
第三题：队爷的讲学计划
题意简述：一个有向图中，队爷从1点出发在图上行走，每条边都要一个花费，如果他走到某个点i，则该店对应强连通分量中的边权全部变为1，前往经过这些边只要花费1的代价且只需要交1次钱（由于你第一次到达i的时候交了钱，所依回到i的那个边不需要交钱），求队爷能走过的最多的点数，和在满足点数最多情况下最少花费。
分析：由于要求经过的点最多，显然对于每个强连通分量，队爷肯定要前往其包含的所有点，这样显然最优。
所以我们将每个强连通分量各自缩为一个点，这个点对应的点数（题目中的城市数）为分量包含的总点数，由于每条路只交一次钱，故代价为点数-1。
这样我们得到一个DAG，在图上跑SPFA求出最长路并同时求出对应最小花费即可。
另外看清题目没有要求终点，则终点可以是每个点。