試題程序及解題報(bào)告mn07f1

親和數(shù)某一天，tenshi看了一本趣味數(shù)學(xué)書，上面提到了親和數(shù)：定義數(shù)對(x,y)為親和數(shù)對當(dāng)且僅當(dāng)x、y為不同正整數(shù)，且x、y各自的所有非自身正因子之和等于另一個(gè)數(shù)。例如(220,284)和(280,224)都是親和數(shù)對，因?yàn)椋?20的所有非自身正因子之和為：1+2+4+5+10+11+20+22+44+55+110=284284的所有非自身正因子之和為：1+2+4+71+142=220數(shù)對(x,y)跟(y,x)被認(rèn)為是同一數(shù)對，所以我們只考慮x<y的情況。親和數(shù)任務(wù)：

tenshi對某個(gè)范圍內(nèi)的親和數(shù)對的數(shù)量非常感興趣，所以希望你能幫她編寫一個(gè)程序計(jì)算給定范圍內(nèi)的親和數(shù)對的數(shù)量。給定一個(gè)范圍A到B，如果A≤x≤B，則我們稱(x,y)在范圍[A,B]內(nèi)。

1≤A≤B≤10^8且B-A≤10^5

輸入：

amicable.in

2001200輸出：

amicable.out

2注：[200,1200]內(nèi)的數(shù)對只有兩個(gè)，分別是(220,284)和(11841210)窮舉法利用窮舉法求因子算法:init;main;print;procedureinit;beginassign(f,'amicable.in');reset(f);readln(f,a,b);close(f);end;procedureprint;beginassign(f,'amicable.out');rewrite(f);writeln(f,s);close(f);end;proceduremain;vari,k:longint;begins:=0;fori:=atobdobegink:=js(i);ifk>ithenifjs(k)=ithens:=s+1;end;end;functionjs(x:longint):longint;vart,i:longint;begint:=1;fori:=2totrunc(sqrt(x))doifxmodi=0thent:=t+i+(xdivi);js:=tend;amicable.in0=10.0(0.35s)amicable.in1=10.0(0.02s)amicable.in2=10.0(0.06s)amicable.in3=10.0(0.01s)amicable.in4=10.0(0.34s)amicable.in5=10.0(0.05s)amicable.in6=10.0(1.05s)amicable.in7=10.0(0.14s)amicable.in8=10.0(1.85s)amicable.in9=10.0(1.58s)表達(dá)式的轉(zhuǎn)換平常我們書寫的表達(dá)式稱為中綴表達(dá)式，因?yàn)樗鼘⑦\(yùn)算符放在兩個(gè)操作數(shù)中間，許多情況下為了確定運(yùn)算順序，括號是不可少的，而后綴表達(dá)式就不必用括號了。后綴標(biāo)記法：書寫表達(dá)式時(shí)采用運(yùn)算符緊跟在兩個(gè)操作數(shù)之后，從而實(shí)現(xiàn)了無括號處理和優(yōu)先級處理，使計(jì)算機(jī)的處理規(guī)則簡化為：從左到右順序完成計(jì)算，并用結(jié)果取而代之。例如：8–(3+2*6)/5+4可以寫為：8326*+5/–4+其計(jì)算步驟為：8326*+5/–4+8312+5/–4+8155/–4+83–4+54+9expstr

：8–(3+2*6)/5+4newexp：8326*+5/–4+expstr

：8–(3+2*6)/5+4newexp：8326*+5/–4+8–(3+2*)6*+/5+/+–4varf:text;expstr,{中綴表達(dá)式}newexp:string;{后綴表達(dá)式}s:array[1..255]ofchar;{堆棧}opcode:array[1..255]of0..3;sp,len:integer;{堆棧指針，串長}ch:char;init;main;print;procedureinit;beginassign(f,'express.in');reset(f);readln(f,expstr);close(f);sp:=0;len:=length(expstr);end;beginfori:=1tolendobeginch:=expstr[i];casechof'0'..'9':newexp:=newexp+ch;'+','-','*','/','^':oprate;'(':opleft;')':opright;end;end;whilesp>0dobeginnewexp:=newexp+s[sp];dec(sp);end;end;mainprocedureoprate;varfg:integer;bl:boolean;begincasechof'+','-':fg:=1;'*','/':fg:=2;'^':fg:=3;end;bl:=false;repeatif(sp=0)or((sp>0)and(opcode[sp]<fg))thenbeginpush(ch);opcode[sp]:=fg;bl:=true;endelsebeginwhile(sp>0)and(opcode[sp]>=fg)dobeginnewexp:=newexp+s[sp];sp:=sp-1;end;end;untilbl;end;procedureopleft;beginpush(ch);opcode[sp]:=0;end;procedureopright;beginifsp<>0thenwhiles[sp]<>'('dobeginnewexp:=newexp+s[sp];sp:=sp-1;end;dec(sp);end;背誦單詞小小在背單詞，她發(fā)現(xiàn)當(dāng)背誦了單詞beauty以后，再接著背誦單詞beautiful就會(huì)覺得容易許多。由于有很多單詞要背，她希望找到一種好的背誦順序。單詞A和它的前驅(qū)B的最大公共前綴的長度稱為背誦單詞A的便利值(例如：B='beauty',A='beautiful',則A的便利值是len({A,B})=len('beaut')=5),我們認(rèn)為一個(gè)背誦單詞A的花費(fèi)是它的長度(例如:'beautiful'的長度len(‘beautiful')=9)與它的便利值之差（對于上述例子背誦A的花費(fèi)為9-5=4）。請你求一個(gè)背誦順序，使得背誦這些單詞的花費(fèi)總和最小。假設(shè)一開始你什么單詞都不記得。輸入：

LETTER.IN

5

beauty

beautiful

flower

man

dog輸出：

LETTER.OUT

beauty

beautiful

dog

flower

man狀態(tài):f(i,j)表示第i到j(luò)個(gè)字符的最優(yōu)值邊界狀態(tài):f(i,i)=len(data[i])1<=i<=ndata[i]表示第i個(gè)字符串a(chǎn)ns=f(1,n)狀態(tài)轉(zhuǎn)移方程f(i,j)=maxLen(data[i])-g[i,i+1]+f(i+1,j)Len(data[i])-g[s[i+1,i+1,1],1]-g[i,s[i+1,j,1]]

+f(i+1,i+1)+f(i+2,j)g[i,j]表示第i個(gè)單詞與第j個(gè)單詞的便利值Len(data[i])-g[s[i+1,i+2,2],i]-g[i,s[i+2,j,1]]

+f(i+1,i+2)+f(i+3,j)Len(data[i])-g[s[i+1,j-1,j-i-1],i]-g[i,s[j,j,1]]

+f(i+1,j-1)+f(j,j)…………s[i,j,k]表示第i個(gè)單詞與第j個(gè)單詞的最優(yōu)便利值序列的第k個(gè)單詞號Len(data[i])-g[i,j]+f(i+1,j-1)盟軍敢死隊(duì)

倉庫是一個(gè)m*n的矩形區(qū)域，每一格用一個(gè)字符來描述：“

.”

代表空地;“#”

代表墻或障礙物;“^”,“v”(小寫),“<”,“>”

四個(gè)字符分別表示正向NSWE四個(gè)方向看的敵人。敵人總是保持固定不動(dòng)并朝著一個(gè)方向看，從這個(gè)方向一直延伸直到邊界或障礙物的區(qū)域是他的視線范圍，如果一個(gè)敵人沒有在任何人的視線范圍之內(nèi)，敢死隊(duì)員就可以消滅他。你不能消滅一個(gè)正在另一個(gè)活著的敵人視線范圍內(nèi)的敵人，否則你就會(huì)被發(fā)現(xiàn)，后果不堪設(shè)想。一個(gè)敵人不會(huì)成為遮擋視線的障礙物。輸入數(shù)據(jù)的第一行是用空格分開的兩個(gè)整數(shù)n,m，分別表示倉庫的長和寬。接下來有n行，每行m個(gè)字符，是倉庫的描述。cmdo.in

22

>^

#^

cmdo.out

2cmdo.in

13

>.<

cmdo.out

Impossible對每一個(gè)敵人賦予一個(gè)編號1~n(n表示敵人數(shù))對于表示一個(gè)消滅所有敵人的順序的序列Q