解题报告(13)

1、第一题：水题，按照题目要求去枚举。注意，同一个字母加密后的字母是一样的，加密后一样的字母原字母也是一样的。var s1,s2,s3:string; a,b:array'A'.'Z'of char; i:longint; c:char;procedure main;begin readln(s1); readln(s2); readln(s3); fillchar(a,sizeof(a),' '); fillchar(b,sizeof(b),' '); for i:=1 to length(s1) do if (as1i<&g

2、t;' ')and(as1i<>s2i) or(bs2i<>' ')and(bs2i<>s1i) then begin writeln('Failed'); exit; end else begin as1i:=s2i; bs2i:=s1i; end; for c:='A' to 'Z' do if ac=' ' then begin writeln('Failed'); exit; end; for i:=1 to length(s3) do w

3、rite(as3i); writeln;end;begin assign(input,'spy.in'); reset(input); assign(output,'spy.out'); rewrite(output); main; close(input); close(output);end.第二题：数论题，分解质因数。通过a0,a1,b0,b1确定X中每项质因子的最大幂数和最小幂数。然后再把每个质因子的幂数范围乘起来。PS:参考程序过10个点的总耗时为0.23秒,评测环境为2.10GHz 2.00GBconst maxn=100; maxm=46341;t

4、ype data = record n,c : longint; end; ans = record n,min,max : longint; end; arr = array0.maxnof data;var a0,a1,b0,b1 : longint; fa0,fa1,fb0,fb1 : arr; xmin,xmax,xn : array0.maxnof longint; bool : array1.maxmof boolean; next : array1.maxmof longint;procedure change( n : longint;var a:arr);var i,k,t

5、: longint;begin fillchar(a,sizeof(a),0); t:=0; i:=2; while n>1 do beginif (i>trunc(sqrt(n)and(t=0) then break; if i=-1 then break;if n mod i=0 thenbegin inc(t); n:=n div i;endelsebegin if t>0 then begin inc(a0.n); with aa0.n do begin n:=i; c:=t; end; t:=0; end; i:=nexti;end; end; if t>0

6、then begin inc(a0.n); aa0.n.n:=i; aa0.n.c:=t; end; if n>1 then begin inc(a0.n); aa0.n.n:=n; aa0.n.c:=1; end;end; change function get(var a : arr;n:longint):longint;var i : longint;begin for i:=1 to a0.n doif ai.n=n then exit(ai.c); exit(0);end; get function min_(a,b : longint):longint;begin if a&

7、lt;b then exit(a) else exit(b);end; min function max_(a,b : longint):longint;begin if a>b then exit(a) else exit(b);end;procedure cmin(n ,c : longint);var i : longint;begin for i:=1 to xn0 doif xni=n thenbegin xmini:=max_(xmini,c); exit;end; inc(xn0); xnxn0:=n; xminxn0:=c; xmaxxn0:=maxlongint;end

8、; cmin procedure cmax(n ,c : longint);var i : longint;begin for i:=1 to xn0 doif xni=n thenbegin xmaxi:=min_(xmaxi,c); exit;end; inc(xn0); xnxn0:=n; xmaxxn0:=c; xminxn0:=0;end; cmin procedure init;var i,j:longint;begin fillchar(bool,sizeof(bool),true); for i:=2 to trunc(sqrt(maxm) do if booli then f

9、or j:=2 to maxm div i do booli*j:=false; j:=-1; fillchar(next,sizeof(next),255); for i:=maxm downto 1 do begin nexti:=j; if booli then j:=i; end;end;procedure main;var i,j,k,t: longint;begin readln(a0,a1,b0,b1); change(a0,fa0); change(a1,fa1); change(b0,fb0); change(b1,fb1); fillchar(xn,sizeof(xn),0

10、); fillchar(xmax,sizeof(xmax),0); fillchar(xmin,sizeof(xmin),0); for i:=1 to fa10.n docmin(fa1i.n,fa1i.c); for i:=1 to fb10.n docmax(fb1i.n,fb1i.c); for i:=1 to fb10.n do begin k:=get(fb0,fb1i.n); if k<fb1i.c then cmin(fb1i.n,fb1i.c); end; for i:=1 to fa00.n do begin k:=get(fa1,fa0i.n); if k<f

11、a0i.c then cmax(fa0i.n,k); end; for i:=1 to xn0 do beginif xmini>xmaxi then begin writeln(0);exit;end;if xmaxi=maxlongint then begin writeln(0);exit;end; end; t:=1 ; for i:=1 to xn0 dot:=t*(xmaxi-xmini+1); writeln(t);end; main var tt:longint;begin assign(input,'son.in'); reset(input); ass

12、ign(output,'son.out'); rewrite(output); readln(tt); init; for tt:=tt downto 1 do begin main end; close(input); close(output);end.第三题：图论题，两次SPFA，用ai表示从起点开始到i结点能经过的最小值，用bi表示从终点延反向边到达i结点能经过的最大值。Ans=max(bi-ai)。const maxn=100010; maxm=1000010;type data=record t,f,next:longint; end;var n,m,ls:long

13、int; a,c,d,stack,v:array0.maxnof longint; f:array1.maxnof boolean; seg:array1.maxmof data;procedure insert_e(s,t,f1,f2:longint);begin inc(ls); segls.t:=t; segls.f:=f1; segls.next:=as; as:=ls; inc(ls); segls.t:=s; segls.f:=f2; segls.next:=at; at:=ls;end;procedure init;var i,j,k,l:longint;begin readln

14、(n,m); fillchar(a,sizeof(a),255); ls:=0; for i:=1 to n do read(vi); for i:=1 to m do begin readln(j,k,l); if l=1 then insert_e(j,k,1,2) else insert_e(j,k,3,3); end;end;function max(a,b:longint):longint;begin if a>b then exit(a) else exit(b);end;function min(a,b:longint):longint;begin if a<b th

15、en exit(a) else exit(b);end;procedure spfa1;var i,k,open,closed:longint;begin fillchar(c,sizeof(c),127); fillchar(f,sizeof(f),0); f1:=true; open:=0; closed:=1; stack1:=1; c1:=v1; while open<closed do begin inc(open); k:=stackopen mod maxn; fk:=false; i:=ak; while i<>-1 do begin if (segi.f a

16、nd 1=1)and(min(ck,vsegi.t)<csegi.t) then begin csegi.t:=min(ck,vsegi.t); if not fsegi.t then begin fsegi.t:=true; inc(closed); stackclosed mod maxn:=segi.t; end; end; i:=segi.next; end; end;end;procedure spfa2;var i,k,open,closed:longint;begin fillchar(d,sizeof(d),0); fillchar(f,sizeof(f),0); fn:

17、=true; open:=0; closed:=1; stack1:=n; dn:=vn; while open<closed do begin inc(open); k:=stackopen mod maxn; fk:=false; i:=ak; while i<>-1 do begin if (segi.f and 2=2)and(max(dk,vsegi.t)>dsegi.t) then begin dsegi.t:=max(dk,vsegi.t); if not fsegi.t then begin fsegi.t:=true; inc(closed); sta

18、ckclosed mod maxn:=segi.t; end; end; i:=segi.next; end; end;end;procedure main;vari,ans:longint;begin spfa1; spfa2; ans:=0; for i:=1 to n do ans:=max(ans,di-ci); writeln(ans);end;begin assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output); init; main; cl

19、ose(input); close(output);end.第四题：搜索题，有时候这个世界需要些暴力。DFS搜索，每次选取填入的数的方案数进行枚举。PS：据说从右下角直接枚举到左上角，比加剪枝也能拿95分。var n,ans,l,time:longint; a:array1.81,1.3of longint; c:array1.27,0.9of boolean; v:array1.81of longint; d,d2,d3:array1.81of longint; o:array1.81of longint;function max(a,b:longint):longint;begin if

20、a>b then exit(a) else exit(b);end;function min(a,b:longint):longint;begin if a<b then exit(a) else exit(b);end;procedure init;var i,j,k:longint;begin for i:=1 to 9 do for j:=1 to 9 do begin k:=(i-1)*9+j; ak,1:=i; ak,2:=j+9; ak,3:=(i-1)div 3*3+(j-1)div 3+1+18; vk:=10-max(abs(i-5),abs(j-5); end;

21、 fillchar(c,sizeof(c),1); for i:=1 to 81 do begin read(di); cai,1,di:=false; cai,2,di:=false; cai,3,di:=false; end;end;procedure check;var i,t:longint;begin t:=0; for i:=1 to 81 do inc(t,di*vi); if t>ans then ans:=t;end;procedure dfs(dep:longint);var i,k:longint;begin if dep>l then begin check;exit;end; if dep<1 then begin check;exit;end; inc(time); if time>10000000 then begin writeln(ans);close(input);close(output);halt;end; k:=odep; for i:=1 to 9 do if cak,1,i and cak,2,i and cak,3,i then begin cak,1,i:=false; cak,2,i:=false; cak,3,i