哈尔滨市第三中学 刘翀

　　　　　　　　　　5． 《方程的解》的程序 

　　program equation;
　　　const maxm=150;
　　　　　　max=4000037;
　　　var k,p:array[1..6]of longint;
　　　　　　fin,fout:text;
　　　　　　n,m:integer;
　　　　　　ans:longint;
　　　　　　mi:array[1..maxm,1..30]of longint;
　　　　　　e:array[0..max-1,1..2]of longint;
　　　procedure init;
　　　　var i:integer;
　　　　begin
　　　　　assign(fin,'equation.in');
　　　　　assign(fout,'equation.out');
　　　　　reset(fin);
　　　　　rewrite(fout);
　　　　　read(fin,n);
　　　　　read(fin,m);
　　　　　for i:=1 to n do
　　　　　　read(fin,k[i],p[i]);
　　　　　close(fin);
　　　　　fillchar(e,sizeof(e),0);
　　　　　ans:=0;
　　　　end;
　　procedure precompute;
　　　var i,j:integer;
　　　　　tmp:longint;
　　　begin
　　　　for j:=1 to 30 do
　　　　　mi[1,j]:=1;
　　　　for i:=2 to m do
　　　　　begin
　　　　　　tmp:=1;
　　　　　　for j:=1 to trunc(ln(maxlongint)/ln(i)) do
　　　　　　　begin
　　　　　　　　tmp:=tmp*i;
　　　　　　　　mi[i,j]:=tmp;
　　　　　　　end;
　　　　　end;
　　　　end;
　　function locate(x:longint):longint;
　　　var i,t:longint;
　　　begin
　　　　t:=abs(x) mod max;
　　　　i:=0;
　　　　while (e[(t+i)mod max,1]<>0)and(e[(t+i)mod max,1]<>x) do
　　　　　inc(i);
　　　　locate:=(t+i) mod max;
　　　end;
　　procedure ins(x:longint);
　　　var posi:longint;
　　　begin
　　　　posi:=locate(x);
　　　　e[posi,1]:=x;
　　　　inc(e[posi,2]);
　　　end;
　　procedure solve(a:integer;s:longint);
　　　var i:integer;
　　　begin
　　　　if a=n div 2 then begin
　　　　　　　　　　　　　　　　for i:=1 to m do
　　　　　　　　　　　　　　　　　　ins(s+k[a]*mi[i,p[a]]);
　　　　　　　　　　　　　　　　exit;
　　　　　　　　　　　　　　　end;
　　　　for i:=1 to m do
　　　　　solve(a+1,s+k[a]*mi[i,p[a]]);
　　　end;
　　procedure find(a:integer;s:longint);
　　　var i:integer;
　　　　　　tmp,posi:longint;
　　　begin
　　　　if a=n then begin
　　　　　　　　　　　　for i:=1 to m do
　　　　　　　　　　　　　begin
　　　　　　　　　　　　　　　tmp:=-1*(s+k[a]*mi[i,p[a]]);
　　　　　　　　　　　　　　　posi:=locate(tmp);
　　　　　　　　　　　　　　　if e[posi,1]=tmp then inc(ans,e[posi,2]);
　　　　　　　　　　　　　end;
　　　　　　　　　　　exit;
　　　　　　　　　end;
　　　　for i:=1 to m do
　　　　　find(a+1,s+k[a]*mi[i,p[a]]);
　　　end;
　　procedure out;
　　　begin
　　　　writeln(fout,ans);
　　　　close(fout);
　　　end;
　　procedure special;
　　　var i:integer;
　　　begin
　　　　if n=1 then begin
　　　　　　　　　　　　if p[1]=0 then writeln(fout,m)
　　　　　　　　　　　　　　　　　　else writeln(fout,0);
　　　　　　　　　　　　close(fout);
　　　　　　　　　　　　halt;
　　　　　　　　　　　end;
　　　end;
　　begin
　　　init;
　　　precompute;
　　　special;
　　　solve(1,0);
　　　find(n div 2+1,0);
　　　out;
　　end.


　　　　　　　　　　6． 《迷宫的墙》的程序

　　program the_100_tough_problems_0020_walls_in_the_maze;
　　　const maxn=6001;
　　　　　　　p=7499;
　　　var fin,fout:text;
　　　　　n,ans:integer;
　　　　　data:array[1..maxn,1..4]of longint;
　　　　　e:array[0..2,0..p-1,1..4]of longint;
　　　　　r:array[1..maxn]of longint;
　　procedure init;
　　　var i,j:integer;
　　　　　　ch:char;
　　　begin
　　　　assign(fin,'d:\test\lab14.in');
　　　　assign(fout,'d:\test\lab.txt');
　　　　reset(fin);
　　　　rewrite(fout);
　　　　readln(fin,n);
　　　　for i:=1 to n-1 do
　　　　　begin
　　　　　　read(fin,ch);
　　　　　　case ch of
　　　　　　　'N':data[i,1]:=0;
　　　　　　　'Z':data[i,1]:=1;
　　　　　　　'C':data[i,1]:=2;
　　　　　　end;
　　　　　　for j:=2 to 4 do
　　　　　　　read(fin,data[i,j]);
　　　　　　readln(fin);
　　　　　end;
　　　　close(fin);
　　　　ans:=n;
　　　　fillchar(e,sizeof(e),0);
　　　　for i:=1 to n do
　　　　　r[i]:=i;
　　　end;
　　function locate(var a,b,c,d:longint):longint;
　　　var t:longint;
　　　　　　i:integer;
　　　begin
　　　　t:=r[b]*sqr(n)+r[c]*n+r[d];
　　　　t:=t mod p;
　　　　i:=0;
　　　　while (e[a,(t+i)mod p,1]<>0)and(e[a,(t+i)mod p,1]<>r[b]) do
　　　　　if (e[a,(t+i)mod p,2]<>r[c])or(e[a,(t+i)mod p,3]<>r[d]) then　inc(i);
　　　　locate:=(t+i)mod p;
　　　end;
　　procedure main;
　　　var i,j,t,k:integer;
　　　begin
　　　　for i:=n-1 downto 1 do
　　　　　begin
　　　　　　t:=locate(data[i,1],data[i,2],data[i,3],data[i,4]);
　　　　　　if e[data[i,1],t,1]<>r[data[i,2]] then begin
　　　　　　　　　　　　　　　　　　　for j:=2 to 4 do
　　　　　　　　　　　　　　　　　　　　e[data[i,1],t,j-1]:=r[data[i,j]];
　　　　　　　　　　　　　　　　　　　e[data[i,1],t,4]:=i;
　　　　　　　　　　　　　　　　　　end
　　　　　　　　　　　　　　　else begin
　　　　　　　　　　　　　　　　　　　　dec(ans);
　　　　　　　　　　　　　　　　　　　　r[i]:=e[data[i,1],t,4];
　　　　　　　　　　　　　　　　　　　　{for j:=1 to i-1 do
　　　　　　　　　　　　　　　　　　　　　for k:=2 to 4 do
　　　　　　　　　　　　　　　　　　　　　　if data[j,k]=i then
　　　　　　　　　　　　　　　　　　　　　　　data[j,k]:=e[data[i,1],t,4];}
　　　　　　　　　　　　　　　　　　　　end;
　　　　　end;
　　　end;
　　procedure out;
　　　begin
　　　　writeln({fout,}ans);
　　　　close(fout);
　　　end;
　　begin
　　　init;
　　　main;
　　　out;
　　end.

　　　　　　　　　　　　　　　　　　　　　　相关链接：浅谈竞赛中哈希表的应用（一）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（二）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（三）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（四）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（五）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（六）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（七）