又来写题解辣～然而并不太清楚题目排列情况。。。不管辣先写起来～
T1:［bzoj1041］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1041
一个赤果果的数学题～～～
首先坐标轴上一定有四个，
最大公约数搞一下然后判断一下就可以啦，细节全部都在代码～
代码如下：
var i,j,ans,d:longint;
t,r,m:int64;
function flag(x,y:longint):longint;
var t:longint;
begin
if (x<y) then
begin
t:=x;
x:=y;
y:=t;
end;
x:=x mod y;
if (x=) then exit(y) else exit(flag(x,y));
end;
begin
readln(r);
ans:=;
t:=*r;
for d:= to trunc(sqrt(t)) do
if (t mod d=) then
begin
for i:= to trunc(sqrt(r/d)) do
begin
j:=trunc(sqrt(t/d-i*i));
if (j=sqrt(t/d-i*i)) and (i<>j) and (flag(i,j)=) then inc(ans);
end;
for i:= to trunc(sqrt(d/)) do
begin
j:=trunc(sqrt(d-i*i));
if (j*j=d-i*i) and (i<>j) and (flag(i,j)=) then inc(ans);
end;
end;
ans:=ans*+;
writeln(ans);
end.
T2:［bzoj1042］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1042
又一个数学题hhh
先动态规划预处理，然后容斥原理就可以了。
代码如下：
var i,j,k,l,tot,g:longint;
c,s:array[..] of longint;
f:array[..] of int64;
ans:int64;
function f1(x:longint):int64;
begin
if (x>=) then exit(f[x]) else exit();
end;
begin
fillchar(c,sizeof(c),);
fillchar(f,sizeof(f),);
readln(c[],c[],c[],c[],tot);
f[]:=;
for i:= to do
for j:=c[i] to do
f[j]:=f[j]+f[j-c[i]];
for i:= to tot do
begin
fillchar(s,sizeof(s),);
for j:= to do
read(s[j]);
readln(g);
ans:=f[g];
for j:= to do
ans:=ans-f1(g-(s[j]+)*c[j]);
for j:= to do
for k:=j+ to do
if (j<>k) then
ans:=ans+f1(g-(s[j]+)*c[j]-(s[k]+)*c[k]);
for j:= to do
for k:=j+ to do
for l:=k+ to do
if (j<>k) and (k<>l) and (j<>l) then
ans:=ans-f1(g-(s[j]+)*c[j]-(s[k]+)*c[k]-(s[l]+)*c[l]);
ans:=ans+f1(g-(s[]+)*c[]-(s[]+)*c[]-(s[]+)*c[]-(s[]+)*c[]);
writeln(ans);
end;
end.
(T3先留好坑。。。之后补）
T4:［bzoj1044］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1044
第一问就是NOIP2015的day2T1（把我坑死的QAQQQ），
第二问就是动态规划就行了。
代码如下：
var n,m,i,j,k,ans,left,right,max,anss,s,now1,x,y:longint;
l,sl,ty:array[..] of longint;
f,f1:array[..,-..] of longint;
function tryit(x:longint):boolean;
var i,j,s,left,right:longint;
begin
i:=;
j:=;
now1:=;
while (i<n) do
begin
left:=i+;
right:=n;
i:=(left+right) div ;
while (right-left>) do
begin
if (sl[i]-sl[now1]<=x) then left:=i else right:=i;
i:=(left+right) div ;
end;
if (sl[right]-sl[now1]<=x) then i:=right else i:=left;
if (sl[n]-sl[now1]>x) then inc(j);
now1:=i;
end;
if (j>m) then exit(false) else exit(true);
end;
begin
read(n,m);
fillchar(l,sizeof(l),);
fillchar(sl,sizeof(sl),);
s:=;
max:=;
for i:= to n do
begin
read(l[i]);
sl[i]:=sl[i-]+l[i];
if (l[i]>max) then max:=l[i];
s:=s+l[i];
end;
left:=max;
right:=s;
ans:=(left+right) div ;
while (right-left>) do
begin
if not(tryit(ans)) then left:=ans else right:=ans;
ans:=(left+right) div ;
end;
ans:=right;
if tryit(left) then ans:=left;
write(ans,' ');
fillchar(f,sizeof(f),);
fillchar(ty,sizeof(ty),);
fillchar(f1,sizeof(f1),);
anss:=;
f[,]:=;
for i:= to n do
f1[,i]:=;
k:=;
for j:= to n do
begin
while (sl[j]-sl[k]>ans) do inc(k);
ty[j]:=k;
end;
for i:= to m+ do
begin
x:=i mod ;
y:=-x;
for j:= to n do
begin
f[y,j]:=(f1[x,j-]-f1[x,ty[j]-]+) mod ;
f1[y,j]:=(f[y,j]+f1[y,j-]) mod ;
end;
anss:=(anss+f[y,n]) mod ;
end;
writeln(anss);
end.
T5:［bzoj1045］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1045
这题。。。标准的组合数学嘛～～～
随便搞一下就粗来了。。。QAQ
辣么辣么多数学题QAQQQ
代码如下：
var n,i,j:longint;
sum,ave,ans:int64;
a,p:array[..] of longint;
procedure qsort(lx,rx:longint);
var i,j,m,x:longint;
begin
i:=lx;
j:=rx;
m:=p[(i+j) div ];
repeat
while (p[i]<m) do inc(i);
while (p[j]>m) do dec(j);
if (i<=j) then
begin
x:=p[i];
p[i]:=p[j];
p[j]:=x;
inc(i);
dec(j);
end;
until (i>j);
if (i<rx) then qsort(i,rx);
if (j>lx) then qsort(lx,j);
end;
begin
readln(n);
fillchar(a,sizeof(a),);
fillchar(p,sizeof(p),);
sum:=;
for i:= to n do
begin
readln(a[i]);
sum:=sum+a[i];
end;
ave:=sum div n;
for i:= to n do
p[i]:=p[i-]-ave+a[i];
qsort(,n);
ans:=;
for i:= to n do
ans:=ans+abs(p[i]-p[n div +]);
writeln(ans);
end.
T6：［bzoj1054］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1054
QAQ这题是一个赤果果的BFS。。。
不对。。。
BFS要判重。。。这题判重都不要hhh
代码如下：
type arr=array[..,..] of longint;
const modp=;
tx:array[..] of longint=(,-,,);
ty:array[..] of longint=(,,,-);
var i,j,k,s,t,s1,s2,rx,ry,swap,rh:longint;
q:array[..*] of arr;
mark:array[..*] of boolean;
step:array[..*] of longint;
ans:arr;
ch:char;
function hash(x:arr):longint;
var i,j,ans,now:longint;
begin
ans:=;
now:=;
for i:= to do
for j:= to do
begin
ans:=(ans+int64(now*x[i,j]));
now:=(now+now);
end;
exit(ans);
end;
begin
s:=;
t:=;
fillchar(q,sizeof(q),);
fillchar(ans,sizeof(ans),);
for i:= to do
begin
for j:= to do
begin
read(ch);
while (ch<>'') and (ch<>'') do read(ch);
q[,i,j]:=ord(ch)-;
end;
end;
for i:= to do
begin
for j:= to do
begin
read(ch);
while (ch<>'') and (ch<>'') do read(ch);
ans[i,j]:=ord(ch)-;
end;
end;
s1:=hash(q[s]);s2:=hash(ans);
mark[s1]:=true;
fillchar(step,sizeof(step),);
if (s1=s2) then writeln('') else
begin
while (s<t) do
begin
for i:= to do
for j:= to do
if (q[s,i,j]>) then
begin
for k:= to do
begin
rx:=i+tx[k];ry:=j+ty[k];
if (<=rx) and (rx<=) and (<=ry) and (ry<=) and (q[s,rx,ry]=) then
begin
swap:=q[s,i,j];q[s,i,j]:=q[s,rx,ry];q[s,rx,ry]:=swap;
rh:=hash(q[s]);
if not(mark[rh]) then
begin
if (rh=s2) then
begin
writeln(step[s]+);
halt;
end;
mark[rh]:=true;
q[t]:=q[s];
step[t]:=step[s]+;
inc(t);
end;
swap:=q[s,i,j];q[s,i,j]:=q[s,rx,ry];q[s,rx,ry]:=swap;
end;
end;
end;
inc(s);
end;
end;
end.
T7:［bzoj1055］
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1055
又一个动态规划呢！
不过是一个记忆化搜索。。。
代码如下：
const ch:array[..] of char=('W','I','N','G');
var i,j:longint;
f,flag:array[..,..,..] of boolean;
x:array[..,..,..] of char;
a:array[..] of longint;
s:string;
flagg:boolean;
function calc(x:char):longint;
begin
if (x='W') then exit()
else if (x='I') then exit()
else if (x='N') then exit()
else if (x='G') then exit();
end;
function f1(k,left,right:longint):boolean;
var i,j,t1,t2:longint;
begin
if flag[k,left,right] then exit(f[k,left,right]);
flag[k,left,right]:=true;
if (right=left) and (s[left]=ch[k]) then
begin
f[k,left,right]:=true;
exit(true);
end;
for i:= to a[k] do
begin
t1:=calc(x[k,i,]);
t2:=calc(x[k,i,]);
for j:=left to right- do
if f1(t1,left,j) and f1(t2,j+,right) then
begin
f[k,left,right]:=true;
exit(true);
end;
end;
f[k,left,right]:=false;
exit(false);
end;
begin
fillchar(a,sizeof(a),);
for i:= to do
read(a[i]);
readln;
fillchar(f,sizeof(f),false);
fillchar(flag,sizeof(flag),false);
for j:= to do
for i:= to a[j] do
readln(x[j,i,],x[j,i,]);
readln(s);
flagg:=false;
for i:= to do
if f1(i,,length(s)) then
begin
write(ch[i]);
flagg:=true;
end;
if not(flagg) then write('The name is wrong!');
writeln;
end.
（T8的坑也先留着。。。QAQQQ）
终于写完啦～～～撒花撒花～～～