T1.
马农：
题目大意：
来自大草原的两兄弟决心成为超级“马农”，专门饲养战马。他们将可以养马的区域，分为 N*N 的单位面积的正方形，每块单位面积的收益为a[i,j]，收益a[i,j]可能是负数，养马也不是包赚的，马匹也可能出现生病死亡等意外。然后两人的马场都必须是矩形区域。同时，规定两个马场的矩形区域相邻，且只有一个交点。且两人希望两个马场的收益相当，希望你给他们设计马场，求共有多少种设计方案。
40%的数据， N<=10。
100%的数据， N<=50, -1000
const
modn=300007;
var
hash:array [0..modn,1..2] of longint;
p:array [0..modn] of longint;
sum:array [0..51,0..51] of longint;
n,i,j,k,l,m,cd,ans:longint;
function insert(d:longint):longint;
var
i:longint;
begin
i:=abs(d) mod modn;
while (hash[i,1]<>0) and (hash[i,1]<>d) do
begin
inc(i);
if i>modn then i:=0;
end;
exit(i);
end;
begin
assign(input,'farmer.in'); reset(input);
assign(output,'farmer.out'); rewrite(output);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(sum[i,j]);
sum[i,j]:=sum[i,j-1]+sum[i,j];
end;
readln;
end;
for i:=1 to n do
for j:=1 to n do
begin
p[0]:=0;
for k:=0 to j-1 do
begin
l:=0;
for m:=i downto 1 do
begin
l:=l+(sum[m,j]-sum[m,k]);
inc(p[0]);
p[p[0]]:=insert(l);
hash[p[p[0]],1]:=l;
inc(hash[p[p[0]],2]);
end;
end;
for k:=j+1 to n do
begin
l:=0;
for m:=i+1 to n do
begin
l:=l+(sum[m,k]-sum[m,j]);
cd:=insert(l);
if hash[cd,1]=l then inc(ans,hash[cd,2]);
end;
end;
for k:=1 to p[0] do
begin
hash[p[k],1]:=0;
hash[p[k],2]:=0;
end;
p[0]:=0;
for k:=j to n do
begin
l:=0;
for m:=i downto 1 do
begin
l:=l+(sum[m,k]-sum[m,j-1]);
inc(p[0]);
p[p[0]]:=insert(l);
hash[p[p[0]],1]:=l;
inc(hash[p[p[0]],2]);
end;
end;
for k:=0 to j-2 do
begin
l:=0;
for m:=i+1 to n do
begin
l:=l+(sum[m,j-1]-sum[m,k]);
cd:=insert(l);
if hash[cd,1]=l then inc(ans,hash[cd,2]);
end;
end;
for k:=1 to p[0] do
begin
hash[p[k],1]:=0;
hash[p[k],2]:=0;
end;
end;
writeln(ans);
close(input); close(output);
end.T2.
马语翻译：
有N个马种，机器人有 M 种，每种机器人能完成 K 个马种之间的语言翻译。问，利用这些机器人，能否实现 1 种群和 N 种群的马语翻译。 若可以，找到翻译过程至少需要用到多少种语言，求最少转换语言的次数。如果无法完成翻译，输出-1。
40%的数据 N<=100， 1<=K<=20， M<=40。
100%的数据 1<=N<=100000， 1<=K<=1000， 1<=M<=1000
题解：
有待完成。。。
T3.
马球比赛：
N个乡镇之间要进行马球联赛。每个乡镇有a[i]匹马，首先，所有乡镇都要求，本乡镇所有的马匹都必须参赛，或者都不参赛（若组队的马匹数量不是该镇马匹数量的约数，将无法参赛）。其次，在本乡镇，选出最佳球队，参加乡镇间联赛。比赛组织方希望满足所有参赛乡镇的要求，并且使得决赛的马匹尽可能多，请你设计每个球队马匹的数量，使得决赛马匹数最大。
注意，决赛至少有 2 个队伍晋级。
20%的数据 2<=N<=100， 1<=a(i)<=10000。
50%的数据 2<=N<=20000。
100%的数据 2<=N<=200000， 1<=a(i)<= 2000000
题解：
这题呢，其实可以递推
首先设f[i]表示以i为参赛标准时，有多少只队伍能参赛。
可以推出：
f[j]=f[j]+f[i] j为i的约数
同理，f[i div j]=f[i div j]+f[i] 然后容易被卡常，就自行脑补
时间复杂度：O（max（a[i]）*Σtrunc（sqrt（i）））
//i为1~max(a[i])
var
sum:array [0..2000001] of int64;
a:array [0..200001] of longint;
cmax,p,q,n,i,j:longint;
mmax:int64;
function max(aa,bb:int64):int64;
begin
if aa>bb then exit(aa);
exit(bb);
end;
begin
assign(input,'polo.in'); reset(input);
assign(output,'polo.out');rewrite(output);
read(n);
cmax:=0;
for i:=1 to n do
begin
read(a[i]);
inc(sum[a[i]]);
cmax:=max(cmax,a[i]);
end;
mmax:=n;
if cmax=2000000 then cmax:=cmax div 20;
for i:=2 to cmax do
if sum[i]<>0 then
begin
for j:=2 to trunc(sqrt(i)) do
if (i mod j=0) then
begin
sum[j]:=sum[j]+sum[i];
if j*j<>i then
sum[i div j]:=sum[i div j]+sum[i];
end;
end;
if cmax=100000 then cmax:=cmax*20;
for i:=2 to cmax do
if sum[i]>1 then mmax:=max(mmax,sum[i]*i);
writeln(mmax);
close(input); close(output);
end.T4.
数列：
题目大意：
给定一个长度为N的数列，求一段连续的子数列满足该子数列中的各元素的平均数大于A，输出可行方案的总数。
对于60%的数据 N <= 1000
对于100%的数据 N <= 100000
所有数据包括都在longint范围内。
题解：
其实对于每一次的输入的数a[i]，我们都将它减去平均数A，然后全部做一遍前缀和。
首先我们知道对于某个前缀和sum[i]，如果它>0就先给答案+1
然后如果sum[i]
var
d,rp,sum:array [0..100001] of longint;
x,i,j,n,m,pd:longint;
ans:int64;
procedure qsort(l,r:longint);
var
mid,i,j:longint;
begin
if l>=r then exit;
i:=l; j:=r;
mid:=sum[(l+r) div 2];
repeat
while sum[i]<mid do inc(i);
while sum[j]>mid do dec(j);
if i<=j then
begin
sum[0]:=sum[i]; d[0]:=d[i];
sum[i]:=sum[j]; d[i]:=d[j];
sum[j]:=sum[0]; d[j]:=d[0];
inc(i); dec(j);
end;
until i>j;
qsort(i,r);
qsort(l,j);
end;
begin
assign(input,'sequence.in'); reset(input);
assign(output,'sequence.out'); rewrite(output);
readln(n,m);
ans:=0;
for i:=1 to n do
begin
read(x);
sum[i]:=sum[i-1]+(x-m);
if sum[i]>0 then inc(ans);
d[i]:=i;
end;
qsort(1,n);
i:=1; j:=1;
while i<=n do
begin
rp[d[i]]:=j;
while sum[i]=sum[i+1] do
begin
inc(i);
rp[d[i]]:=j;
end;
inc(i); inc(j);
end;
dec(j);
for i:=0 to j do sum[i]:=0;
for i:=1 to n do
begin
pd:=rp[i]-1;
while pd>0 do
begin
ans:=ans+sum[pd];
pd:=pd-pd and (-pd);
end;
pd:=rp[i];
while pd<=j do
begin
sum[pd]:=sum[pd]+1;
pd:=pd+pd and (-pd);
end;
end;
writeln(ans);
close(input); close(output);
end.