解題報告(13)解析

1、第一題：水題，按照題目要求去枚舉。注意，同一個字母加密后的字母是一樣的，加密后一樣的字母原字母也是一樣的。vars1,s2,s3:string;a,b:array'A'.'Z'ofchar;i:longint;c:char;proceduremain;beginreadln(s1);readln(s2);readln(s3);fillchar(a,sizeof(a),'');fillchar(b,sizeof(b),'');fori:=1tolength(s1)doif(as1i<>'')and(as1

2、i<>s2i)or(bs2i<>'')and(bs2i<>s1i)thenbeginwriteln('Failed');exit;endelsebeginas1i:=s2i;bs2i:=s1i;end;forc:='A'to'Z'doifac=''thenbeginwriteln('Failed');exit;end;fori:=1tolength(s3)dowrite(as3i);writeln;end;beginassign(input,'spy.in

3、');reset(input);assign(output,'spy.out');rewrite(output);main;close(input);close(output);end.第二題：數(shù)論題，分解質(zhì)因數(shù)。通過a0,a1,b0,b1確定X中每項質(zhì)因子的最大冪數(shù)和最小冪數(shù)。然后再把每個質(zhì)因子的冪數(shù)范圍乘起來。PS:參考程序過10個點的總耗時為0.23秒,評測環(huán)境為2.10GHz2.00GBconstmaxn=100;maxm=46341;typedata=recordn,c:longint;end;ans=recordn,min,max:longint;end;a

4、rr=array0.maxnofdata;vara0,a1,b0,b1:longint;fa0,fa1,fb0,fb1:arr;xmin,xmax,xn:array0.maxnoflongint;bool:array1.maxmofboolean;next:array1.maxmoflongint;procedurechange(n:longint;vara:arr);vari,k,t:longint;beginfillchar(a,sizeof(a),0);t:=0;i:=2;whilen>1dobeginif(i>trunc(sqrt(n)and(t=0)thenbreak;i

5、fi=-1thenbreak;ifnmodi=0thenbegininc(t);n:=ndivi;endelsebeginift>0thenbegininc(a0.n);withaa0.ndobeginn:=i;c:=t;end;t:=0;end;i:=nexti;end;end;ift>0thenbegininc(a0.n);aa0.n.n:=i;aa0.n.c:=t;end;ifn>1thenbegininc(a0.n);aa0.n.n:=n;aa0.n.c:=1;end;end;changefunctionget(vara:arr;n:longint):longint;

6、vari:longint;beginfori:=1toa0.ndoifai.n=nthenexit(ai.c);exit(0);end;getfunctionmin_(a,b:longint):longint;beginifa<bthenexit(a)elseexit(b);end;minfunctionmax_(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;procedurecmin(n,c:longint);vari:longint;beginfori:=1toxn0doifxni=nthenbeginxmi

7、ni:=max_(xmini,c);exit;end;inc(xn0);xnxn0:=n;xminxn0:=c;xmaxxn0:=maxlongint;end;cminprocedurecmax(n,c:longint);vari:longint;beginfori:=1toxn0doifxni=nthenbeginxmaxi:=min_(xmaxi,c);exit;end;inc(xn0);xnxn0:=n;xmaxxn0:=c;xminxn0:=0;end;cminprocedureinit;vari,j:longint;beginfillchar(bool,sizeof(bool),tr

8、ue);fori:=2totrunc(sqrt(maxm)doifboolithenforj:=2tomaxmdividobooli*j:=false;j:=-1;fillchar(next,sizeof(next),255);fori:=maxmdownto1dobeginnexti:=j;ifboolithenj:=i;end;end;proceduremain;vari,j,k,t:longint;beginreadln(a0,a1,b0,b1);change(a0,fa0);change(a1,fa1);change(b0,fb0);change(b1,fb1);fillchar(xn

9、,sizeof(xn),0);fillchar(xmax,sizeof(xmax),0);fillchar(xmin,sizeof(xmin),0);fori:=1tofa10.ndocmin(fa1i.n,fa1i.c);fori:=1tofb10.ndocmax(fb1i.n,fb1i.c);fori:=1tofb10.ndobegink:=get(fb0,fb1i.n);ifk<fb1i.cthencmin(fb1i.n,fb1i.c);end;fori:=1tofa00.ndobegink:=get(fa1,fa0i.n);ifk<fa0i.cthencmax(fa0i.n

10、,k);end;fori:=1toxn0dobeginifxmini>xmaxithenbeginwriteln(0);exit;end;ifxmaxi=maxlongintthenbeginwriteln(0);exit;end;end;t:=1fori:=1toxn0dot:=t*(xmaxi-xmini+1);writeln(t);end;mainvartt:longint;beginassign(input,'son.in');reset(input);assign(output,'son.out');rewrite(output);readln(

11、tt);init;fortt:=ttdownto1dobeginmainend;close(input);close(output);end.第三題：bi 表示從終點延圖論題，兩次SPFA,用ai表示從起點開始到i結(jié)點能經(jīng)過的最小值，用反向邊到達i結(jié)點能經(jīng)過的最大值。Ans=max(bi-ai)。constmaxn=100010;maxm=1000010;typedata=recordt,f,next:longint;end;varn,m,ls:longint;a,c,d,stack,v:array0.maxnoflongint;f:array1.maxnofboolean;seg:array

12、1.maxmofdata;procedureinsert_e(s,t,f1,f2:longint);begininc(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;procedureinit;vari,j,k,l:longint;beginreadln(n,m);fillchar(a,sizeof(a),255);ls:=0;fori:=1tondoread(vi);fori:=1tomdobeginreadln(j,k,l);i

13、fl=1theninsert_e(j,k,1,2)elseinsert_e(j,k,3,3);end;end;functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;functionmin(a,b:longint):longint;beginifa<bthenexit(a)elseexit(b);end;procedurespfa1;vari,k,open,closed:longint;beginfillchar(c,sizeof(c),127);fillchar(f,sizeof(f),0);f1

14、:=true;open:=0;closed:=1;stack1:=1;c1:=v1;whileopen<closeddobegininc(open);k:=stackopenmodmaxn;fk:=false;i:=ak;whilei<>-1dobeginif(segi.fand1=1)and(min(ck,vsegi.t)<csegi.t)thenbegincsegi.t:=min(ck,vsegi.t);ifnotfsegi.tthenbeginfsegi.t:=true;inc(closed);stackclosedmodmaxn:=segi.t;end;end;

15、i:=segi.next;end;end;end;procedurespfa2;vari,k,open,closed:longint;beginfillchar(d,sizeof(d),0);fillchar(f,sizeof(f),0);fn:=true;open:=0;closed:=1;stack1:=n;dn:=vn;whileopen<closeddobegininc(open);k:=stackopenmodmaxn;fk:=false;i:=ak;whilei<>-1dobeginif(segi.fand2=2)and(max(dk,vsegi.t)>ds

16、egi.t)thenbegindsegi.t:=max(dk,vsegi.t);ifnotfsegi.tthenbeginfsegi.t:=true;inc(closed);stackclosedmodmaxn:=segi.t;end;end;i:=segi.next;end;end;end;proceduremain;vari,ans:longint;beginspfa1;spfa2;ans:=0;fori:=1tondoans:=max(ans,di-ci);writeln(ans);end;beginassign(input,'trade.in');reset(input

17、);assign(output,'trade.out');rewrite(output);init;main;close(input);close(output);end.第四題：搜索題，有時候這個世界需要些暴力。DFS搜索，每次選取填入的數(shù)的方案數(shù)進行枚舉。PS:據(jù)說從右下角直接枚舉到左上角，比加剪枝也能拿95分。varn,ans,l,time:longint;a:array1.81,1.3oflongint;c:array1.27,0.9ofboolean;v:array1.81oflongint;d,d2,d3:array1.81oflongint;o:array1.81

18、oflongint;functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;functionmin(a,b:longint):longint;beginifa<bthenexit(a)elseexit(b);end;procedureinit;vari,j,k:longint;beginfori:=1to9doforj:=1to9dobegink:=(i-1)*9+j;ak,1:=i;ak,2:=j+9;ak,3:=(i-1)div3*3+(j-1)div3+1+18;vk:=10-max(abs(

19、i-5),abs(j-5);end;fillchar(c,sizeof(c),1);fori:=1to81dobeginread(di);cai,1,di:=false;cai,2,di:=false;cai,3,di:=false;end;end;procedurecheck;vari,t:longint;begint:=0;fori:=1to81doinc(t,di*vi);ift>ansthenans:=t;end;proceduredfs(dep:longint);vari,k:longint;beginifdep>lthenbegincheck;exit;end;ifdep<1thenbegincheck;exit;end;inc(time);iftime>10000000thenbeginwriteln(ans);close(input);close(output);halt;end;k:=odep;fori:=1to9doifcak,1,iandcak,2,iandcak,3,ithenbegincak,1,i:=false;cak,2,i:=fals